链表基本运算详解：查找、插入、删除及特殊链表

在上一篇文章中，我们介绍了线性表的基本概念和顺序存储。本文将深入探讨单链表的基本运算，并介绍循环链表和双向链表这两种特殊的链表结构，帮助读者全面掌握链表的操作技巧。

1.单链表基本运算

单链表是最基础的动态数据结构，其基本运算包括查找、插入、删除等操作。理解这些基本运算的原理和实现，是掌握更复杂数据结构的关键。

链表的查找操作

链表的查找分为按序号查找和按值查找两种方式，它们是其他操作的基础。

按序号查找

按序号查找是根据元素在链表中的位置来定位元素。

// 在带头节点的单链表head中查找第i个节点，返回节点的存储位置
LinkList *Get(LinkList *head, int i) {int j = 0;LinkList *p = head;  // 从头节点开始扫描while ((p->next != NULL) && (j < i)) {p = p->next;     // 扫描下一个节点j++;             // 已扫描节点计数器}if (i == j)return p;        // 找到了第i个节点elsereturn NULL;     // 未找到，i≤0或i>n
}

按值查找

按值查找是根据数据元素的值来定位节点。

// 在带头节点的单链表head中查找节点值等于key的节点
// 若找到则返回节点的位置p；否则返回NULL
LinkList *Locate(LinkList *head, DataType key) {LinkList *p = head->next;  // 从首元节点开始比较while ((p != NULL) && (p->data != key)) {p = p->next;           // 没找到则继续循环}return p;  // 找到返回节点指针，否则返回NULL
}

时间复杂度分析：两种查找操作的时间复杂度都是O(n)，因为在最坏情况下需要遍历整个链表。

链表的插入操作

链表插入操作的优势在于不需要移动其他元素，只需要修改指针即可。

在指定节点后插入

void InsertAfter(LinkList *p, DataType x) {LinkList *s = (LinkList*)malloc(sizeof(LinkList));  // 生成新节点s->data = x;s->next = p->next;  // 新节点指向原后继节点p->next = s;        // 原节点指向新节点
}

时间复杂度：O(1)，因为只需要修改两个指针。

在指定节点前插入

在节点前插入相对复杂，需要先找到前驱节点。

// 在带头节点的单链表head中，将值为x的新节点插入到节点p之前
void InsertBefore(LinkList *head, LinkList *p, DataType x) {LinkList *s = (LinkList*)malloc(sizeof(LinkList));  // 生成新节点s->data = x;LinkList *q = head;  // 从头指针开始while (q->next != p) {q = q->next;     // 查找p的前驱节点q}s->next = p;         // 新节点指向pq->next = s;         // 前驱节点指向新节点
}

实现线性表的插入运算

结合查找和插入操作，实现标准的线性表插入运算。

void Insert(LinkList *L, DataType x, int i) {LinkList *p = Get(L, i - 1);  // 找到第i-1个节点if (p == NULL) {printf("插入位置不合法\n");  // i<1或i>(n+1)} else {InsertAfter(p, x);           // 将值为x的新节点插入到p之后}
}

链表的删除操作

删除操作需要修改前驱节点的指针，并释放被删节点的内存。

删除指定节点

void DeleteNode(LinkList *head, LinkList *p) {LinkList *q = head;  // 查找p的前驱节点qwhile (q->next != p) {q = q->next;}q->next = p->next;   // 删除节点pfree(p);             // 释放节点p的内存
}

实现线性表的删除运算

void Delete(LinkList *L, int i) {LinkList *p = Get(L, i - 1);  // 找到第i-1个节点if ((p != NULL) && (p->next != NULL)) {LinkList *r = p->next;    // r为节点p的后继p->next = r->next;        // 将节点r从链表上摘下free(r);                  // 释放节点r} else {printf("删除位置不合法\n");  // i<1或i>n}
}

链表合并算法

将两个递增有序的单链表合并为一个递增有序的单链表，要求不另外开辟存储空间。

LinkList *Union(LinkList *la, LinkList *lb) {LinkList *p = la->next, *q = lb->next;LinkList *r = la;  // r为p的直接前驱while ((p != NULL) && (q != NULL)) {if (p->data > q->data) {// 将q节点插入到r之后LinkList *u = q->next;r->next = q;r = q;q->next = p;q = u;} else {// p节点保持原位r = p;p = p->next;}}if (q != NULL) {r->next = q;  // 将剩余节点连接到结果链表}free(lb);  // 释放lb的头节点return la;
}

算法思想：采用归并思想，逐一比较两个链表的节点值，将较小的节点插入到结果链表中。

2.循环链表

循环链表是一种特殊的单链表，其最后一个节点的指针不是NULL，而是指向头节点，形成一个环形结构。

循环链表的特点

• 无需NULL判断：遍历时不需要判断是否到达链表末尾
• 任意起点：可以从任意节点开始遍历整个链表
• 适合循环应用：如约瑟夫问题、循环队列等

循环链表的插入操作

void Insert(LinkList *head, DataType x, int i) {LinkList *s = (LinkList*)malloc(sizeof(LinkList));s->data = x;  // 生成值为x的新节点LinkList *p = head;int j = 0;// 查找第i个位置while ((p->next != head) && (j < i)) {p = p->next;j++;}if (i == j) {s->next = p->next;p->next = s;  // 执行插入操作} else {printf("插入位置不合法\n");free(s);}
}

关键差异：循环条件从p->next != NULL改为p->next != head。

3.双向链表

双向链表的每个节点包含两个指针域：一个指向直接前驱，另一个指向直接后继。

双向链表的结构定义

typedef char DataType;typedef struct dnode {DataType data;           // 数据域struct dnode *prior;     // 指向前驱节点的指针struct dnode *next;      // 指向后继节点的指针
} DLinkList;

双向链表的优势

1. 双向遍历：可以从任意节点向前或向后遍历
2. 删除效率高：删除指定节点时无需查找前驱节点
3. 插入灵活：可以方便地在任意位置插入节点

双向链表的基本操作

删除节点

void DeleteNode(DLinkList *p) {if (p->prior != NULL) {p->prior->next = p->next;  // 修改前驱节点的后继指针}if (p->next != NULL) {p->next->prior = p->prior; // 修改后继节点的前驱指针}free(p);  // 释放节点内存
}

在指定节点前插入

void InsertBefore(DLinkList *p, DataType x) {DLinkList *s = (DLinkList*)malloc(sizeof(DLinkList));s->data = x;s->prior = p->prior;     // 新节点的前驱指向p的前驱s->next = p;             // 新节点的后继指向pif (p->prior != NULL) {p->prior->next = s;  // 修改p前驱的后继指针}p->prior = s;            // 修改p的前驱指针
}

时间复杂度：双向链表的插入和删除操作都是O(1)，因为不需要查找前驱节点。

4.存储密度分析

存储密度是衡量数据结构空间效率的重要指标：

存储密度 = 节点数据本身占用存储量 / 节点结构占用存储量

不同链表结构的存储密度对比

假设数据域占用4字节，指针域占用8字节：

• 单链表：存储密度 = 4/(4+8) = 1/3 ≈ 0.33
• 双向链表：存储密度 = 4/(4+8+8) = 1/5 = 0.2
• 数组：存储密度 = 4/4 = 1.0

空间效率分析

1. 数组：存储密度最高，但空间固定分配
2. 单链表：存储密度适中，空间动态分配
3. 双向链表：存储密度较低，但操作效率高

5.链表运算复杂度总结

操作	单链表	双向链表	循环链表
查找	O(n)	O(n)	O(n)
插入(已知位置)	O(1)	O(1)	O(1)
插入(已知值)	O(n)	O(n)	O(n)
删除(已知节点)	O(n)	O(1)	O(n)
删除(已知位置)	O(n)	O(n)	O(n)

6.应用场景选择

单链表适用场景

• 数据量不大，主要进行顺序访问
• 内存空间有限，需要较高存储密度
• 实现简单的动态数据结构

双向链表适用场景

• 需要频繁的双向遍历
• 需要高效的节点删除操作
• 实现复杂的数据结构（如LRU缓存）

循环链表适用场景

• 循环调度算法
• 约瑟夫环问题
• 循环缓冲区实现

7.总结

链表作为基础的动态数据结构，提供了灵活的内存管理和高效的插入删除操作。掌握链表的各种操作技巧，不仅有助于理解数据结构的本质，更为学习树、图等高级数据结构奠定了坚实基础。

在实际应用中，应根据具体需求选择合适的链表类型：追求存储效率时选择单链表，需要双向操作时选择双向链表，处理循环问题时使用循环链表。理解每种结构的特点和适用场景，才能在编程实践中做出最佳选择。