理解 C++ 中的链表

Question

我正在尝试理解链表的概念。到目前为止，这是我所知道的以及我在理解方面遇到问题的地方。

//create node
struct list
{
int id; //member var
list* next; //pointer to link next list item
}

//int main()

//create list head and set it to NULL
list* head = NULL;

//instantiate list node
list* newList = new list;

//insert a list
newList->id = 20;
newList->next = NULL;

这个我不太明白是怎么回事

newList->next = head;
head = newList;

Answer 1

newList->next = head;
head = newList;

您开始时 head 设置为 NULL。
然后，你创建一个新节点，让它的 next 指向 head，也就是 NULL。
然后，您将 head 设置为新节点。现在，head 指向一个包含一项的列表。

Answer 2

注意： 我将在这个答案中引用的内存 "locations" 是否纯粹是为了模仿这些指针可能或可能永远不会的实际位置指向.

在纸上画出这些关系以可视化结果。让我们按行分解。

list *head = NULL;

这是我们的可视化：

 *head (0x00)
+-----------+
|           |
|   NULL    |
|           |
+-----------+

现在，我们遵循以下几行：

list *newList = new list;
newList->id = 20;
newList->next = NULL;

那个可视化：

 *head (0x00)      *newList (0x3a)
+-----------+     +----+------+
|           |     | id | next |
|   NULL    |     +----+------+
|           |     | 20 | NULL |
+-----------+     +----+------+

最后我们以您的最后一点结束：

newList->next = head;

因此改变了可视化（为清楚起见重新排序）：

 *newList (0x3a) +->*head (0x00)
+----+------+    | +-----------+
| id | next |    | |           |
+----+------+    | |   NULL    |
| 20 | head------+ |           |
+----+------+      +-----------+

这已经创建了 "link" 给 LinkedList 命名。您 link 节点通过某种形式的引用组合在一起。所以你所做的是创建一个 "head" 或列表的开头，然后你在列表中创建了一个辅助节点并将它（逻辑上）放在 head 之前。通常，您随后会将对 newList 的引用重新分配给 head，因为它是列表的新开头。

下一步可能是（我确定这就是我在这个问题末尾询问的错误位的意思）：

head = newList;

现在将可视化更改为：

 *head (0x3a)  +---> (0x00)
+----+------+  |   +-----------+
| id | next |  |   |           |
+----+------+  |   |   NULL    |
| 20 | 0x00----+   |           |
+----+------+      +-----------+

此外，下面一行呢？

head = n; // What is 'n'? Where did you get it from? It doesn't appear anywhere else in your sample

编辑

我更改了可视化以更准确地反映现实情况。当我发布原始答案时，我没有注意我在做什么，非常感谢 José 和他的评论让我注意到可视化是不准确的。

除了更改视觉效果之外，我还添加了更多信息，并希望更进一步说明您将如何使用此 linked 列表循环遍历其记录。

list *node = head;
while (node != NULL) {
    std::cout << "The id is " << node->id << std::endl;
    node = node->next;
}

理解 C++ 中的链表

Understanding Linked List in C++

c++

linked-list