c++ - 理解 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

注意:我将在这个答案中引用的内存“位置”纯粹是为了模拟这些指针可能指向或可能永远不会指向的实际位置。

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

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------+ |           |
+----+------+      +-----------+

这已经创建了一个“链接”，它给一个 LinkedList 它的名字。您通过某种形式的引用将节点链接在一起。所以你所做的是创建一个“头部”或列表的开头，然后你在列表中创建了一个辅助节点并将它(逻辑上)放在头部之前。通常，您随后会将对 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

编辑

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

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

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