双向链表： C++, Python （代码示例）
陈莎拉
什么是双向链表？
在双向链表中，每个节点都链接到上一个节点和下一个节点。每个节点由三个元素组成：一个元素保存数据，另外两个元素是下一个节点和上一个节点的指针。这两个指针帮助我们从特定节点向前或向后移动。
这是双向链表的基本结构。
每个链表都有头节点和尾节点。头节点没有“prev”（上一个指针）节点，尾节点没有“next”节点。
以下是双向链表的一些重要术语：
- 上一篇： 每个节点都与其前一个节点相连。它用作指针或链接。
- 下一篇： 每个节点都链接到其下一个节点。它用作指针或链接。
- 日期： 这用于在节点中存储数据。“数据”可以容纳其他 数据结构 里面。例如，字符串，字典，集合，哈希表等都可以存储在“数据”中。
以下是双向链表中单个节点的基本结构：
Opera双向链表
双向链表的操作包括添加、删除节点，插入、移除节点，以及从上至下遍历链表。
以下是我们可以使用双向链表实现的操作列表：
- 插入前面
- 插入尾部或最后一个节点
- 节点后插入
- 在节点前插入
- 从前面删除
- 从尾部删除
- 搜索并删除节点
- 从头到尾
- 从尾部到头部
我们将看到上述所有操作的实现和伪代码。
在双向链表前面插入
前端插入意味着我们需要在链表中创建一个节点，并将其放在链表的开头。
例如，给定一个节点“15”。我们需要将其添加到头节点。
执行此操作时有两个重要条件：
- 如果双向链表中没有节点，则新节点将成为头节点。
- 如果已经有头节点，则先前的头节点将被新节点替换。
以下是此操作的伪代码：
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
在双向链表末尾插入
“插入到末尾”意味着我们将在链表中创建一个节点并将其放在末尾。
为了实现这一点，我们可以使用两种方法：
- 方法1： 从双向链表的头部开始遍历，直到“next”变为空。然后将新节点与“next”链接起来。
- 方法2： 取双向链表的最后一个节点。然后，最后一个节点的“下一个”节点将链接到新节点。现在，新节点将成为尾节点。
以下是在尾节点插入的伪代码：
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then 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 then List = ListHead.next 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 then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
删除双向链表的头部
双向链表中的头节点没有任何前一个节点。因此，如果我们要删除头节点，下一个指针将是新的头节点。我们还需要在删除节点时释放节点占用的内存。
删除头节点的步骤如下：
步骤1） 将一个变量分配给当前头节点。
步骤2） 访问当前头节点的“下一个”节点，并将“上一个”（上一个指针）节点设为“NULL”。这意味着我们正在断开第二个节点与第一个节点的连接。
步骤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.next ListHead.next = NULL free memory( Tail ) return head
从双向链表中搜索并删除节点
此操作允许我们搜索特定节点数据并删除该节点。我们需要执行线性搜索，因为链表是线性数据结构。删除后，我们还需要释放内存。
以下是在双向链表中查找和删除节点的步骤：
步骤1） 从头部遍历链接列表，直到节点的值等于搜索项。
步骤2） 为匹配的节点分配一个变量“deleteNode”。
步骤3） 将“deleteNode”的前一个节点赋值给下一个节点。
步骤4） 释放“deleteNode”的内存
以下是从链接列表中搜索和删除节点的伪代码：
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
从前向后遍历双向链表
从头节点开始遍历，直到找到“NULL”，遍历每个节点时，可以打印节点的值。从头（正向）遍历的步骤如下：
步骤1） 将指针或变量分配给当前头节点。
步骤2） 迭代到头部的下一个节点，直到得到“NULL”
步骤3） 在每次迭代中打印节点的数据。
步骤4） 返回头节点。
以下是从前面遍历双向链表的伪代码：
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
这里，返回不是强制性的。但操作后返回头节点是一种很好的做法。
从后往前遍历双向链表
这个操作是从前端遍历的逆操作，做法是一样的，只是有一点不同，必须先遍历到尾节点，再从尾节点遍历到前端节点。
以下是从后面遍历双向链表的步骤：
步骤1） 遍历直到到达尾节点。
步骤2） 从尾节点开始，我们将遍历直到前一个节点为“NULL”。 对于头节点，“prev”（上一个指针）将为空
步骤3） 在每次迭代中，我们将打印节点数据。
以下是从后面遍历的伪代码：
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
单链表和双链表的区别
单链表和双链表的主要区别在于链接的数量。
单链表的节点与双链表的节点结构的区别如下：
| 领域 | 单链表 | 双向链表 |
|---|---|---|
| 结构 | 单链表 有一个数据字段和一个到下一个节点的链接。 | 双向链表有一个数据字段和两个链接。一个用于前一个节点，另一个用于下一个节点。 |
| 穿越 | 它只能从头到尾遍历。 | 它可以向前和向后移动。 |
| 内存 | 占用内存较少。 | 它比单链表占用更多的内存。 |
| 无障碍服务 | 单链表效率较低，因为它们仅使用一个链接指向下一个节点。没有指向前一个节点的链接。 | 双向链表比单向链表更有效率。 |
双向链表 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);
}
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 = new 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 = new node();
head = listHead;
cout<<"Traversal from head:\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 = new node();
head = (*listHead);
while(head->next!=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;
return;
}
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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
双向链表 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.insertFront(val)
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:
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 is not 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 is not 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.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is 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))
return
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(1)。
- 搜索节点的时间复杂度为 O(n)。因为搜索项可以位于链表之间的任何位置。此处，“n”是链表中存在的总节点数。
双向链表的最坏情况时间复杂度将与平均情况相同。
双向链表的内存复杂度
内存复杂度为 O(n)，其中“n”是节点总数。在实现链表时，我们必须释放使用的内存。否则，对于较大的链表，它将导致内存泄漏。
总结
- 链表是一种线性数据结构，是以线性方式表示的数据集合。
- 双向链表是一种链表，其中一个节点与前一个节点和下一个节点都有链接。
- 双向链表包含添加节点、删除节点、在另一个节点之后或之前插入一个节点、从头到尾遍历链表的所有操作。
- 双向链表有一个数据字段和两个链接。一个用于前一个节点，另一个用于下一个节点。
- 双向链表的复杂性：最佳情况、平均情况
- 最坏的情况。
