我们在上一篇文章中介绍了链表。还创建了一个具有 3 个节点的简单链表并讨论了链表遍历。 本文中讨论的所有程序都考虑以下链表表示。
// 一个链表节点 class Node { public: int data; Node *next; };
在这篇文章中，讨论了在链表中插入新节点的方法。可以通过三种方式添加节点
1) 在链表的前面
2) 在给定节点之后。
3) 在链表的末尾。
在前面添加一个节点：（4 步过程）
新节点总是添加在给定链表的头部之前。并且新添加的节点成为链表的新头。例如，如果给定的链表是 10->15->20->25 并且我们在前面添加了一个项目 5，那么链表就变成了 5->10->15->20->25。让我们调用添加在列表前面的函数是 push()。push() 必须接收一个指向头指针的指针，因为 push 必须将头指针更改为指向新节点
以下是在前面添加节点的 4 个步骤。
/* 给定一个指向列表头部的引用（指向指针的指针）和一个 int，在列表的前面插入一个新节点。 */ void push(Node** head_ref, int new_data) { /* 1. 分配节点 */ Node* new_node = new Node(); /* 2. 放入数据 */ new_node->data = new_data; /* 3. 将新节点的下一个作为头 */ new_node->next = (*head_ref); /* 4. 移动头部指向新节点 */ (*head_ref) = new_node; }
push() 的时间复杂度是 O(1)，因为它做的工作量是恒定的。
在给定节点之后添加一个节点：（5 个步骤过程）
我们得到一个指向节点的指针，在给定节点之后插入新节点。
// 给定一个节点 prev_node，在给定的 prev_node 后面插入一个新节点 void insertAfter(Node* prev_node, int new_data) { // 1. 检查给定的 prev_node 是否为 NULL if (prev_node == NULL) { cout << "给定的前一个节点不能为 NULL"; return; } // 2. 分配新节点 Node* new_node = new Node(); // 3.放入数据 new_node->data = new_data; // 4. 将新节点的下一个设为 prev_node 的下一个 new_node->next = prev_node->next; // 5.将 prev_node 的下一个移动为 new_node prev_node->next = new_node; }
insertAfter() 的时间复杂度是 O(1)，因为它做的工作量是恒定的。
最后添加一个节点：（6 步过程）
新节点总是添加在给定链表的最后一个节点之后。例如，如果给定的链表是 5->10->15->20->25 并且我们在最后添加了一个项目 30，那么链表变成了 5->10->15->20->25- > 30。
由于链表通常由它的头部表示，我们必须遍历链表直到最后，然后将倒数第二个节点更改为新节点。
以下是最后添加节点的 6 个步骤。
c++
复制代码
// 给定一个指向列表头部的引用（指向指针的指针）和一个 int，在末尾附加一个新节点 void append(Node** head_ref, int new_data) { // 1. 分配节点 Node* new_node = new Node(); //在步骤 5 中使用 Node *last = *head_ref; // 2. 放入数据 new_node->data = new_data; // 3. 这个新节点将是最后一个节点，所以将它的 next 设为 NULL new_node->next = NULL; // 4. 如果链表为空，则以新节点为头 if (*head_ref == NULL) { *head_ref = new_node; return; } // 5. else 遍历到最后一个节点 while (last->next != NULL) last = last->next; // 6. 更改最后一个节点的下一个 last->next = new_node; return; }
append 的时间复杂度为 O(n)，其中 n 是链表中的节点数。由于从头到尾有一个循环，该函数执行 O(n) 工作。
通过保留一个指向链表尾部的额外指针/
下面是一个完整的程序，它使用上述所有方法来创建一个链表。
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *next; }; void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void insertAfter(Node* prev_node, int new_data) { if (prev_node == NULL) { cout<<"给定的前一个节点不能为 NULL"; return; } Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void append(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void printList(Node *node) { while (node != NULL) { cout<<" "<<node->data; node = node->next; } } int main() { Node* head = NULL; append(&head, 6); push(&head, 7); push(&head, 1); append(&head, 4); insertAfter(head->next, 8); cout<<"创建的链表是："; printList(head); return 0; }
输出：
创建的链表是：1 7 8 6 4
