编辑“︁双向链表”︁

{{DISPLAYTITLE:双向链表}}

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

== 基本概念 ==
双向链表的每个节点由三部分组成：
* '''数据域'''：存储节点的值。
* '''前驱指针'''（prev）：指向前一个节点。
* '''后继指针'''（next）：指向后一个节点。

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

=== 节点结构 ===
用伪代码表示双向链表节点的结构如下：
<syntaxhighlight lang="python">
class Node:
    def __init__(self, data):
        self.data = data    # 数据域
        self.prev = None    # 前驱指针
        self.next = None    # 后继指针
</syntaxhighlight>

=== 双向链表结构 ===
双向链表的基本结构可以用以下图示表示：
<mermaid>
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
</mermaid>

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

=== 1. 插入操作 ===
==== 在头部插入 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 在尾部插入 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 在指定位置插入 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

=== 2. 删除操作 ===
==== 删除头部节点 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 删除尾部节点 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 删除指定节点 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

=== 3. 遍历操作 ===
==== 正向遍历 ====
<syntaxhighlight lang="python">
def traverse_forward(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")
</syntaxhighlight>

==== 反向遍历 ====
<syntaxhighlight lang="python">
def traverse_backward(self):
    current = self.tail
    while current:
        print(current.data, end=" -> ")
        current = current.prev
    print("None")
</syntaxhighlight>

== 时间复杂度分析 ==
双向链表的主要操作时间复杂度如下：
* 访问：<math>O(n)</math>（需要从头或尾开始遍历）
* 插入/删除（已知位置）：
  * 头部或尾部：<math>O(1)</math>
  * 中间位置：<math>O(n)</math>（需要遍历到指定位置）
* 搜索：<math>O(n)</math>

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

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]