前言
之前存储数据一直使用数组，数组空间连续、支持随机访问，但长度固定，中间增删元素开销很大。今天学习单向链表，采用带头结点结构，利用动态内存存储数据，解决数组的短板。链表是面试高频考点，重点吃透增删改查、链表反转、冒泡排序等核心逻辑。
一、数组 vs 单向链表
数组
- 内存连续，支持下标随机访问，读取速度快。
- 定义时长度固定，元素数量存在上限。
- 中间插入、删除需要移动大量元素，效率低。
单向链表
- 节点分散存储，内存无需连续，不能随机访问，只能顺序遍历。
- 每个节点带有指针域，存在额外内存开销。
- 动态申请内存，数据数量理论上没有上限。
- 已知位置插入、删除仅修改指针，效率更高。
使用建议：
- 数据规模固定、频繁查询选数组。
- 数据数量不确定、频繁增删选择链表。
二、链表结构定义
选用带头结点单向链表，头结点不存放有效数据，统一空链表与非空链表操作逻辑。
typedef int DataType;
typedef struct node {
DataType Data; // 数据域
struct node *pNext; // 指针域，保存下一个节点地址
} Node_t;
三、核心接口（面试重点函数）
1. 创建空链表
Node_t *CreateEmptyLinkList(void) {
Node_t *head = malloc(sizeof(Node_t));
if (head == NULL) {
printf("malloc failed\\n");
return NULL;
}
head->pNext = NULL;
return head;
}
2. 头插节点
int InsertHead(Node_t *head, DataType data) {
Node_t *newNode = malloc(sizeof(Node_t));
if (newNode == NULL)
return –1;
newNode->Data = data;
// 顺序不能颠倒！先指向后继节点
newNode->pNext = head->pNext;
head->pNext = newNode;
return 0;
}
3. 遍历打印链表
void ShowLinkList(Node_t *head) {
Node_t *p = head->pNext;
while (p != NULL) {
printf("%d ", p->Data);
p = p->pNext;
}
printf("\\n");
}
4. 删除指定数据（面试基础）
int DeleteNode(Node_t *head, DataType data) {
Node_t *pCur = head->pNext;
Node_t *pPre = head;
int cnt = 0;
while (pCur != NULL) {
if (pCur->Data == data) {
pPre->pNext = pCur->pNext;
free(pCur);
pCur = pPre->pNext;
cnt++;
} else {
pPre = pCur;
pCur = pCur->pNext;
}
}
return cnt;
}
5. 链表反转（🔥面试高频）
思路：头插法。断开原链表，依次取出节点不断头插，完成逆序。
int ReverseLinkList(Node_t *head) {
Node_t *pCur = head->pNext;
head->pNext = NULL;
while (pCur != NULL) {
Node_t *tmp = pCur;
pCur = pCur->pNext;
tmp->pNext = head->pNext;
head->pNext = tmp;
}
return 0;
}
6. 链表冒泡排序（🔥面试常考）
实现方式：交换节点数据；进阶版本可以直接交换节点指针。
void BubbleSortLinkList(Node_t *head) {
if (head->pNext == NULL || head->pNext->pNext == NULL)
return;
Node_t *pEnd = NULL;
while (1) {
if (pEnd == head->pNext->pNext)
break;
Node_t *p1 = head->pNext;
Node_t *p2 = p1->pNext;
while (p2 != pEnd) {
if (p1->Data > p2->Data) {
DataType temp = p1->Data;
p1->Data = p2->Data;
p2->Data = temp;
}
p1 = p2;
p2 = p2->pNext;
}
pEnd = p1;
}
}
7. 销毁链表（防止内存泄漏）
void DestroyLinkList(Node_t **ppHead) {
Node_t *pFree = *ppHead;
while (pFree != NULL) {
Node_t *tmp = pFree->pNext;
free(pFree);
pFree = tmp;
}
*ppHead = NULL;
}
