双向链接列表
Harshit Jindal
2023年10月12日
Data Structure
Doubly Linked List
双向链接列表是线性数据结构。它是定义为节点的对象的集合。但是与链接列表不同，该节点有两个指针，一个是前一个指针，另一个是下一个指针。就像链表节点存储在内存中的随机位置中，而不是存储在连续位置中一样。
双向链接列表 vs 链接列表
- 双向链接列表允许我们在向前和向后的方向上遍历链接列表，但这是以
prev指针为每个节点所需的额外空间为代价的。 - 在双向链表中插入元素非常容易，因为我们不必维护多个指针或遍历链表来查找先前的指针，但是与链表相比，我们必须修改更多的指针。
双向链接列表遍历算法
前进方向
令 head 成为链接列表的第一个节点。
-
初始化
curr，指向链接列表的head节点。 -
虽然
curr尚未到达列表的末尾，即curr！=NULL，但请执行以下操作：- 打印存储在当前节点内的数据。
curr=curr->next;- 如果是最后一个节点，则存储为
tail，以方便向后遍历。
同样，我们可以通过从 tail 开始并将 curr 更改为 curr->prev 来进行向后遍历。
反方向
令 tail 为链表的最后一个节点。
-
初始化
curr，指向链接列表的tail节点。 -
虽然
curr尚未到达列表的开头，即curr!=NULL，但请执行以下操作：- 打印存储在当前节点内的数据。
curr = curr->上一个
双向链接列表插入
双向链接列表在插入元素时有 4 种情况，就像链表一样。
将节点插入 DLL push() 的开头
-
使用数据
x和prev创建为NULL的新节点temp。 -
将
temp->next设置为head，将head->prev设置为temp，以在head之前插入temp。 -
将
temp设置为链接列表的开头。
在 Append()DLL 末尾插入节点
-
创建一个新节点
temp，其数据为x，并且其prev为NULL。 -
初始化指向
head的tail。 -
如果链接列表为空，则将
temp设置为链接列表的head，然后返回。 -
否则，迭代链接列表的末尾，使
tail->next！=NULL，以便你到达最后一个元素 -
将
tail->next设置为temp，将temp->prev设置为tail。
在给定节点 insertBefore() 之前插入节点
-
如果
next==NULL，则返回； -
用数据
x创建一个新节点curr。 -
将
curr->prev设置为next->prev，以在next之前添加一个新节点，将next->prev设置为curr，以建立后向链接。 -
将
curr->next设置为next，最后检查curr->prev是否为NULL。 -
如果不是
NULL，则将curr->prev->next设置为curr以完成插入，否则curr是链接列表的第一个节点。将head设置为curr。
在给定节点 insertAfter() 之后插入节点
-
如果
prev==NULL，则返回； -
用数据
x创建一个新节点curr。 -
将
curr->next设置为prev->next，以在prev之后添加一个新节点，并将prev->next设置为curr，以建立前向链接。 -
将
curr->prev设置为prev，最后检查curr->next是否为 NULL。如果不是NULL，则将curr->next->prev设置为curr以完成插入。
双向链接列表插入插图
将节点插入 DLL push() 的开头
在 Append()DLL 末尾插入节点
在给定节点 insertBefore() 之前插入节点
在给定节点 insertAfter() 之后插入节点
双向链接列表遍历和插入实现
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
};
void push(Node** head, int x) {
Node* curr = new Node();
curr->data = x;
curr->next = (*head);
curr->prev = NULL;
if ((*head) != NULL) (*head)->prev = curr;
(*head) = curr;
}
void insertAfter(Node* prev, int x) {
if (prev == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
Node* curr = new Node();
curr->data = x;
curr->next = prev->next;
prev->next = curr;
curr->prev = prev;
if (curr->next != NULL) curr->next->prev = curr;
}
void insertBefore(struct Node** head, struct Node* next, int x) {
if (next == NULL) {
return;
}
Node* curr = new Node();
curr->data = x;
curr->prev = next->prev;
next->prev = curr;
curr->next = next;
if (curr->prev != NULL)
curr->prev->next = curr;
else
(*head) = curr;
}
void append(Node** head, int x) {
Node* curr = new Node();
Node* tail = *head;
curr->data = x;
curr->next = NULL;
if (*head == NULL) {
curr->prev = NULL;
*head = curr;
return;
}
while (tail->next != NULL) tail = tail->next;
tail->next = curr;
curr->prev = tail;
return;
}
void printList(Node* node) {
Node* tail = NULL;
cout << "Forward Traversal:";
while (node != NULL) {
cout << " " << node->data << " ";
tail = node;
node = node->next;
}
cout << "\nReverse Traversal:";
while (tail != NULL) {
cout << " " << tail->data << " ";
tail = tail->prev;
}
cout << "\n";
}
int main() {
Node* head = NULL;
append(&head, 6);
push(&head, 7);
push(&head, 1);
append(&head, 4);
printList(head);
insertAfter(head->next, 8);
insertBefore(&head, head->next->next, 3);
printList(head);
return 0;
}
双向链接列表遍历和插入算法的复杂性
遍历
时间复杂度
- 平均情况
要遍历完整的双向链表，我们必须访问每个节点。因此，如果它具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。
- 最佳情况
最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。
- 最坏情况
最差的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。
空间复杂度
遍历算法的空间复杂度为 O(1)，因为除 curr 指针外不需要其他空间。
插入方式
时间复杂度
- 平均情况
在所有 4 情况下插入一个元素最多需要 4 链接更改，因此插入的时间复杂度为 O(1)。
- 最佳情况
最佳情况下的时间复杂度是 O(1)。它与平均情况下的时间复杂度相同。
- 最坏情况
最坏情况下的时间复杂度是 O(1)。它与最佳情况下的时间复杂度相同。
空间复杂度
对于所有 4 种插入方式，插入算法的空间复杂度为 O(1)。
Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe
作者： 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