带有 Node class 的链表如何在 C++ 中工作？

Question

我目前正在学习数据结构和算法 class，结果发现它主要面向链表的概念。这些是我难以理解的一些事情：

如何将数字插入数据？
如何从一个节点移动到下一个节点？
如何在main中调用Nodeclass并打印出数据值？

我有以下代码。我做错了吗？

#include <iostream>

using namespace std;

class LinkedList
{

    class Node
    {
      public:
        Node (int data, Node *n);
        int data;
        Node *next;
    };
        
    Node *head;
};


int main()
{

    LinkedList::Node NodeObj;
    NodeObj.data = 5;
    cout <<NodeObj.data;
    return 0;
}

Answer 1

一个不错的教程位于：http://www.zentut.com/c-tutorial/c-linked-list/

从编程的角度来看，通常您的 LinkedList class 会有一些方法来完成您询问的事情，例如：

添加 - 在链表末尾创建一个新条目
InsertAfter(Node *n) - 在列出的列表中的指定节点之后创建一个新条目
Remove(Node *n) - 从链表中移除指定的节点
Count() - returns 链表中节点数的计数
Get(long i) - returns 指向链表中第 i 个条目的指针
Find(某种类型的条件) - return指向匹配
销毁——删除链表中的所有节点

然后你的主线只是调用这些方法来利用链表（object 封装的整个点）。注意有一个LinkedListobject实例化，它实例化和管理Nodeobjects.

因此，如果您要从某个输入数组 (inArray) 中存储 10 个数字，您可以执行如下操作：

Node* n;
llObj = new LinkedList;
For (i=0; i<=9; i++) {
    n = llObj.add();
    n.data = inArray[i];
}

要遍历链表，您可以执行以下操作：

For (i=0; i<=llObj.Count(); i++) {
    n = llObj.get(i);
    n.data = n.data + 1;
}

但是，如果您从下面的代码示例中自己编写一个 .get() 方法，您会发现上面的代码非常效率低下，并且不是理想的方法从主线代码单步执行整个链表。

要找到数字 6：

n = llObj.find(6);

等等。通常，链表不会像您的示例那样只存储一个数据值，而是存储一个结构或 object。因此，像 Find 这样的方法变得更有用，因为您可以创建 Find 方法来查看结构或 object.

中的各个字段

Add 方法只是遍历列出的列表中的所有现有条目，直到找到最后一个条目，然后创建一个新条目，并将以前的最后一个条目链接到现在新的最后一个条目。

Node* LinkedList::add() {
    void *n = NULL;
    if (head != NULL) {
        // one or more Nodes do exist
        // first loop until we find the last-most node who's n.next == NULL
        n = head;
        while (n.next != NULL) n = n.next;
        // found the last node, now allocate a new Node, and store a pointer to it in the formerly last node's .next property
        n.next = new Node;
        n = n.next;
        // IMPORTANT: ensure this new last Node's .next is forced to be null
        n.next = NULL;
    }
    else
    {
        // the header is NULL, so there is no first node yet
        // allocate a new Node and store a pointer to it in the LinkedList header
        head = new Node;
        n = head;
        // IMPORTANT: ensure this first Node's .next is forced to be null
        n.next = NULL;  
    {
    return n;
}

注意While循环...这是关键的linked-list遍历机制。该循环检查当前节点的 .next 字段……如果它有一个 non-NULL 指针，则循环通过将该 .next 指针复制到循环指针 n 来循环，并再次测试。一旦循环找到 .next 为 NULL 的节点，则找到最后一个节点，然后循环退出，n 包含指向最后一个节点的指针。

另请注意有关 LinkedList class 的 .head 属性的 If 语句。当链表为空时，总是需要做一些特殊的代码来计算。有几种处理方法；我选择了使用最少数据内存的那个。

删除节点意味着链表中只有"skipping over it"。我们遍历列出的列表，直到找到要删除的列表，我们只是 "move back" 它的 .next 属性到前一个条目的 .next 指针。链接列表维基百科条目中有一张好图片：

代码示例：

void LinkedList::remove(Node* nodeToRemove) {
    // do nothing if we've been given a NULL pointer
    if (nodeToRemove == NULL) return;
    Node *n;
    if (nodeToRemove == head) {
        // the node to remove is the very first node, so set the head
        // to the contents of the first node's .next property
        head = n.next;
        delete n;
        return;
    }

    // need to find the indicated node; the following loop locates the
    // node that is immediately before the node to be removed; note too
    // that we have to test for the end of the linked list because the
    // caller may have provided a bad pointer value
    n = head;
    while (n.next != NULL && n.next != nodeToRemove) n = n.next;
    if (n.next == NULL) return;  // reached end of linked list without finding the node
    // good, the node immediately before the node to remove has been found!
    Node* r = n.next;   // this is inefficient code but want to make it very clear to newbies
    n.next = r.next;
   delete r;
}

请注意，我们必须再次对 LinkedList header 做一些特殊的逻辑处理。请原谅我在代码中使用了 returns；许多挑剔的贴纸会认为 no-no。还要注意在上面的代码中，我们不需要做特殊的逻辑来说明链表的结尾，只需要它的开头。如果 node-to-remove 是链表中的最后一个节点（并且它的 r.next 因此 == NULL），那么 "n.next = r.next" 代码行只是将 NULL 移回链表中的一个位置，这正是我们想要的。

您现在应该能够弄清楚如何在我提到的 LinkedList class 中创建所有其他方法。

=================================

我很喜欢某人的回答，不幸的是他删除了。对于一个 5 岁的孩子来说，链表确实很像寻宝游戏。在 Treasure Hint 中，您必须亲自前往每个位置才能获得下一个位置的线索。在链表中，您必须访问节点的位置才能找到下一个节点位置的地址。一个完美的类比，对第一个提供它的回答者表示敬意。

带有 Node class 的链表如何在 C++ 中工作？

How does a linked list with Node class work in C++?

c++

class

linked-list

nodes