企业官网建设流程全解析

前言

链表（linked list）是数据结构课的基础内容。它由一个个节点（node）串成，每个节点存一份数据，再存一个指向下一个节点的引用。双向链表（doubly linked list）在此基础上多存一个prev指针，指向前一个节点——这是它和单向链表最大的区别，也是它全部便利与代价的来源。

先说清一条边界：双向链表和单向循环链表常被混为一谈，但它们回答的是两个不同的问题。单向循环链表里每个节点只有一个next，尾节点指回头节点形成环；双向链表多一个prev指针，因此可以从任意节点向前走。至于「是否成环」，那是另一个独立的设计选择——本文实现的是带哨兵的双向非循环链表。读者若把两者混为一谈，会觉得「为什么这里要多维护一个指针」，所以先把边界划清。

本文用 Python 类实现一个功能完整的DoublyLinkedList，讲清三个关键点：哨兵节点（sentinel）怎么消掉边界判断、插入和删除时指针该按什么顺序改、以及多维护一个prev带来的便利与代价。示例以 Python 3.8 为基准，逐行推演过逻辑，但请注意本机没有解释器，代码未实际运行。

一、节点长什么样

一个双向链表节点需要三个属性：数据、前驱、后继。

# 适用于 Python 3.8+
class Node:
__slots__ = ("value", "prev", "next")

def __init__(self, value, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next

def __repr__(self):
return f"Node({self.value!r})"

用__slots__是为了限制属性、省一点内存，这不是必需的。next属性和内置函数next()同名，在类内部用self.next访问没有冲突，但如果你在方法里既要用next(iter)又要用self.next，读起来会绕，介意的话可以改叫nxt。本文统一用next。

二、哨兵节点：消掉「头尾特判」

不用哨兵时，每次插入删除都要判断「是不是在头部」「是不是在尾部」「链表是不是空的」，分支特别多，也容易漏。

哨兵节点的思路是：建两个不存数据的假节点——一个head（头哨兵）、一个tail（尾哨兵）。真实的第一个节点永远在head.next，最后一个永远在tail.prev。空链表就是head.next is tail、tail.prev is head。这样任何位置的插入删除都变成同一套指针操作，不用再特判首尾。

# 适用于 Python 3.8+
class DoublyLinkedList:
def __init__(self):
self.head = Node(None) # 头哨兵，不存数据
self.tail = Node(None) # 尾哨兵，不存数据
self.head.next = self.tail # 空链表：哨兵互指
self.tail.prev = self.head
self.size = 0

def __len__(self):
return self.size

def is_empty(self):
return self.size == 0

图示（H、T是哨兵）：

H <-> (真节点1) <-> (真节点2) <-> T

空链表时：

H <-> T

三、在任意节点之前插入

先写一个底层方法_insert_before(node, value)，把「新建节点并挂到node前面」的指针操作封装起来。

指针顺序很重要。设要在node前面插入new，原来node.prev是p：

# 适用于 Python 3.8+
def _insert_before(self, node, value):
p = node.prev # 原前驱
new = Node(value, prev=p, next=node)
p.next = new # ① 前驱指向新节点
node.prev = new # ② 目标节点回指新节点
self.size += 1
return new

顺序为什么不能颠倒：必须先用p = node.prev把原前驱存下来，再去改p.next；如果先写node.prev = new，就再也找不到原来的前驱p了。记住一句口诀——先存旧指针，再改新指针。这里 ①② 两行之间其实没有依赖，但都必须在p取出来之后执行。

有了它，几个常用操作就是一行：

# 适用于 Python 3.8+
def append(self, value): # 追加到末尾
return self._insert_before(self.tail, value)

def prepend(self, value): # 插到开头
return self._insert_before(self.head.next, value)

注意append插在尾哨兵之前，prepend插在头哨兵的后继之前——完全对称，没有一个特判分支。这正是哨兵的价值。

四、删除节点

双向链表删除一个已知节点非常方便，因为能直接拿到它的前驱：把前驱的后继指向后继，把后继的前驱指向前驱即可。

# 适用于 Python 3.8+
def _unlink(self, node):
node.prev.next = node.next # ① 前驱跳过自己
node.next.prev = node.prev # ② 后继跳过自己
node.prev = node.next = None # ③ 断开自己的指针（可选，帮 GC）
self.size -= 1
return node.value

def pop_front(self):
if self.is_empty():
raise IndexError("pop from empty list")
return self._unlink(self.head.next)

def pop_back(self):
if self.is_empty():
raise IndexError("pop from empty list")
return self._unlink(self.tail.prev)

_unlink的 ①② 两行必须先做，不能先做 ③：如果先把node.prev设成None，第 ② 行里node.prev就取不到真前驱了，链会断。

顺便对比单向链表：单向链表要在尾部删除，必须从头部一路走到倒数第二个节点，是 O(n)；而双向链表因为尾哨兵有prev，pop_back是 O(1)。这就是多存一个prev的直接收益。

五、查找与遍历

查找需要从某个方向逐个走：

# 适用于 Python 3.8+
def find(self, value):
cur = self.head.next
while cur is not self.tail:
if cur.value == value:
return cur
cur = cur.next
return None

def to_list(self):
out = []
cur = self.head.next
while cur is not self.tail:
out.append(cur.value)
cur = cur.next
return out

def to_list_reversed(self):
out = []
cur = self.tail.prev # 从尾部往前走，靠的就是 prev
while cur is not self.head:
out.append(cur.value)
cur = cur.prev
return out

to_list_reversed正是双向链表独有的便利：单向链表做不到从尾部往头部走。

六、串起来跑一遍

# 适用于 Python 3.8+
if __name__ == "__main__":
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)
print(dll.to_list()) # [0, 1, 2, 3]
print(dll.to_list_reversed()) # [3, 2, 1, 0]

print(dll.pop_back()) # 3
print(dll.pop_front()) # 0
print(dll.to_list()) # [1, 2]
print(len(dll)) # 2

常见坑点

坑一：插入时先改目标再存旧指针，导致链断裂。

# 适用于 Python 3.8+
# ❌ 先覆盖 node.prev，就丢了原前驱
def _insert_before_bad(self, node, value):
node.prev = Node(value, prev=node.prev, next=node)
node.prev.prev.next = node.prev # 逻辑已乱，易出错
# ✅ 先取出原前驱，再挂接
def _insert_before(self, node, value):
p = node.prev
new = Node(value, prev=p, next=node)
p.next = new
node.prev = new

坑二：删除时先断开自身指针。

# 适用于 Python 3.8+
# ❌ 先清空 node.prev，后面就用不上了
node.prev = None
node.prev.next = node.next # AttributeError: 'NoneType'
# ✅ 先让邻居互指，最后再清自己
node.prev.next = node.next
node.next.prev = node.prev
node.prev = node.next = None

坑三：忘了维护size。

# 适用于 Python 3.8+
# ❌ 插入里写了 self.size += 1，删除的 _unlink 里却忘了 self.size -= 1
# 结果 len(dll) 只会越来越大，和真实节点数对不上
# ✅ 增删各维护一次，成对出现
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1 # 这一步千万别漏

坑四：空链表上用哨兵直接取数据。

# 适用于 Python 3.8+
# ❌ 直接返回哨兵指向的节点的值，空链表时会取到哨兵
def pop_front_bad(self):
return self._unlink(self.head.next) # 空表时删掉了尾哨兵
# ✅ 先判空
def pop_front(self):
if self.is_empty():
raise IndexError("pop from empty list")
return self._unlink(self.head.next)

坑五：遍历时用while cur:判结束。

# 适用于 Python 3.8+
# ❌ 哨兵节点本身是真值对象，while cur 永远成立，死循环
cur = self.head.next
while cur:
cur = cur.next
# ✅ 用「是否到达尾哨兵」判断
while cur is not self.tail:
cur = cur.next

坑六：__slots__里漏写了属性。

# 适用于 Python 3.8+
# ❌ 类里声明了 __slots__ 但没包含 prev，赋值报错
class Node:
__slots__ = ("value", "next")
def __init__(self, value, prev=None, next=None):
self.prev = prev # AttributeError
# ✅ __slots__ 里把用到的属性都列上
class Node:
__slots__ = ("value", "prev", "next")

坑七：把哨兵节点当普通节点算进长度。

# 适用于 Python 3.8+
# ❌ 以为 len() 的结果里含两个哨兵，手动减 2，反而少算了两个
print(len(dll) - 2)
# ✅ size 只统计真实节点，两个哨兵不计入
print(len(dll))

总结

双向链表的核心是那个多出来的prev指针：它让「删尾」「已知节点删除」「反向遍历」都变成 O(1) 或直接可行，代价是每次插入删除都要多维护一根指针、每个节点多一份内存开销。配上头尾两个哨兵，首尾的特判全部消失，代码会干净很多。真正要牢记的只有两条指针顺序口诀：插入时先存旧指针再改新指针，删除时先接好邻居再断开自己。