c++ - 如何计算双向链表中元素的数量？

Question

列表是这样排列的:

struct Node {
    Node *next;
    Node *prev;
    T datum;
};

Node *first;   // points to first Node in list, or 0 if list is empty  
Node *last;    // points to last Node in list, or 0 if list is empty

我试过:

int i =0;  
while(first->next)
{  
    i++;  
}  

但这似乎不对。

Answer 1

您可以通过将指针从一个节点移动到另一个节点直到指针为 NULL 来解决此问题。计算指针为非 NULL 的次数。所需的代码非常简单:

int list_size(const Node *ptr)
{
    int size = 0;
    while (ptr) {
        size++;
        ptr = ptr->next;
    }
    return size;
}

像这样使用它:

int size = list_size(first);

此代码不使用 prev 指针，因此它也适用于单链表。