如何在不使用 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，这是因为对于列表只有一个节点的情况，为上面的过度简化类编写它是不可能的。实现这一点的一种可能方法是拥有一个包装类，就像原始代码中的包装类一样，它是一个指向链表开头的指针。看这里。