双向链表

双向链表（Doubly Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据域和两个指针域，分别指向前驱节点（previous）和后继节点（next）。与单向链表相比，双向链表允许双向遍历，因此在某些操作中具有更高的灵活性。

基本概念

双向链表的每个节点由三部分组成：

• 数据域：存储节点的值。
• 前驱指针（prev）：指向前一个节点。
• 后继指针（next）：指向后一个节点。

双向链表的首节点（头节点）的 `prev` 指针为 `null`，尾节点的 `next` 指针为 `null`。

节点结构

用伪代码表示双向链表节点的结构如下：

class Node:
    def __init__(self, data):
        self.data = data    # 数据域
        self.prev = None    # 前驱指针
        self.next = None    # 后继指针

双向链表结构

双向链表的基本结构可以用以下图示表示：

graph LR A[Head] --> B[Node 1] B -->|prev| A B -->|next| C[Node 2] C -->|prev| B C --> D[Tail] D -->|prev| C D -->|next| null

双向链表的操作

双向链表支持以下基本操作：

1. 插入操作

在头部插入

def insert_at_head(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

在尾部插入

def insert_at_tail(self, data):
    new_node = Node(data)
    if self.tail is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

在指定位置插入

def insert_at_position(self, data, position):
    if position == 0:
        self.insert_at_head(data)
        return
    new_node = Node(data)
    current = self.head
    for _ in range(position - 1):
        if current is None:
            raise IndexError("Position out of bounds")
        current = current.next
    if current.next is None:
        self.insert_at_tail(data)
    else:
        new_node.prev = current
        new_node.next = current.next
        current.next.prev = new_node
        current.next = new_node

2. 删除操作

删除头部节点

def delete_at_head(self):
    if self.head is None:
        return
    if self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        self.head = self.head.next
        self.head.prev = None

删除尾部节点

def delete_at_tail(self):
    if self.tail is None:
        return
    if self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        self.tail = self.tail.prev
        self.tail.next = None

删除指定节点

def delete_node(self, data):
    current = self.head
    while current:
        if current.data == data:
            if current.prev:
                current.prev.next = current.next
            else:
                self.head = current.next
            if current.next:
                current.next.prev = current.prev
            else:
                self.tail = current.prev
            return
        current = current.next

3. 遍历操作

正向遍历

def traverse_forward(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

反向遍历

def traverse_backward(self):
    current = self.tail
    while current:
        print(current.data, end=" -> ")
        current = current.prev
    print("None")

时间复杂度分析

双向链表的主要操作时间复杂度如下：

• 访问：$O(n)$（需要从头或尾开始遍历）
• 插入/删除（已知位置）：

 * 头部或尾部：$O(1)$
 * 中间位置：$O(n)$（需要遍历到指定位置）

• 搜索：$O(n)$

实际应用案例

双向链表在以下场景中有广泛应用： 1. 浏览器历史记录：用户可以通过“前进”和“后退”按钮导航，双向链表便于双向遍历。 2. 音乐播放器播放列表：支持上一曲和下一曲功能。 3. 撤销/重做功能（如文本编辑器）：双向链表可以记录操作历史并支持双向操作。

双向链表 vs 单向链表

特性	双向链表	单向链表
指针数量	2（prev + next）	1（next）
内存占用	更高	更低
遍历方向	双向	单向
插入/删除效率	更高（无需临时变量）	较低（需保存前驱节点）

总结

双向链表是一种高效且灵活的数据结构，特别适合需要频繁双向遍历的场景。尽管它比单向链表占用更多内存，但其在插入、删除操作上的优势使其成为许多实际应用的首选。初学者应重点掌握其基本操作（插入、删除、遍历）的实现原理，并通过实际编码练习加深理解。