链表 - 使用后指针在末尾插入

Question

我正在学习链表插入并遇到以下代码以在链表的末尾插入一个节点（在一本相当古老且过时的 C++ 书籍中仍然使用我不知道为什么）：

void Insert_End(Node * np){
    if (start == NULL){
        start = rear = np;
    }
    else{
        rear -> next = np;
        rear = np;
    }
}

我的问题是不应该 np -> next = rear;

PS : np 是最后插入的新节点，rear 指向最后一个节点，start 指向第一个节点。

Answer 1

My question is shouldn't it be np -> next = rear;

不，因为没有节点会指向 np，因此它不会成为任何列表的一部分（头部为 np 的列表除外）。此外，np 不会在后面，因为它的 next 会指向一个节点（之前是 rear 的节点）。该示例是正确的实现。

Answer 2

My question is shouldn't it be np -> next = rear;

不对，下面的图片可以帮助您轻松理解。

当您第一次执行 start = rear = np; 时，所有 3 个节点可能如下所示。

  ------
  |  np  |
   ------
  ^      ^
  |       |
 ----      ----
|start|   | rear|
 ----      ----

连续插入：

当您执行 rear -> next = np; 时，您的列表可能如下所示。

注意：rear 仍然指向列表的前一个最后一个节点，np1 指向 np2.

  ------         -----
  |  np1 | ---> | np2 |
   ------        -----
  ^       ^
  |       |
 ----      ----
|start|   | rear|
 ----      ----

当您执行 rear = np; 时，您的 rear 会更新为指向当前最后一个节点。

  ------         -----
  |  np1 | ---> | np2 |
   ------        -----
  ^              ^
  |              |
 ----           ----
|start|        | rear|
 ----           ----

链表 - 使用后指针在末尾插入

Linked list - Insert at end using a rear pointer

c

c++

linked-list

singly-linked-list