如何確定鏈接列表的大小而不使用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。