双向链接列表
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