顺序表、链表核心知识汇总

在数据结构的基础学习中，顺序表和链表是两种最基础、最常用的线性表结构，它们各自有着独特的存储方式、操作特性和适用场景。无论是笔试面试还是实际开发，掌握二者的核心知识点及区别，都是必备的基础能力。本文将从定义、存储结构、核心操作、优缺点及适用场景等方面，全面汇总顺序表与链表的相关知识，帮助大家快速理清思路、夯实基础。

一、线性表基础认知

在讲解顺序表和链表之前，首先明确一个基础概念：线性表。线性表是由n（n≥0）个具有相同数据类型的元素组成的有限序列，其特点是元素之间存在“一对一”的逻辑关系——除了第一个元素，每个元素有且仅有一个直接前驱；除了最后一个元素，每个元素有且仅有一个直接后继。

顺序表和链表，本质上都是线性表的具体实现方式，核心区别在于元素的存储方式不同，这也导致了二者在操作效率、空间利用率等方面的差异。

二、顺序表详解

2.1 定义

顺序表是用一段连续的存储单元依次存储线性表中的各个元素，使得逻辑上相邻的元素，在物理存储位置上也相邻。简单来说，就是把元素“排成一排”，每个元素紧挨着前一个元素，没有空隙。

类比生活中的例子：排队买奶茶，每个人依次站在队伍里，位置是连续的，知道前一个人的位置，就能直接找到下一个人，这就是顺序表的逻辑。

2.2 存储结构

顺序表的存储结构分为两种：静态顺序表和动态顺序表，二者的存储示意图如下：

静态顺序表

使用固定大小的数组存储，数组的容量在初始化时就确定，无法动态调整。

• 优点是实现简单；
• 缺点是空间利用率低（若元素个数远小于数组容量，会浪费空间），且无法应对元素个数超过数组容量的情况。

动态顺序表

使用动态数组（malloc/realloc）存储，容量可以根据元素个数动态扩容（通常是扩容为原容量的1.5倍或2倍）。

• 优点是空间利用率高，能灵活应对元素增减；
• 缺点是扩容时需要申请新的连续空间，拷贝原有元素，会消耗一定的时间成本。

2.3 核心操作及时间复杂度

顺序表的核心操作包括：初始化、插入、删除、查找、修改、求长度等，其中插入和删除的时间复杂度与操作位置相关，查找和修改的时间复杂度固定。以下仅展示各操作的核心代码（省略冗余校验，聚焦核心逻辑）：

• 初始化：分配连续的存储空间，初始化元素个数为0，时间复杂度O(1)。

// 动态顺序表核心结构体
typedef struct SeqList{
int* data; // 存储元素的数组
int size; // 当前元素个数
int capacity; // 顺序表容量
} SeqList;

// 核心初始化逻辑
void SeqListInit(SeqList* sl) {
sl->data = (int*)malloc(sizeof(int) * 4); // 初始容量4
sl->size = 0;
sl->capacity = 4;
}

• 插入操作：核心逻辑为扩容（如需）+ 元素移动（头插/中间插），尾插无需移动元素。
• 尾插：在顺序表末尾插入元素，无需移动其他元素，时间复杂度O(1)。

// 尾插核心代码（无需移动元素）
void SeqListPushBack(SeqList* sl, int x) {
if(s1 == NULL) exit(EXIT_FAILURE);
if (sl->size == sl->capacity) // 扩容判断（核心）
sl->data = (int*)realloc(sl->data, sizeof(int)*sl->capacity*2);
sl->data[sl->size++] = x;
}

• 头插/中间插：需要将插入位置及之后的所有元素向后移动一位，腾出空间插入新元素，最坏情况下（头插）需要移动所有元素，时间复杂度O(n)。

// 头插核心代码（需移动元素）
void SeqListPushFront(SeqList* sl, int x) {
if(s1 == NULL) exit(EXIT_FAILURE);
for (int i = sl->size; i > 0; i–) // 从后往前移动
sl->data[i] = sl->data[i-1];
sl->data[0] = x;
sl->size++;
}

• 删除操作：核心逻辑为元素移动（头删/中间删），尾删无需移动元素。
• 尾删：删除末尾元素，无需移动其他元素，时间复杂度O(1)。

// 尾删核心代码
void SeqListPopBack(SeqList* sl) {
if(s1 == NULL) exit(EXIT_FAILURE);
if (sl->size == 0) return;
sl->size–; // 直接缩减长度，后续插入覆盖
}

• 头删/中间删：需要将删除位置之后的所有元素向前移动一位，填补空缺，最坏情况下（头删）需要移动所有元素，时间复杂度O(n)。

// 头删核心代码
void SeqListPopFront(SeqList* sl) {
if(s1 == NULL) exit(EXIT_FAILURE);
for (int i = 0; i < sl->size – 1; i++) // 从前往后移动
sl->data[i] = sl->data[i+1];
sl->size–;
}

• 查找与修改：按下标操作O(1)，按值操作O(n)，核心代码如下：

// 按下标查找
int SeqListFindByIndex(SeqList* sl, int index) {
if(s1 == NULL) return -1;
//下标校验…
return sl->data[index];
}

// 按下标修改
void SeqListModifyByIndex(SeqList* sl, int index, int x) {
if(s1 == NULL) return -1;
sl->data[index] = x; // 直接修改
}

• 销毁代码：

// 顺序表销毁核心
void SeqListDestroy(SeqList* sl) {
free(sl->data);
sl->data = NULL;
sl->size = sl->capacity = 0;
}

2.4 优缺点

优点

• 存储密度高：元素之间没有空隙，无需额外存储指针（或引用），空间利用率高（静态顺序表除外）。
• 按下标访问效率高：支持随机访问，通过下标可直接定位元素，时间复杂度O(1)。
• 实现简单：基于数组实现，代码逻辑简洁，易于理解和实现。

缺点

• 插入/删除效率低：除了尾插、尾删，其他位置的插入/删除需要移动大量元素，时间成本高。
• 动态扩容有开销：动态顺序表扩容时，需要申请新空间、拷贝元素，可能导致性能波动。
• 空间灵活性差：静态顺序表容量固定，动态顺序表扩容后若元素减少，多余空间无法释放，仍会造成浪费。

三、链表详解

3.1 定义

链表是一种非连续、非顺序的存储结构，它通过“指针（或引用）”将分散在内存中的各个元素（称为“节点”）连接起来。逻辑上相邻的元素，物理存储位置上可以不相邻，每个节点除了存储自身的数据，还会存储下一个（或上一个）节点的地址。

类比生活中的例子：一串糖葫芦，每个山楂（节点）都通过竹签（指针）连接起来，山楂的位置可以分散（比如串歪了），但通过竹签就能找到下一个山楂，这就是链表的逻辑。

3.2 常见链表类型

根据节点的连接方式，链表主要分为以下4种，其中单链表和双链表是最常用的类型。

单链表

每个节点只存储“数据域”和“后继指针”（指向后一个节点），尾节点的后继指针为null。结构最简单，但只能从表头向后遍历，无法反向遍历。

// 单链表节点核心结构体
typedef struct ListNode {
int data; // 数据域
struct ListNode* next; // 后继指针
} ListNode;

双链表

每个节点除了数据域和后继指针，还增加了“前驱指针”（指向前一个节点），头节点的前驱指针为null，尾节点的后继指针为null。支持双向遍历，插入/删除操作更灵活，但需要额外存储前驱指针，空间开销略大。

// 双链表节点结构体
typedef struct DListNode {
int data; // 数据域
struct DListNode* prev; // 前驱指针（指向前一个节点）
struct DListNode* next; // 后继指针（指向后一个节点）
} DListNode;

循环链表

基于单链表或双链表改造，尾节点的后继指针不指向null，而是指向头节点，形成一个闭环。适合需要循环遍历的场景（如约瑟夫环问题）。

双向循环链表

双链表的闭环版本，头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，支持双向循环遍历，灵活性最高，但空间开销最大。

3.3 核心操作及时间复杂度

链表的核心操作与顺序表一致，但由于存储结构不同，时间复杂度有明显差异，核心优势体现在插入/删除操作（无需移动元素）。以下以最常用的单链表为例，展示各操作的核心代码（省略冗余校验）：

• 初始化：创建头节点（或不带头节点），初始化指针为空，时间复杂度O(1)。

// 单链表节点核心结构体
typedef struct ListNode {
int data; // 数据域
struct ListNode* next; // 后继指针
} ListNode;

// 带头节点初始化（核心）
ListNode* ListInitWithHead() {
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL; // 头节点后继指针置空
return head;
}

• 插入操作：核心逻辑为修改指针指向，无需移动元素。
• 头插：直接创建新节点，将新节点的后继指针指向原头节点，再更新头节点为新节点，无需移动元素，时间复杂度O(1)。

// 头插核心代码
ListNode* ListPushFront(ListNode* head, int x) {
//判空…
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = x;
//先修改新创建节点的指针域
newNode->next = head->next; // 新节点指向头节点后继
head->next = newNode; // 头节点指向新节点
return head;
}

• 尾插：若有尾指针（记录尾节点位置），直接将尾节点的后继指针指向新节点，更新尾指针，时间复杂度O(1)；若无尾指针，需先遍历到尾节点，时间复杂度O(n)。

// 尾插核心代码（带头节点）
void ListPushBack(ListNode* head, int x) {
//判空…
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = x;
newNode->next = NULL;
ListNode* cur = head;
while (cur->next != NULL) cur = cur->next; // 找到尾节点
cur->next = newNode; // 尾节点指向新节点
}

• 中间插：找到插入位置的前驱节点，将新节点的后继指针指向前驱节点的后继节点，再将前驱节点的后继指针指向新节点，无需移动其他元素，时间复杂度O(n)（主要耗时在查找前驱节点）。

//查找前驱节点
ListNode* cur = head;
while (cur->next != NULL && cur->next != pos) {
cur = cur->next;
}

• 删除操作：核心逻辑为修改指针指向，释放目标节点。
• 头删：将头节点指向原头节点的后继节点，释放原头节点，时间复杂度O(1)。

void ListPopFront(ListNode* head) {
ListNode* temp = head->next; // temp = node1

head->next = temp->next; // head->next = NULL
free(temp); // 删掉 node1
}

• 尾删：若无尾指针，需遍历到倒数第二个节点，将其后继指针设为null，时间复杂度O(n)；若有尾指针，还需找到前驱节点，时间复杂度仍为O(n)（双链表可优化为O(1)）。

// 尾删核心代码（带头节点 + 安全判断）
void ListPopBack(ListNode* head) {
// 空链表，没有节点可删
if (head->next == NULL)
return;

ListNode* cur = head;
// 找到倒数第二个节点
while (cur->next->next != NULL)
cur = cur->next;

free(cur->next);
cur->next = NULL;
}

• 中间删：找到删除节点的前驱节点，将前驱节点的后继指针指向删除节点的后继节点，释放删除节点，时间复杂度O(n)（主要耗时在查找前驱节点）。

// 中间删：删除值为 x 的节点
void ListDelete(ListNode* head, int x) {
ListNode* prev = head;

// 查找前驱节点（核心）
while (prev->next != NULL && prev->next->data != x) {
prev = prev->next;
}

// 找到则删除
if (prev->next != NULL) {
ListNode* del = prev->next;
prev->next = del->next;
free(del);
}
}

• 查找与修改：核心为遍历查找，时间复杂度O(n)。

// 按值查找（带头节点）
ListNode* ListFindByVal(ListNode* head, int x) {
ListNode* cur = head->next;
while (cur != NULL && cur->data != x) {
cur = cur->next;
}
return cur; // 找到返回节点，没找到返回 NULL
}

// 修改节点数据（带安全判断）
void ListModify(ListNode* pos, int x) {
if (pos != NULL) { // 防止空指针
pos->data = x;
}
}

• 实际开发中需注意内存释放，避免内存泄漏，核心销毁代码如下：

// 单链表销毁核心（带头节点）
void ListDestroy(ListNode* head) {
ListNode* cur = head;
while (cur != NULL) {
ListNode* temp = cur;
cur = cur->next;
free(temp);
}
}

3.4 优缺点

优点

• 插入/删除效率高：除了查找前驱节点的耗时，插入/删除本身无需移动元素，仅需修改指针，时间复杂度O(1)（查找除外）。
• 空间灵活性高：元素按需分配内存，无需提前申请连续空间，也不会造成空间浪费（除非有指针冗余）。
• 扩容无开销：无需像顺序表那样扩容，只要内存有空闲，就能随时添加新节点。

缺点

• 访问效率低：不支持随机访问，只能顺序遍历，查找和修改操作的时间复杂度较高。
• 存储密度低：每个节点除了存储数据，还需存储指针（或引用），额外占用内存空间。
• 实现复杂：相比顺序表，链表的指针操作较多，代码逻辑更复杂，容易出现指针异常（如空指针、野指针）。

四、顺序表与链表核心对比

为了更清晰地掌握二者的差异，以下从核心维度进行对比，方便大家快速选型：

五、总结与拓展

顺序表和链表，没有绝对的优劣之分，核心是“按需选型”：

• 如果你的场景中，查找、修改操作频繁（比如查询学生成绩、修改用户信息），且元素个数不会频繁大幅波动，优先选择顺序表。
• 如果你的场景中，插入、删除操作频繁（比如购物车添加/删除商品、消息队列的入队/出队），且元素个数动态变化，优先选择链表。

此外，在实际开发中，还会基于二者的特性进行优化，比如：用顺序表实现栈（尾插尾删效率高），用链表实现队列（头删尾插效率高）；或者结合二者的优点，实现“静态链表”（用数组模拟链表，兼顾顺序表的随机访问和链表的插入删除灵活性）。

最后，希望本文的汇总能帮助大家理清顺序表与链表的知识点，夯实数据结构的基础，在学习和面试中少走弯路～