链表插入
Harshit Jindal
2024年2月15日
在本文中，我们将学习如何在链表中插入节点。我们可以看到出现了 4 种不同的情况。
- 我们要在链接列表的开头之前插入一个节点。此操作类似于堆栈中的推入操作。
- 我们要在链接列表的末尾（即尾节点旁边）插入一个节点。
- 我们想在链接列表的第 i 个位置插入一个节点。
- 我们有该节点的引用，之后我们要插入新节点。
链表插入算法
令 head 为指向链表第一个节点的指针，令 x 为要插入链表中的数据。
在链接列表 push() 的开头插入节点
-
用数据
x创建一个新节点temp。 -
将
temp->next设置为head，以在head之前插入temp。 -
将
temp设置为链接列表的开头。
在链接列表 append() 的末尾插入节点
-
用数据
x创建一个新节点temp。 -
初始化指向
head的tail。 -
如果链接列表为空，则将
temp设置为链接列表的head，然后返回。 -
否则，迭代链接列表的末尾，使
tail->next！=NULL，以便你到达最后一个元素 -
将
tail->next设置为temp。
在链接列表 insertNpos() 的 i-th 位置处插入节点
-
如果位置
pos<=0，则返回；否则返回 0。 -
如果
pos==0并且head为空，则创建一个数据为x的新节点并将其设置为head。 -
如果
pos==1，则调用push()。 -
另外，用数据
x创建一个新节点temp。 -
初始化指向
head的curr。 -
当
pos--时，执行以下操作。-
如果
pos==1，- 如果
curr不是NULL- 将
temp->next设置为curr->next，以便在curr之后插入temp。 - 将
curr->next设置为temp，以将curr连接到temp。
- 将
- 返回;
- 如果
-
否则将
curr设置为curr->next。
-
在给定节点的引用旁边插入节点 - insertAfter()
-
如果
prev==NULL，则返回； -
用数据
x创建一个新节点curr。 -
将
curr->next指向prev->next以在 prev 之后添加新节点。 -
将
prev->next指向curr以完成插入。
链表插入图
假设我们有一个节点 temp，其数据值等于 5，我们想将其插入链表中。让我们考虑所有 4 种情况，并说明上述算法是如何工作的。
在链接列表的开头插入节点 - push()
-
将
temp的指针设置为head。 -
将
head指向temp。
在链接列表 append() 的末尾插入节点
-
将
curr指向head，数据为2。 -
将
curr设置为curr->next，并将其移动到数据为3的节点。 -
将
curr设置为curr->next，并将其移动到数据为4的节点。 -
退出 while 循环并将
curr->next设置为temp。
在链接列表的 i-th 位置处插入节点 - insertNpos()
我们将节点插入到位置 3。
-
将
curr指向head，数据为1，pos=pos-1=2。 -
将
curr设置为curr->next，并将其移动到数据为3，pos=pos -1=1的节点。 -
将
temp->next设置为curr->next，以便在curr之后插入 temp。 -
将
curr->next设置为temp，以在curr和curr->next之间完成temp的插入。
在给定节点 insertAfter() 的引用旁边插入节点
-
将
temp->next设置为prev->next，以在prev和prev->next之间插入temp。 -
将
prev->next设置为temp以完成插入。
链表插入实现
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};
void push(Node** head, int x) {
Node* temp = new Node(x);
temp->next = (*head);
(*head) = temp;
}
void insertAfter(Node* prev, int x) {
if (prev == NULL) {
return;
}
Node* curr = new Node(x);
curr->next = prev->next;
prev->next = curr;
}
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
}
void insertNpos(Node** head, int x, int pos) {
if (pos <= 0) {
return;
}
if (!head && pos == 1) {
*head = new Node(x);
} else if (pos == 1) {
push(head, x);
}
Node* temp = new Node(x);
Node* curr = *head;
while (pos--) {
if (pos == 1) {
if (curr) {
temp->next = curr->next;
curr->next = temp;
}
return;
}
curr = curr->next;
}
}
void append(Node** head, int x) {
Node* temp = new Node(x);
Node* tail = *head;
if (*head == NULL) {
*head = temp;
return;
}
while (tail->next != NULL) tail = tail->next;
tail->next = temp;
return;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
printList(head);
cout << "\n";
push(&head, 3);
push(&head, 4);
printList(head);
cout << "\n";
append(&head, 5);
printList(head);
cout << "\n";
insertAfter(head->next->next, 6);
printList(head);
cout << "\n";
insertNpos(&head, 24, 2);
printList(head);
return 0;
}
链表插入算法的复杂度
时间复杂度
- 平均情况
要将节点插入链表中的第 i 个位置，我们必须访问 i 个节点。因此，时间复杂度约为 O(i)。而且我们在链表中有 n 个节点，因此平均情况下的时间复杂度为 O(n/2) 或 O(n)。时间复杂度约为 O(n)。
- 最佳情况
最好的情况是，当我们想在链表的开头插入一个节点，或者在插入站点之前有对该节点的引用时。最佳情况下的时间复杂度是 O(1)。
- 最坏情况
最差的时间复杂度是 O(n)。这与平均情况下的时间复杂度相同。
空间复杂度
该插入算法的空间复杂度为 O(1)，因为除 curr 指针外不需要其他空间。
作者： Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn