单向链表、顺序栈和链式栈三种数据结构。内容包括基本定义、结构体设计、核心特性及时间复杂度分析。重点对比了顺序栈的静态与动态实现，以及链式栈的单结构体头节点法与双结构体封装法。最后通过表格综合对比了三种结构在存储、操作及性能上的差异，为系统设计中选择合适的数据结构提供依据。
单向链表是一种线性数据结构，由一系列节点通过指针单向连接而成。每个节点包含数据域和指向下一个节点的指针域。
// 单向链表节点结构
typedef struct ListNode {
int data;
} ListNode;
ListNode *head;
ListNode *tail;
length;
} LinkedList;
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
| 头插 | O(1) | 直接修改头指针 |
| 尾插 | O(1)/O(n) | 若有尾指针则为 O(1) |
| 中间插入 | O(n) | 需遍历至指定位置 |
| 删除 | O(1)/O(n) | 头删除 O(1)，其他需遍历 |
| 查找 | O(n) | 必须顺序遍历 |
顺序栈基于数组实现，通过固定偏移量维护栈顶位置，利用连续内存空间存储数据元素。
// 静态顺序栈
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针（数组下标）
} StaticSeqStack;
// 动态顺序栈
typedef struct {
int *data; // 动态数组指针
int top; // 栈顶指针
int capacity; // 栈容量
} DynamicSeqStack;
// 初始化动态顺序栈
DynamicSeqStack* InitDynamicStack(int initCapacity) {
DynamicSeqStack *stack = (DynamicSeqStack*)malloc(sizeof(DynamicSeqStack));
stack->data = (int*)malloc(initCapacity * sizeof(int));
stack->top = -1;
stack->capacity = initCapacity;
return stack;
}
// 入栈操作
int Push(DynamicSeqStack *stack, int value) {
if (stack->top == stack->capacity - 1) {
// 栈满，需要扩容
int newCapacity = stack->capacity * 2;
int *newData = (int*)realloc(stack->data, newCapacity * sizeof(int));
if (!newData) return 0;
stack->data = newData;
stack->capacity = newCapacity;
}
stack->data[++stack->top] = value;
return 1;
}
// 出栈操作
int Pop(DynamicSeqStack *stack) {
if (stack->top == -1) {
// 栈空处理
return INT_MIN;
}
return stack->data[stack->top--];
}
链式栈基于链表实现栈结构，具备链表的动态特性与栈的操作限制。其设计存在两种主要模式：单结构体头节点法和双结构体封装法。
该方法采用单一节点结构，使用头节点作为栈的标识，栈顶位于头节点之后。
// 单结构体定义
typedef struct StackNode {
int data; // 数据域
struct StackNode *next; // 指针域
} StackNode;
// 栈节点同时也是栈标识
// 创建空栈
StackNode* CreateStack() {
StackNode *head = (StackNode*)malloc(sizeof(StackNode));
head->next = NULL; // 空栈，头节点 next 为 NULL
return head;
}
// 入栈操作
void Push(StackNode *head, int value) {
StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->data = value;
newNode->next = head->next; // 新节点指向原栈顶
head->next = newNode; // 头节点指向新栈顶
}
// 出栈操作
int Pop(StackNode *head) {
if (head->next == NULL) {
return INT_MIN; // 栈空处理
}
StackNode *top = head->next;
int value = top->data;
head->next = top->next;
free(top);
return value;
}
该方法采用两个结构体，分别定义节点和栈管理结构，实现逻辑与数据分离。
// 节点结构
typedef struct LinkedStackNode {
int data; // 数据域
struct LinkedStackNode *next; // 指针域
} LinkedStackNode;
// 栈管理结构
typedef struct {
LinkedStackNode *top; // 栈顶指针
int size; // 栈大小
} LinkedStack;
// 创建空栈
LinkedStack* CreateLinkedStack() {
LinkedStack *stack = (LinkedStack*)malloc(sizeof(LinkedStack));
stack->top = NULL;
stack->size = 0;
return stack;
}
// 入栈操作
void PushLinkedStack(LinkedStack *stack, int value) {
LinkedStackNode *newNode = (LinkedStackNode*)malloc(sizeof(LinkedStackNode));
newNode->data = value;
newNode->next = stack->top; // 新节点指向原栈顶
stack->top = newNode; // 更新栈顶指针
stack->size++; // 更新栈大小
}
// 出栈操作
int PopLinkedStack(LinkedStack *stack) {
if (stack->top == NULL) {
return INT_MIN; // 栈空处理
}
LinkedStackNode *topNode = stack->top;
int value = topNode->data;
stack->top = topNode->next; // 更新栈顶指针
free(topNode);
stack->size--; // 更新栈大小
return value;
}
| 对比维度 | 单结构体头节点法 | 双结构体封装法 |
|---|---|---|
| 结构复杂度 | 简单，一种结构体 | 复杂，两种结构体 |
| 内存开销 | 有头节点额外开销 | 无头节点开销 |
| 状态维护 | 需遍历计算栈大小 | 可直接获取栈大小 |
| 代码清晰度 | 逻辑相对简单 | 职责分离清晰 |
| 扩展性 | 扩展性有限 | 易于扩展功能 |
| 适用场景 | 简单栈操作 | 需要状态维护的复杂栈 |
| 特性 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 物理结构 | 非连续存储 | 连续存储 | 非连续存储 |
| 内存分配 | 动态节点分配 | 静态数组或动态数组 | 动态节点分配 |
| 指针开销 | 每个节点含指针 | 无指针开销 | 每个节点含指针 |
| 内存连续性 | 不连续，碎片化 | 连续，无碎片 | 不连续，碎片化 |
| 特性 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 插入位置 | 任意位置 | 仅栈顶 | 仅栈顶 |
| 删除位置 | 任意位置 | 仅栈顶 | 仅栈顶 |
| 访问方式 | 顺序访问 | 随机访问（数组下标） | 顺序访问 |
| 遍历方向 | 单向遍历 | 双向（理论上） | 单向遍历 |
| 扩容机制 | 自然扩展 | 需要显式扩容 | 自然扩展 |
| 指标 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 头插/入栈 | O(1) | O(1)（平摊） | O(1) |
| 尾插 | O(1)/O(n) | 不支持 | 不支持 |
| 中间插入 | O(n) | 不支持 | 不支持 |
| 头删/出栈 | O(1) | O(1) | O(1) |
| 查找访问 | O(n) | O(1)（通过下标） | O(n) |
| 缓存效率 | 差 | 好 | 差 |
| 空间利用率 | 较低（含指针） | 高 | 较低（含指针） |
单向链表、顺序栈和链式栈代表了三种不同的线性数据组织策略。单向链表强调操作灵活性，顺序栈注重访问效率，链式栈则结合了动态扩展与操作约束。
链式栈的两种设计模式体现了不同的工程权衡：单结构体头节点法以简洁性见长，双结构体封装法则以扩展性取胜。实际选择应基于具体需求，权衡性能、内存、扩展性和实现复杂度等因素。
在系统设计中，理解这些基础结构的本质特性及其实现差异，对于选择合适的数据结构、优化算法性能、构建稳定可靠的软件系统具有重要意义。每种结构都有其适用场景，优秀的系统设计者应根据具体约束条件做出合理选择，而非盲目追求某种结构的普遍适用性。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online