链表：为什么通过将新节点添加到 head->next 来扩展单节点列表，而不是 head=head->next 然后添加到 head

Question

一个简单的链表代码：

#include<iostream>

struct node {
  int    data;
  node*  next;
};

int main() {
  node *head, *head1;
  head = new node;
  head1 = head; //we'll use head1 to print the entire list at the end

  head->data =  2;

以下代码块（已注释掉）不会将新节点添加到列表中

  /* head = head->next;
  head = new node;
  head -> data = 20;*/

但是下面的（看似相似）方法是有效的，我们最后打印整个列表

  head->next = new node; 
  head = head->next; 
  head->data = 20;
  
  while (head1 != nullptr) {
    std::cout<<head1->data<<std::endl;
    head1 = head1->next;
  }
}

由于head和head->next都是node*类型，如何理解

head->next = new node;

有效，但

head = head->next; head=new node;

无效

Answer 1

显示的代码有效。

如果你尝试

head = head->next; head=new node;

它将失败，因为此时

head->next

为空，所以现在

head

为空。您可以为其分配一个新节点，但这不会影响

next

先前指向的对象的

head

成员。

事情是这样开始的：

+----------+
| *head    |
+----------+
     |
     |
     V
+----------+               +--------+
| node     |<--------------| *head1 |
| -------- |               +--------+
| data = 2 |       ??????
| *next ---------->?????? 
+----------+       ??????

现在，如果我们尝试您所问的问题，我们最终会得到：

+----------+               +--------+
| node     |<--------------| *head1 |
| -------- |               +--------+
| data = 2 |       ??????
| *next ---------->?????? 
+----------+       ??????

+----------+
| *head    |
+----------+
     |
     |
     V
+-----------+             
| node      |
| --------- |           
| data = 20 |      ??????
| *next ---------->?????? 
+-----------+      ??????

请注意，

head1

仍然指向包含值

2

的原始节点，但没有任何东西将该节点链接到包含值

20

的节点。

Answer 2

  head = head->next; 
  head = new node; 
  head -> data = 20;

此代码不会添加新节点，因为一旦我们执行

head = head->next

，现在

head

就指向

NULL

。现在我们已经创建了一个新节点，但之前的节点仍然仅指向

NULL

。为了测试这一点，我们可以在执行

temp

之前将 head 临时存储在

head = head->next

节点中，并在分配完成后打印

temp->next

。您仍会将

temp->next

视为

NULL

。

为了避免这种行为，我们首先创建一个节点，然后将其分配给

head->next

。

Answer 3

如何理解

head->next = new node;

有效，但

head = head->next; head=new node;

无效？

更改变量

head

的值不会改变

head1->next

。这也是为什么

head = head->next;

不会神奇地将

head1

更新为相同的原因。

这可能有助于想象发生了什么。当你的 main 函数执行完毕后

head->data =  2;

我们会遇到这样的情况：

      ┌─[node*]─┐    ┌─[node]───────────┐
head1:│     ────────►│       ┌─[int]───┐│
      └─────────┘    │ data: │  2      ││
                     │       └─────────┘│ 
      ┌─[node*]─┐    │       ┌─[node*]─┐│
head: │     ────────►│ next: │  ─────────────► (undefined)
      └─────────┘    │       └─────────┘│  
                     └──────────────────┘

head->next

中的值未定义：它可能是

NULL

，也可能是未分配内存的地址，或者是为其他内容分配的内存地址，...等等。这是未定义的。

执行

head = head->next;

后，我们有这个：

      ┌─[node*]─┐    ┌─[node]───────────┐
head1:│     ────────►│       ┌─[int]───┐│
      └─────────┘    │ data: │  2      ││
                     │       └─────────┘│ 
      ┌─[node*]─┐    │       ┌─[node*]─┐│
head: │     ──────┐  │ next: │  ─────────────► (undefined)
      └─────────┘ │  │       └─────────┘│  ┌─►  
                  │  └──────────────────┘  │
                  └────────────────────────┘

所以

head

现在有一个未定义的值——与

head1->next

指针相同的未定义值。

这里的一些观察：

• 无法继续使用相同的未定义地址并在那里分配节点。 new node 将分配内存并返回一个指向它的（新的）指针。如果你给
head
• 赋值，它不会改变

  head1->next

  中的指针值。如果您将某些内容分配给

  head1->next

  ，它不会更改

  head

  的指针值：它们是单独的指针，当前恰好指向同一个未定义的点。
因此，当您现在执行

head = new node

（和

head->data = 20

）时，我们会得到：

      ┌─[node*]─┐    ┌─[node]───────────┐
head1:│     ────────►│       ┌─[int]───┐│
      └─────────┘    │ data: │  2      ││
                     │       └─────────┘│ 
      ┌─[node*]─┐    │       ┌─[node*]─┐│
head: │     ──────┐  │ next: │  ─────────────► (undefined)
      └─────────┘ │  │       └─────────┘│  
                  │  └──────────────────┘
                  │  ┌─[node]───────────┐
                  └─►│       ┌─[int]───┐│
                     │ data: │  20     ││
                     │       └─────────┘│ 
                     │       ┌─[node*]─┐│
                     │ next: │  ─────────────► (undefined)
                     │       └─────────┘│
                     └──────────────────┘

如您所见，

head1->next

什么也没发生。现在您有两个单独的链表，它们的最后一个（也是唯一的）节点中都有一个未定义的指针。这意味着使用

while

循环对任一列表进行迭代都将导致未定义的行为，并且可能会导致错误。

Answer 4

使用 C++

。只是在一两个地方将 malloc 更改为

new

并不能给你真正的 C++。我首先将

ctor

添加到

node

结构中：

struct node {
  int    data;
  node*  next;

  node(int data = 0, node *next = nullptr) 
    : data(data), next(next) 
  { }    
};

这样，在链表头部插入一个新节点就是：

// our head pointer:
node *head = nullptr;

// Insert a new node with the value 1 at the head of the list:
head = new node(1, head);

用户不应该直接处理这个问题。我们想要一个他们可以干净使用的界面。

class linked_list {

    struct node {
        int data;
        node *next;

        node(int data = 0, node *next = nullptr) : data(data), next(next)
        { }
    };

    node *head = nullptr;
    node *tail = nullptr;
public:
    // add a new node at the front of the list:
    void add_head(int new_value) {
        // add new node before head.
        head = new node(new_value, head);
        // if this is the first node in the list, it's also the tail:
        if (head->next == nullptr)
            tail = head;
    }

    // add a new node at the tail of the list:
    void add_tail(int new_value) {
        // if the list is empty, adding at the tail is the same as
        // adding at the head:
        if (tail == nullptr)
            add_head(new_value);
        // otherwise, add the new node after the current tail
        // and update tail to point to the new node:
        else {
            tail->next = new node(new_value, nullptr);
            tail = tail->next;
        }
    }

    void show() {
        for (node *current = head; current; current = current->next)
            std::cout << current->data << "\n";
    }
};

类的大部分想法是提供一个相对抽象、易于使用的接口，保护它们免受遍历列表、正确插入节点、确保它始终保持正确的链表等丑陋细节的影响。

int main() {
    linked_list ll;

    ll.add_head(2);
    ll.add_tail(20);
    ll.show();
}