如何确定链接列表的大小而不使用while循环？

Question

我需要输出一个链表中的节点数。我的老师说这个链表跟踪了它的数据并“知道”有多少个节点。所以，我不需要一个while循环来确定链表的大小。我很难弄清楚一个方法，而不是一个while循环来打印出大小。

这是链表：

template <class T> 
class LinkedList 
{ 
private: 
struct ListNode 
{ 
    T data ; 
    struct ListNode * next; 
}; 

ListNode *head; 

public: 
LinkedList() { head = nullptr; } 
~LinkedList(); 

// Linked list operations 
void insertNode(T); 
bool deleteNode(T); 
void displayList() const; 
}; 


/////////// Implementation portion of linked list with template ////////////// 

// displayList: print all list data 
template <class T> 
void LinkedList<T>::displayList() const 
{ 
ListNode * ptr = head; 

while (ptr != nullptr) 
{ 
    cout << ptr->data << endl; 
    ptr = ptr->next; 
} 
} 

// insertNode: add a node in list order 
template <class T> 
void LinkedList<T>::insertNode(T newValue) 
{ 
ListNode *newNode; 
ListNode *pCur; 
ListNode *pPre = NULL; 

newNode = new ListNode; 
newNode->data = newValue; 
newNode->next = nullptr; 

if (head == nullptr) 
{ 
    head = newNode; 
} 
else 
{ 
    pCur = head; 
    pPre = nullptr; 
    while (pCur != nullptr && pCur->data < newValue) 
    { 
     pPre = pCur; 
     pCur = pCur->next; 
    } 

    if (pPre == nullptr) 
    { 
     head = newNode; 
     newNode->next = pCur; 
    } 
    else 
    { 
     pPre->next = newNode; 
     newNode->next = pCur; 
    } 
} 
} 

// deleteNode: delete a node if found 
template <class T> 
bool LinkedList<T>::deleteNode(T toBeDeleted) 
{ 
ListNode *pCur; 
ListNode *pPre; 

if (!head) 
    return true; 

pCur = head; 
pPre = NULL; 
while (pCur != NULL && pCur->data < toBeDeleted) 
{ 
    pPre = pCur; 
    pCur = pCur->next; 
} 

if (pCur != NULL && pCur->data == toBeDeleted) 
{ 
    if (pPre) 
     pPre->next = pCur->next; 
    else 
     head = pCur->next; 
    delete pCur; 
    return true; 
} 
return false; 
} 


// destructor, delete all nodes 
template <class T> 
LinkedList<T>::~LinkedList() 
{ 
ListNode *ptr = head; 
while (ptr != NULL) 
{ 
    head = head->next; 
    delete ptr; 
    ptr = head; 
} 
} 

Answer 1

使用你定义的代码，该列表的大小不是由列表直接存储。除此之外，链表的主要优点是每个节点都不知道列表的其余部分，并且存储大小将会失去此目的。

但是，您可能误解了在不使用while循环时被问到的问题。每个节点都知道它的长度是1+（它的尾部的长度），所以获得链表长度的更合适的实现是递归，而不是迭代。

下面是一个非常简单的LinkedList类的例子，它实现了使用递归的简单方法。正如你所看到的，代码不使用迭代，只检查它自己的数据，然后为下一个节点调用相同的方法。虽然程序语言中的递归在大多数情况下效率较低，但对于像这样的结构，毫无疑问它是优雅的。

#include <iostream> 

template<class T> 
class LinkedList 
{ 
private: 
    T data; 
    LinkedList* next; 
public: 
    LinkedList() 
     : LinkedList(T()) { 
    } 
    LinkedList(T value) 
     : data(value), next(nullptr) { 
    } 
    ~LinkedList() { 
     delete next; 
    } 

    void insertNode(T newValue) { 
     if (!next) { 
      next = new LinkedList(newValue); 
      return; 
     } 

     next->insertNode(newValue); 
    } 

    void displayList() const { 
     std::cout << data << std::endl; 
     if (next) { 
      next->displayList(); 
     } 
    } 

    T& at(int N) { 
     if (N == 0) { 
      return this->data; 
     } 
     return next->at(N-1); 
    } 

    int size() { 
     if (!next) { 
      return 1; 
     } 

     return 1+next->size(); 
    } 
}; 


int main(int argc, char const *argv[]) 
{ 
    LinkedList<int>* test = new LinkedList<int>(0); 

    for (int i = 1; i < 10; ++i) { 
     test->insertNode(i); 
    } 

    std::cout << "List of length: " << test->size() << std::endl; 
    test->displayList(); 

    return 0; 
} 

你会发现我并没有包括deleteNode，那是因为写它上面的过于简单类是不可能的地方名单只有一个节点的情况。实现这一点的一种可能方式是拥有一个包装类，就像你在原始代码中一样，它是一个指向链表开始的指针。见here。