当前位置：首页 > ds >正文

顺序表VS单链表

ds 2025/9/5 21:37:33

1. 顺序表与链表的应用场景

在数据结构中，顺序表和单链表是两种最基础的线性存储结构，它们的实现方式和适用场景截然不同：

顺序表：适合频繁查询和尾部操作的场景。
单链表：适合频繁插入/删除且数据量动态变化的场景。

2. 概念对比

特性	顺序表	单链表
存储方式	连续内存空间（数组）	非连续内存空间（节点通过指针链接）
随机访问	支持，时间复杂度 O(1)	不支持，需遍历，时间复杂度 O(n)
动态扩容	需重新分配内存并拷贝数据	按需动态分配，无需扩容
内存占用	空间预分配，可能存在浪费	按需分配，无额外空间浪费
缓存友好性	高（内存连续，缓存命中率高）	低（内存分散，缓存局部性差）

3. 存储结构与内存管理

(1) 顺序表的存储结构

typedef struct SeqList {SLDataType* arr;    // 动态数组指针int capacity;       // 总容量int size;           // 当前元素个数
} SL;

特点：内存连续，通过数组索引直接访问元素。
扩容机制：容量不足时按倍数（如2倍）扩容，涉及内存拷贝（realloc）。

(2) 单链表的存储结构

typedef struct SListNode {SLTDataType data;    // 数据域struct SListNode* next; // 指针域
} SLTNode;

特点：每个节点独立分配内存，通过指针链接。
内存管理：插入时动态分配节点（malloc），删除时释放节点（free）。

4. 基本操作的实现与时间复杂度

(1) 插入操作

操作	顺序表	单链表
头部插入	O(n)，需移动所有元素	O(1)，修改头指针
尾部插入	O(1)（不考虑扩容）	O(n)，需遍历到尾部
指定位置插入	O(n)，平均移动 n/2 个元素	O(n)，需遍历到前驱节点

// 顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x) {SLCheckCapacity(ps); // 检查扩容ps->arr[ps->size++] = x;
}// 单链表头部插入
void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode; // 直接修改头指针
}

(2) 删除操作

操作	顺序表	单链表
头部删除	O(n)，需移动所有元素	O(1)，修改头指针
尾部删除	O(1),直接减少size	O(n)，需遍历到倒数第二个节点
指定位置删除	O(n)，平均移动 n/2 个元素	O(n)，需遍历到前驱节点

// 顺序表尾部删除
void SLPopBack(SL* ps) {assert(ps->size > 0);ps->size--; // 逻辑删除
}// 单链表头部删除
void SLTPopFront(SLTNode** pphead) {SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next; // 更新头指针
}

(3) 查找操作

顺序表：直接通过下标访问（O(1)）。
单链表：需从头节点遍历（O(n)）。

(4) 指针使用的区别

场景	顺序表	单链表
头指针操作	通过结构体指针直接操作数组（`SL* ps`）。	需使用双重指针（`SLTNode** pphead`）修改头指针。
节点访问	通过下标直接访问（`arr[i]`）。	需遍历指针链（`pcur = pcur->next`）。