c++ - 关于链表节点的说明

Question

我想了解什么是链表节点。传递给构造函数的是什么？特别是，什么是 node* head？它是指向结构本身的指针。链表如何适应这种结构？

struct node {
    node* next;
    int data;
    explicit node(int data) : node(nullptr, data) {}
    node(node* head, int data) : next(head), data(data) {}
}

编辑::

我应该更清楚我的问题。我知道我可以手动定义每个节点并初始化它们并继续这样做以创建一个列表。但是我如何在不指定每次都想要什么的情况下从节点实现一个列表呢？我想我的意思是我不确定如何从给出节点定义的节点构建列表。

Answer 1

让我们先关注单个节点:

--------
| data |
--------
| next |
--------

显然，data 成员保存当前节点的数据。因此，节点只是一对data 持有者，以及指向列表中下一个元素的指针(next)。现在，“链接”列表这个名字告诉你这种数据结构是由一些链接连接起来的。所以你可能有多个节点，链接在一起，就像这样:

--------     --------       --------
| 5    |     | 3    |     | 6       |
--------     --------      --------
| next | --->| next | --->| nullptr |
--------     --------      --------

很容易找到列表中的最后一个节点是什么节点 - next 指针的值为 nullpointer 的那个节点，表明列表中没有更多节点。

但是，我们如何找到列表的第一个元素呢？我们将通过保留 head 指针来做到这一点 - 指向内存中某处列表的第一个元素的指针:

--------     --------       --------
| 5    |     | 3    |     | 6       |
--------     --------      --------
| next | --->| next | --->| nullptr |
--------     --------      --------

  ^
  |
 head

通过存储head指针，我们可以像这样轻松遍历列表:

node *tmp = head; // tmp is our "iterator" through the list
while(tmp != nullptr) 
{
   // Print the data
   cout << tmp->data;

   // Move iterator to the next element
   // Note that when we print the last element,
   // tmp will become nullptr, and the loop will break!
   tmp = tmp->next;
}

I should be more clear with my question. I know that I can manually define each node and initialize them and keep doing that to create a list. But how do I implement a list from the node without specifying what I want each time? I guess what I am getting at is I am unsure how to build a list from the node just given this definition for a node.

有一个巧妙的技巧可以做到这一点 - 您可以将 last 指针保留在某处，并且您可以创建一个辅助函数，例如:

void insert(int data)
{
    node* n = new node(data);

    // If the list is empty:
    if(head == nullptr)
    {
       // This element becomes the first!
       head = n;
    }
    else
    {
       // Append this element to the end of the
       // list
       last->next = n;
    }

    // Update last, as this is the last
    // element in the list
    last = n;
}