c++ - C++函数中链表的大小

Question

谁能告诉我检查链表大小(节点数)的代码是什么。这就是我的代码(插入和删除头部+打印所有节点的信息)

struct node 
{
    int info;
    node *nextptr;
};

class list
{
private:
    node *L,*tail;
     int count;

public:
    list()
    {
        L=tail=NULL;
        count=0;
    }

    void InsertHead(int info);
    int RemoveHead();
    void Print();
}; 

Answer 1

管理链表大小的方法有两种，都各有缺点。最简单的是管理一个计数变量，你的类有这样一个变量，你每次向列表中添加一个节点时递增它，每次删除一个节点时递减它。

在这种情况下，您可以在常数时间内获得链表的大小。缺点是一个有用的操作，拼接，你把一个列表切成中间某个地方的两个较小的列表，变成了线性复杂度，因为现在你必须计算子列表中有多少节点。

如果您希望 splice 保持不变，则无法跟踪列表的大小。所以任何时候你想要获得列表的大小，你都必须计算那里有多少个节点。