一、单向链表（Singly Linked List）
1.1 基本定义
单向链表是一种线性数据结构，由一系列节点通过指针单向连接而成。每个节点包含数据域和指向下一个节点的指针域。
1.2 结构定义
// 单向链表节点结构
typedef struct ListNode {
int data; // 数据域
struct ListNode *next; // 指针域
} ListNode;
// 单向链表管理结构（可选）
typedef struct LinkedList {
ListNode *head; // 头指针
ListNode *tail; // 尾指针
int length; // 链表长度
} LinkedList;
1.3 核心特性
- 动态内存分配：节点按需分配，无需预知数据规模
- 非连续存储：物理地址分散，通过指针建立逻辑联系
- 灵活操作：支持任意位置插入和删除
- 单向遍历：仅支持从头至尾的顺序访问
1.4 时间复杂度分析
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
| 头插 | O(1) | 直接修改头指针 |
| 尾插 | O(1)/O(n) | 若有尾指针则为 O(1) |
| 中间插入 | O(n) | 需遍历至指定位置 |
| 删除 | O(1)/O(n) | 头删除 O(1)，其他需遍历 |
| 查找 | O(n) | 必须顺序遍历 |
二、顺序栈（Sequential Stack）
2.1 基本定义
顺序栈基于数组实现，通过固定偏移量维护栈顶位置，利用连续内存空间存储数据元素。
2.2 结构定义
// 静态顺序栈
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储数据的数组
int top; // 栈顶指针（数组下标）
} StaticSeqStack;
// 动态顺序栈
typedef struct {
int *data; // 动态数组指针
int top; // 栈顶指针
int capacity; // 栈容量
} DynamicSeqStack;
2.3 核心特性
- 连续存储：数据在内存中连续存放
- 大小固定：静态实现有固定上限，动态实现可扩容
- 操作受限：仅允许在栈顶进行插入和删除
- 高效访问：通过数组下标直接访问，缓存友好
2.4 关键操作实现
// 初始化动态顺序栈
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--];
}
三、链式栈（Linked Stack）
3.1 基本定义
链式栈基于链表实现栈结构，具备链表的动态特性与栈的操作限制。其设计存在两种主要模式：单结构体头节点法和双结构体封装法。
3.2 设计模式一：单结构体头节点法
该方法采用单一节点结构，使用头节点作为栈的标识，栈顶位于头节点之后。
结构定义
// 单结构体定义
typedef struct StackNode {
int data; // 数据域
struct StackNode *next; // 指针域
} StackNode;
// 栈节点同时也是栈标识
实现特点
- 头节点作为栈标识：头节点不存储有效数据，其 next 指针指向栈顶
- 统一节点类型：仅需一种结构体类型
- 头插法操作：入栈采用头插法，出栈删除头节点后继
- 函数参数简单：函数直接接收头节点指针
核心操作示例
// 创建空栈
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;
}
3.3 设计模式二：双结构体封装法
该方法采用两个结构体，分别定义节点和栈管理结构，实现逻辑与数据分离。
结构定义
// 节点结构
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;
}
3.4 两种设计模式对比
| 对比维度 | 单结构体头节点法 | 双结构体封装法 |
|---|---|---|
| 结构复杂度 | 简单，一种结构体 | 复杂，两种结构体 |
| 内存开销 | 有头节点额外开销 | 无头节点开销 |
| 状态维护 | 需遍历计算栈大小 | 可直接获取栈大小 |
| 代码清晰度 | 逻辑相对简单 | 职责分离清晰 |
| 扩展性 | 扩展性有限 | 易于扩展功能 |
| 适用场景 | 简单栈操作 | 需要状态维护的复杂栈 |
四、三项结构综合对比
4.1 存储结构对比
| 特性 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 物理结构 | 非连续存储 | 连续存储 | 非连续存储 |
| 内存分配 | 动态节点分配 | 静态数组或动态数组 | 动态节点分配 |
| 指针开销 | 每个节点含指针 | 无指针开销 | 每个节点含指针 |
| 内存连续性 | 不连续，碎片化 | 连续，无碎片 | 不连续，碎片化 |
4.2 操作特性对比
| 特性 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 插入位置 | 任意位置 | 仅栈顶 | 仅栈顶 |
| 删除位置 | 任意位置 | 仅栈顶 | 仅栈顶 |
| 访问方式 | 顺序访问 | 随机访问（数组下标） | 顺序访问 |
| 遍历方向 | 单向遍历 | 双向（理论上） | 单向遍历 |
| 扩容机制 | 自然扩展 | 需要显式扩容 | 自然扩展 |
4.3 性能指标对比
| 指标 | 单向链表 | 顺序栈 | 链式栈 |
|---|---|---|---|
| 头插/入栈 | O(1) | O(1)（平摊） | O(1) |
| 尾插 | O(1)/O(n) | 不支持 | 不支持 |
| 中间插入 | O(n) | 不支持 | 不支持 |
| 头删/出栈 | O(1) | O(1) | O(1) |
| 查找访问 | O(n) | O(1)（通过下标） | O(n) |
| 缓存效率 | 差 | 好 | 差 |
| 空间利用率 | 较低（含指针） | 高 | 较低（含指针） |
五、结论
单向链表、顺序栈和链式栈代表了三种不同的线性数据组织策略。单向链表强调操作灵活性，顺序栈注重访问效率，链式栈则结合了动态扩展与操作约束。
链式栈的两种设计模式体现了不同的工程权衡：单结构体头节点法以简洁性见长，双结构体封装法则以扩展性取胜。实际选择应基于具体需求，权衡性能、内存、扩展性和实现复杂度等因素。
在系统设计中，理解这些基础结构的本质特性及其实现差异，对于选择合适的数据结构、优化算法性能、构建稳定可靠的软件系统具有重要意义。每种结构都有其适用场景，优秀的系统设计者应根据具体约束条件做出合理选择，而非盲目追求某种结构的普遍适用性。