链表插入
Harshit Jindal
2023年1月30日
2021年3月21日
在本文中,我们将学习如何在链表中插入节点。我们可以看到出现了 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
指针外不需要其他空间。
Author: 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