双向链表实现栈：原理、代码与性能分析

1. 为什么用双向链表实现栈

栈这个数据结构，几乎每个写过代码的人都用过。后进先出，push 进去，pop 出来，简单直接。大多数场景下，数组或者动态数组就足够应付了，Python 里一个 list 加 append/pop 就能跑，C++ 里 std::vector 也能凑合。但如果你真的动手用双向链表去实现一个栈，会发现这里面有不少值得聊的东西。

我先说结论：用双向链表实现栈，核心价值不在于性能比数组好，而在于它天然支持 O(1) 的栈顶操作，同时不需要像数组那样考虑扩容和缩容时的数据搬移。数组实现栈，push 的时候如果容量满了，得申请一块更大的内存，把旧数据全部拷过去，这个操作是 O(n) 的。虽然均摊下来还是 O(1)，但单次操作会有毛刺。双向链表不存在这个问题，每次 push 就是新建一个节点，挂上去，完事。

那为什么是双向链表而不是单向链表？单向链表实现栈，push 和 pop 都在头部操作，其实也够了。但双向链表多了一个指向前驱的指针，在某些场景下会带来额外的便利。比如你想在栈顶之外，还能从栈底方向做一些操作，或者你想实现一个“双端栈”，两端都能 push 和 pop，双向链表就更自然。另外，双向链表在删除节点时，不需要像单向链表那样从头遍历去找前驱，直接通过 prev 指针就能拿到，删除操作更干净。

这篇文章我会从零开始，把双向链表实现栈的完整思路、代码细节、边界条件、常见坑点全部拆开讲一遍。适合已经了解栈的基本概念、想深入理解底层实现的人，也适合正在准备面试、需要手写数据结构的人。代码我会用 Python 和 C 两个版本对照，Python 方便理解逻辑，C 方便理解内存层面的操作。

2. 双向链表与栈的核心概念拆解

2.1 双向链表的基本结构

双向链表的每个节点包含三个部分：数据域、前驱指针、后继指针。用 C 语言描述大概是这样：

typedef struct Node { int data; struct Node* prev; struct Node* next; } Node;

每个节点都知道自己的前一个节点和后一个节点是谁。链表的头节点 prev 指向 NULL，尾节点 next 指向 NULL。这个结构比单向链表多了一个 prev 指针，所以每个节点多占一个指针的内存空间。在 64 位系统上，一个指针 8 字节，所以每个节点多 8 字节开销。这是用空间换时间的典型做法。

双向链表的核心操作包括：在头部插入节点、在尾部插入节点、删除指定节点、遍历。对于栈来说，我们只需要在头部插入和删除，因为栈顶就对应链表的头部。这样 push 和 pop 都是 O(1) 操作，不需要遍历。

2.2 栈的核心约束

栈的核心约束只有一个：后进先出。所有操作都围绕栈顶进行。栈的基本操作包括：

• push：把元素压入栈顶
• pop：弹出栈顶元素
• peek/top：查看栈顶元素但不弹出
• isEmpty：判断栈是否为空
• size：返回栈中元素个数

用双向链表实现时，栈顶对应链表的头节点。push 就是在头部插入一个新节点，pop 就是删除头节点并返回其数据。peek 就是返回头节点的数据。isEmpty 就是判断头节点是否为 NULL。size 可以维护一个计数器，也可以在需要时遍历链表计算，但维护计数器更高效。

2.3 为什么栈顶选头部而不是尾部

这是一个值得想清楚的问题。用双向链表实现栈，栈顶可以选头部，也可以选尾部。两者都是 O(1) 操作，因为双向链表在头部和尾部的插入删除都是常数时间。那为什么大多数实现选头部？

原因有几个。第一，头部操作不需要维护尾指针。如果栈顶选尾部，你需要一个额外的 tail 指针来快速定位尾部，否则每次 push 都要遍历到尾部，那就变成 O(n) 了。第二，头部操作在代码上更简洁，因为头指针是链表的入口，所有操作都从入口开始，逻辑更直观。第三，如果栈顶选尾部，pop 之后需要把 tail 指针往前移，需要访问 tail->prev，这没问题，但代码会稍微绕一点。

当然，选尾部也有好处：如果你同时需要从头部进行队列操作，那尾部做栈顶就更合适。但纯粹实现栈的话，头部是更自然的选择。

3. 完整实现与逐行解析

3.1 Python 版本实现

先看 Python 版本，因为 Python 的语法更简洁，逻辑更清晰。我用一个 Node 类表示节点，一个 Stack 类表示栈。

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class Stack: def __init__(self): self.head = None self._size = 0 def push(self, data): new_node = Node(data) if self.head is None: self.head = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node self._size += 1 def pop(self): if self.head is None: raise IndexError("pop from empty stack") data = self.head.data self.head = self.head.next if self.head is not None: self.head.prev = None self._size -= 1 return data def peek(self): if self.head is None: raise IndexError("peek from empty stack") return self.head.data def is_empty(self): return self.head is None def size(self): return self._size

这段代码看起来简单，但有几个细节值得展开说。

push 操作分两种情况：栈为空时，新节点直接作为头节点；栈不为空时，新节点的 next 指向当前头节点，当前头节点的 prev 指向新节点，然后更新头指针为新节点。注意顺序：先设置 new_node.next，再设置 self.head.prev，最后更新 self.head。如果顺序反了，比如先更新 self.head，那 self.head.prev 就找不到原来的头节点了。

pop 操作也要小心。先保存头节点的数据，然后把头指针往后移。如果新的头节点不为 NULL，要把它的 prev 置为 NULL，因为它现在是栈顶了，前面没有节点了。这一步很容易漏掉，漏掉的话，新的头节点还指着一个已经被弹出的节点，虽然不影响功能，但会造成内存泄漏的风险，而且在某些调试场景下会让人困惑。

3.2 C 语言版本实现

C 语言版本需要手动管理内存，更能体现双向链表的本质。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; typedef struct { Node* head; int size; } Stack; Stack* create_stack() { Stack* s = (Stack*)malloc(sizeof(Stack)); s->head = NULL; s->size = 0; return s; } void push(Stack* s, int data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = data; new_node->prev = NULL; new_node->next = s->head; if (s->head != NULL) { s->head->prev = new_node; } s->head = new_node; s->size++; } int pop(Stack* s) { if (s->head == NULL) { fprintf(stderr, "pop from empty stack\n"); exit(EXIT_FAILURE); } Node* temp = s->head; int data = temp->data; s->head = temp->next; if (s->head != NULL) { s->head->prev = NULL; } free(temp); s->size--; return data; } int peek(Stack* s) { if (s->head == NULL) { fprintf(stderr, "peek from empty stack\n"); exit(EXIT_FAILURE); } return s->head->data; } int is_empty(Stack* s) { return s->head == NULL; } void destroy_stack(Stack* s) { Node* current = s->head; while (current != NULL) { Node* next = current->next; free(current); current = next; } free(s); }

C 版本里，push 的时候要手动 malloc 一个新节点，pop 的时候要手动 free 掉弹出的节点。destroy_stack 用来释放整个栈的内存，遍历链表逐个 free。这里注意，遍历的时候要先保存 next 指针，再 free 当前节点，否则 free 之后 current->next 就是非法访问了。

3.3 边界条件与异常处理

边界条件是手写数据结构时最容易出错的地方。对于双向链表实现的栈，主要有这几个边界：

• 空栈时 pop：应该报错或者返回特定值，不能直接访问 NULL 指针
• 空栈时 peek：同上
• 只有一个元素时 pop：pop 之后 head 变成 NULL，size 变成 0
• push 第一个元素：head 从 NULL 变成新节点，新节点的 prev 和 next 都是 NULL

我见过很多人在只有一个元素时 pop 忘记把 head 的 prev 置 NULL，结果 head 变成 NULL 之后还去访问 head->prev，直接段错误。这个坑很常见，写的时候一定要在脑子里过一遍。

注意：pop 之后如果栈不为空，一定要把新栈顶的 prev 指针置为 NULL。这不是可选项，是必须做的。否则新栈顶还指着一个已经释放的节点，后续操作可能出问题。

4. 性能分析与对比

4.1 时间复杂度对比

从表里可以看出，双向链表栈的 push 是严格 O(1)，不存在数组扩容时的 O(n) 毛刺。这是它最大的优势。数组栈的 push 在大多数时候也是 O(1)，但偶尔会触发扩容，把整个数组拷贝一遍。对于实时性要求高的场景，比如高频交易系统、游戏引擎的帧循环，这种毛刺是不可接受的。

4.2 空间复杂度对比

双向链表栈的空间开销比数组栈大。每个节点除了存数据，还要存两个指针。在 64 位系统上，一个 int 数据占 4 字节，两个指针占 16 字节，总共 20 字节，加上内存对齐，可能占 24 字节。而数组栈每个元素只占 4 字节。所以双向链表栈的内存占用是数组栈的 5 到 6 倍。

但数组栈通常会有预留容量，比如你 push 了 10 个元素，但数组容量可能是 16，有 6 个位置是空的。双向链表栈没有这个问题，用多少分配多少，不会浪费。所以实际内存占用取决于使用模式。如果栈的大小波动很大，双向链表栈可能反而更省内存。

4.3 缓存友好性对比

这是双向链表栈最大的劣势。数组在内存里是连续存放的，CPU 缓存命中率高。双向链表的节点是分散在堆上的，每次访问都要跳转到不同的内存地址，缓存命中率低。在现代 CPU 上，缓存未命中的代价很高，可能差几十倍。

所以如果你的栈操作非常频繁，而且对性能要求极高，数组栈通常是更好的选择。双向链表栈适合那些对单次操作延迟敏感、但对整体吞吐量要求不那么极致的场景。

5. 常见问题与排查技巧

5.1 内存泄漏问题

C 语言版本最容易出的问题就是内存泄漏。每次 push 都 malloc 了一个节点，如果 pop 的时候忘记 free，或者 destroy_stack 没有正确遍历释放，就会泄漏。我建议在开发阶段用 valgrind 或者 AddressSanitizer 跑一遍，确保没有泄漏。

Python 版本有垃圾回收，一般不用担心内存泄漏。但如果你在 Node 里存了循环引用，比如两个节点互相指向对方，垃圾回收器可能无法回收。不过栈的结构是单向的，不会出现循环引用，所以 Python 版本基本安全。

5.2 空指针解引用

空栈时 pop 或者 peek，如果没做检查，直接访问 head->data，就会空指针解引用。C 语言里直接段错误，Python 里抛 AttributeError。所以一定要在 pop 和 peek 开头检查 head 是否为 NULL。

5.3 指针更新顺序错误

push 和 pop 涉及多个指针的更新，顺序很重要。push 的时候，如果先更新 head，再设置 new_node.next，那 new_node.next 就指向新的 head 了，原来的链表就断了。pop 的时候，如果先 free 了头节点，再访问 head->next，就是访问已释放内存。

我个人的习惯是：push 时先处理新节点的指针，再处理旧头节点的指针，最后更新 head。pop 时先保存头节点，再更新 head，再处理新头节点的 prev，最后 free 旧头节点。

5.4 常见问题速查表

6. 扩展与变体

6.1 双端栈

双向链表天然支持双端操作。你可以在头部和尾部都进行 push 和 pop，实现一个双端栈。这在某些场景下很有用，比如你需要同时从两端处理数据。实现上只需要维护 head 和 tail 两个指针，两端操作都是 O(1)。

6.2 带最小值的栈

有时候你需要一个能在 O(1) 时间内返回最小值的栈。用双向链表实现时，可以在每个节点里额外存一个 min 值，表示从栈底到当前节点的最小值。push 的时候，新节点的 min 是 min(新数据, 当前栈顶的 min)。pop 的时候直接返回栈顶的 min。这样所有操作还是 O(1)。

6.3 线程安全版本

多线程环境下使用栈，需要加锁。可以在 Stack 结构里加一个互斥锁，push 和 pop 的时候先加锁再操作。但加锁会带来性能开销，如果并发量很大，可以考虑用无锁数据结构，不过那又是另一个话题了。

7. 我个人的实操体会

我第一次用双向链表实现栈的时候，觉得这玩意太简单了，结果写出来一跑就段错误。排查了半天，发现是 pop 之后忘记把新栈顶的 prev 置 NULL，导致后续操作访问了已释放的内存。这个坑我后来在面试别人的时候也见过好几次，很多人都会漏掉这一步。

还有一个体会是，双向链表实现栈的代码量比数组栈大不少，但逻辑更清晰。数组栈要考虑扩容、缩容、索引计算，双向链表栈就是纯粹的指针操作。如果你要教别人数据结构，用双向链表讲栈可能比用数组更直观，因为所有操作都围绕节点和指针，没有额外的容量管理逻辑。

最后说一个实际场景。我之前做过一个撤销功能，需要记录用户的操作历史，支持无限次撤销和重做。当时就是用两个双向链表实现的栈，一个存撤销历史，一个存重做历史。用户操作时 push 到撤销栈，撤销时从撤销栈 pop 并 push 到重做栈，重做时反过来。双向链表的 O(1) 操作和动态内存分配正好适合这种场景，不用担心数组扩容的毛刺，也不用预估历史记录的最大数量。

如果你也在做类似的功能，或者正在学习数据结构，建议自己动手把双向链表栈写一遍，不要只看不练。写完之后用几个边界用例测一下：空栈 pop、单元素 pop、连续 push 再连续 pop、push 和 pop 交替。这几个用例能覆盖大部分 bug。