双向链表： C++, Python (Code 例）
陈莎拉
什么是双向链表？
在双向链表中，每个节点都与前一个节点和后一个节点相连。每个节点由三个元素组成：一个元素存储数据，另外两个元素分别是指向前一个节点和后一个节点的指针。这两个指针用于从特定节点向前或向后移动。
以下是双向链表的基本结构。
双向链表的结构
每个链表都有一个头节点和一个尾节点。头节点没有 上一页 （前一个指针）节点，尾节点没有 下页 节点。
以下是双向链表的一些重要术语：
- 上一篇： 每个节点都与其前一个节点相连。它用作指针或链接。
- 下一篇： 每个节点都链接到其下一个节点。它用作指针或链接。
- 日期： 这是用于在节点中存储数据。数据可以包含其他内容。 数据结构 数据字段中可以存储字符串、字典、集合、哈希表和其他数据结构。
以下是双向链表中单个节点的基本结构：
双向链表中节点的结构
Opera双向链表
双向链表的操作包括添加、删除、插入和移除节点，以及从上到下或从下到上遍历链表。
以下是可以在双向链表上执行的操作列表：
- 插入前面
- 在尾部或最后一个节点插入
- 节点后插入
- 在节点前插入
- 从前面删除
- 从尾部删除
- 搜索并删除节点
- 从头到尾
- 从尾部到头部
下面给出每个操作的实现和伪代码。
在双向链表的前面插入元素
插入到链表前端是指在链表中创建一个节点，并将其放置在链表的开头。
例如，有一个给定的节点 15需要将其添加为头节点。
执行此操作时需满足两个重要条件：
- 如果双向链表为空，则新节点成为头节点。
- 如果已经存在头节点，则将原有的头节点替换为新节点。
以下是该操作的伪代码：
function insertAtFront(ListHead, value): newNode = Node() newNode.value = value ListHead.prev = newNode newNode.next = ListHead newNode.prev = NULL return ListHead
插入前节点
在双向链表的末尾插入元素
在链表末尾插入节点是指在链表中创建一个新节点并将其放置在链表尾部。
有两种方法可以实现此操作：
- 方法1： 从双向链表的头部开始遍历，直到 下页 变为空。然后将新节点与 下页 指针。
- 方法2： 取双向链表的最后一个节点。然后， 下页 最后一个节点的指针指向新节点。新节点成为尾节点。
以下是尾节点插入操作的伪代码：
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
插入到链表末尾
节点后插入
考虑如下所示的现有双向链表：
目标是插入一个给定的节点，该节点将链接到具有特定值的节点之后。 12.
步骤1） 从节点头到节点尾遍历。检查哪个节点具有该值 12.
步骤2） 创建一个新的节点，并将其指定为下一个节点的指针。 12。 该 下页 新节点的节点数为 15。
以下是双向链表中一个节点后插入新节点的伪代码：
function insertAfter(ListHead, searchItem, value): List = ListHead newNode = Node() newNode.value = value while List.value is not equal searchItem: List = List.next newNode.next = List.next newNode.prev = List List.next = newNode
节点后插入
节点前插入
此操作类似于在节点后插入元素。首先搜索特定节点的值，然后创建一个新节点并将其插入到搜索到的节点之前。
要插入给定节点 15 在节点之前 12， 按着这些次序：
步骤1） 从头节点到尾节点遍历链表。
步骤2） 检查当前节点的下一个指针是否具有该值 12.
步骤3） 插入新节点作为 下页 当前节点的节点。
以下是双向链表中一个节点前面插入新节点的伪代码：
function insertBefore(ListHead, searchItem, value): List = ListHead newNode = Node() newNode.value = value while List.next.value is not equal searchItem: List = List.next newNode.next = List.next newNode.prev = List List.next = newNode
在节点前插入节点
删除双向链表的头节点
双向链表中的头节点没有任何前置节点。因此， 下页 当当前头节点被移除时，指针会指向新的头节点。同时，还需要释放被删除节点占用的内存。
以下是删除头节点的步骤：
步骤1） 将一个变量分配给当前头节点。
步骤2） 浏览 下页 当前头节点的节点，并使其 上一页 指针为空。这将断开第二个节点与第一个节点的连接。
步骤3） 释放先前头节点占用的内存。
以下是删除双向链表头节点的伪代码：
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
删除头节点
删除操作后必须释放已分配的内存。否则，被删除的内存块在程序运行期间一直处于占用状态，其他应用程序将无法使用该内存段。
删除双向链表的尾部
此操作类似于删除头部节点，但删除的是尾部节点而不是头部节点。要确定某个节点是否为尾部节点，请检查其指向下一个节点的指针是否为空。删除尾部节点后，必须释放内存。
该手术也称为 从背面删除.
这是执行此操作的步骤：
步骤1） 遍历双向链表直至到达尾节点。
步骤2） 将变量或指针分配给尾节点。
步骤3） 设置 下页 指针指向 NULL 并释放尾节点的内存。
以下是删除尾节点的伪代码：
function deleteTail(ListHead): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead ListHead.prev.next = NULL free memory(Tail) return head
在双向链表中查找并删除节点
此操作查找特定节点值并删除该节点。由于链表是线性数据结构，因此需要进行线性搜索。删除后，必须释放内存。
以下是查找和删除双向链表中节点的步骤：
步骤1） 从链表头开始遍历链表，直到找到与要查找的项值相等的节点。
步骤2） 赋值变量 删除节点 到匹配的节点。
步骤3） 连接前一个节点 删除节点 跳转到下一个节点，并设置下一个节点的 上一页 指向上一个节点的指针。
步骤4） 释放记忆 删除节点.
以下是查找和删除链表中节点的伪代码：
function searchAndDelete(ListHead, searchItem): head = ListHead while head.value not equals searchItem: head = head.next deleteNode = head head.prev.next = head.next if head.next is not NULL: head.next.prev = head.prev free memory(deleteNode) return ListHead
查找和删除操作
从前向遍历双向链表
从头节点开始遍历，直到找到 NULL 值为止。遍历每个节点时，可以打印该值。以下是正向遍历的步骤：
步骤1） 将指针或变量分配给当前头节点。
步骤2） 遍历到头节点的下一个节点，直到得到 NULL 值。
步骤3） 在每次迭代中打印节点数据。
步骤4） 返回头节点。
以下是从链表前端遍历双向链表的伪代码：
function traverseFromFront(ListHead): head = ListHead while head not equals NULL: print head.data head = head.next return ListHead
返回节点并非强制性的。但是，操作完成后返回头节点是一种良好的实践。
从后向后遍历双向链表
此操作是从前端遍历的逆过程。方法基本相同，只有一个小区别：先到达末端节点，然后使用反向路径返回到前端。 上一页 指针。
以下是从链表末尾遍历双向链表的步骤：
步骤1） 遍历直至到达尾节点。
步骤2） 从尾节点开始，遍历 上一页 直到前一个节点为 NULL 为止。 上一页 指向头节点的指针为空。
步骤3） 在每次迭代中，打印节点数据。
以下是从后往前遍历的伪代码：
function traverseFromBack(ListHead): head = ListHead while head.next is not NULL: head = head.next tail = head while tail is not NULL: print tail.value tail = tail.prev return ListHead
单链表和双链表的区别
单链表和双链表的主要区别在于每个节点包含的链接数量。
以下是单链表和双向链表节点之间的区别：
| 领域 | 单链表 | 双向链表 |
|---|---|---|
| 结构 | 单链表 有一个数据字段和一个到下一个节点的链接。 | 双向链表有一个数据字段和两个链接。一个用于前一个节点，另一个用于下一个节点。 |
| 穿越 | 它只能从头到尾遍历。 | 它可以向前和向后移动。 |
| 内存 | 占用内存较少。 | 比单链表占用更多内存。 |
| 无障碍服务 | 单链表效率较低，因为它只使用一条链接指向下一个节点，而没有指向前一个节点的链接。 | 对于双向访问，双向链表比单向链表效率更高。 |
双向链表 C++
以下是完整的 C++ 实现双向链表，支持插入、删除、搜索和遍历操作。
#include<iostream> using namespace std; struct node{ int data; struct node *next; struct node *prev; }; void insertFront(node* &listHead, int value){ node* newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; if(listHead != NULL){ listHead->prev = newNode; newNode->next = listHead; } listHead = newNode; cout<<"Added "<<value<<" at the front"<<endl; } void insertEnd(node* &listHead, int value){ if(listHead == NULL){ insertFront(listHead, value); return; } node* newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node *head = listHead; while(head->next != NULL){ head = head->next; } head->next = newNode; newNode->prev = head; cout<<"Added "<<value<<" at the end"<<endl; } void insertAfter(node* &listHead, int searchValue, int value){ node* newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node *head = listHead; while(head->next != NULL && head->data != searchValue){ head = head->next; } newNode->next = head->next; head->next = newNode; newNode->prev = head; if(newNode->next != NULL){ newNode->next->prev = newNode; } cout<<"Inserted "<<value<<" after node "<<searchValue<<endl; } void insertBefore(node* &listHead, int searchValue, int value){ node* newNode = new node(); newNode->data = value; newNode->prev = NULL; newNode->next = NULL; node *head = listHead; while(head->next != NULL && head->next->data != searchValue){ head = head->next; } newNode->next = head->next; head->next = newNode; newNode->prev = head; if(newNode->next != NULL){ newNode->next->prev = newNode; } cout<<"Inserted "<<value<<" before node "<<searchValue<<endl; } void traverseFromFront(node *listHead){ node* head = listHead; cout<<"Traversal from head:\t"; while(head != NULL){ cout<<head->data<<"\t"; head = head->next; } cout<<endl; } void traverseFromEnd(node *listHead){ node* head = listHead; cout<<"Traversal from tail:\t"; while(head->next != NULL){ head = head->next; } node *tail = head; while(tail != NULL){ cout<<tail->data<<"\t"; tail = tail->prev; } cout<<endl; } void searchAndDelete(node **listHead, int searchItem){ node* head = (*listHead); while(head != NULL && head->data != searchItem){ head = head->next; } if(*listHead == NULL || head == NULL) return; if((*listHead)->data == head->data){ *listHead = head->next; } if(head->next != NULL){ head->next->prev = head->prev; } if(head->prev != NULL){ head->prev->next = head->next; } free(head); cout<<"Deleted Node\t"<<searchItem<<endl; } int main(){ node *head = NULL; insertFront(head, 5); insertFront(head, 6); insertFront(head, 7); insertEnd(head, 9); insertEnd(head, 10); insertAfter(head, 5, 11); insertBefore(head, 5, 20); traverseFromFront(head); traverseFromEnd(head); searchAndDelete(&head, 7); traverseFromFront(head); traverseFromEnd(head); }
输出
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversal from head: 7 6 20 5 11 9 10 Traversal from tail: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from tail: 10 9 11 5 20 6
双向链表 Python
以下是完整的 Python 使用类来表示节点和链表本身，实现双向链表。
class Node: def __init__(self, data=None, prev=None, next=None): self.data = data self.next = next self.prev = prev class DoublyLinkedList: def __init__(self): self.head = None def insertFront(self, val): newNode = Node(data=val) newNode.next = self.head if self.head is not None: self.head.prev = newNode self.head = newNode print("Added {} at the front".format(val)) def insertEnd(self, val): newNode = Node(data=val) if self.head is None: self.head = newNode print("Added {} at the end".format(val)) return temp = self.head while temp.next is not None: temp = temp.next temp.next = newNode newNode.prev = temp print("Added {} at the end".format(val)) def traverseFromFront(self): temp = self.head print("Traversing from head:\t", end="") while temp is not None: print("{}\t".format(temp.data), end="") temp = temp.next print() def traverseFromEnd(self): temp = self.head print("Traversing from tail:\t", end="") while temp.next is not None: temp = temp.next tail = temp while tail is not None: print("{}\t".format(tail.data), end="") tail = tail.prev print() def insertAfter(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode newNode.prev = temp if newNode.next is not None: newNode.next.prev = newNode print("Inserted {} after node {}".format(value, searchItem)) def insertBefore(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.next.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode newNode.prev = temp if newNode.next is not None: newNode.next.prev = newNode print("Inserted {} before node {}".format(value, searchItem)) def searchAndDelete(self, searchItem): temp = self.head while temp is not None and temp.data != searchItem: temp = temp.next if self.head is None or temp is None: return if self.head.data == temp.data: self.head = temp.next if temp.next is not None: temp.next.prev = temp.prev if temp.prev is not None: temp.prev.next = temp.next print("Deleted Node\t{}".format(searchItem)) doublyLinkedList = DoublyLinkedList() doublyLinkedList.insertFront(5) doublyLinkedList.insertFront(6) doublyLinkedList.insertFront(7) doublyLinkedList.insertEnd(9) doublyLinkedList.insertEnd(10) doublyLinkedList.insertAfter(5, 11) doublyLinkedList.insertBefore(5, 20) doublyLinkedList.traverseFromFront() doublyLinkedList.traverseFromEnd() doublyLinkedList.searchAndDelete(7) doublyLinkedList.traverseFromFront() doublyLinkedList.traverseFromEnd()
输出
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversing from head: 7 6 20 5 11 9 10 Traversing from tail: 10 9 11 5 20 6 7 Deleted Node 7 Traversing from head: 6 20 5 11 9 10 Traversing from tail: 10 9 11 5 20 6
双向链表的复杂性
时间复杂度一般分为三种类型：最佳情况、平均情况和最坏情况。
双向链表最佳情况下的时间复杂度：
- 在链表头部或尾部插入元素的时间复杂度为 O(1)，因为无需遍历链表内部。头部指针和尾部指针可以直接访问链表的头部和尾部节点。
- 删除头部或尾部的成本为 O(1)。
- 当目标节点是头节点时，搜索节点的成本为 O(1)。
双向链表的平均时间复杂度：
- 在头部或尾部插入的成本为 O(1)。
- 删除头部或尾部的成本为 O(1)。
- 搜索节点的时间复杂度为 O(n)，因为目标节点可以位于列表中的任何位置。这里， n 是节点总数。
双向链表的最坏情况时间复杂度与平均情况相同。
双向链表的内存复杂度
内存复杂度为 O(n)，其中 n 是节点的总数。在实现链表时，必须释放内存。否则，较大的链表会导致内存泄漏。
双向链表的应用
双向链表为许多现实世界的数据结构提供支持，因为双向遍历简化了许多常见操作。
- LRU缓存： 最近最少使用的缓存使用双向链表和哈希映射来实现 O(1) 的移到前面和驱逐操作。
- 浏览器历史记录： 前后导航功能可以沿链表方向双向遍历。
- 撤销和重做堆栈： 编辑器和集成开发环境 track 个文档版本，带有上一个和下一个指针。
- 德克： Double-端队列可以在 O(1) 时间内从两端进行入队和出队操作。
- 音乐播放列表： 上一页和下一页 track 键依靠前进和后退指针。
