数据结构：线性双链表详解（C语言实现）

线性双链表详解（C语言实现）

线性双链表（双向链表）是一种基础且强大的数据结构，每个节点包含前驱指针（prev）、后继指针next）和数据域。它支持双向遍历，插入和删除操作更高效，尤其适用于频繁修改的场景。

🔧 一、双链表的结构设计

双链表节点由数据域和两个指针组成：

typedef struct DNode { int data;  // 数据域（以int为例，可自定义） struct DNode* prev; // 指向前驱节点 struct DNode* next; // 指向后继节点} DNode, *DLinkedList;

• 头节点与尾节点：头节点的prev指向NULL，尾节点的next指向NULL，标识链表边界。

⚙️ 二、核心操作实现（C语言）

1. 初始化双链表

创建空链表时初始化头尾节点：

DLinkedList initList() { DNode* head = (DNode*)malloc(sizeof(DNode)); head->prev = NULL; head->next = NULL; return head;}

2. 插入节点

• 头插法：新节点插入链表头部

void insertAtHead(DLinkedList* L, int data) { DNode* newNode = (DNode*)malloc(sizeof(DNode)); newNode->data = data; newNode->prev = NULL; newNode->next = *L; if (*L != NULL) { (*L)->prev = newNode; // 原头节点的prev指向新节点 } *L = newNode;  // 更新头指针}

• 尾插法：新节点插入链表尾部

void insertAtTail(DLinkedList L, int data) { DNode* newNode = (DNode*)malloc(sizeof(DNode)); newNode->data = data; newNode->next = NULL; if (*L == NULL) { *L = newNode; newNode->prev = NULL; return; } DNode* tail = *L; while (tail->next != NULL) { // 定位尾节点 tail = tail->next; } tail->next = newNode; newNode->prev = tail; // 新节点的prev指向原尾节点}

• 指定位置插入：在节点p后插入

void insertAfter(DNode* p, int data) { if (p == NULL) return; DNode* newNode = (DNode*)malloc(sizeof(DNode)); newNode->data = data; newNode->next = p->next; newNode->prev = p; if (p->next != NULL) { p->next->prev = newNode; // 原后继节点的prev指向新节点 } p->next = newNode; // p的next指向新节点}

3. 删除节点

• 删除头节点：

void deleteHead(DLinkedList* L) { if (*L == NULL) return; DNode* temp = *L; *L = (*L)->next; if (*L != NULL) { (*L)->prev = NULL; // 新头节点的prev置空 } free(temp);}

• 删除尾节点：

void deleteTail(DLinkedList L) { if (*L == NULL) return; DNode* tail = *L; while (tail->next != NULL) { tail = tail->next; } if (tail->prev != NULL) { tail->prev->next = NULL; // 新尾节点的next置空 } free(tail);}

• 删除指定节点：

void deleteNode(DNode* node) { if (node == NULL) return; if (node->prev != NULL) { node->prev->next = node->next; // 前驱节点跳过当前节点 } if (node->next != NULL) { node->next->prev = node->prev; // 后继节点跳过当前节点 } free(node);}

4. 遍历操作

• 正向遍历（头→尾）：

void traverseForward(DLinkedList L) { DNode* current = L; while (current != NULL) { printf(\"%d \", current->data); current = current->next; }}

• 反向遍历（尾→头）：

void traverseBackward(DLinkedList L) { DNode* tail = L; while (tail->next != NULL) { // 先定位尾节点 tail = tail->next; } while (tail != NULL) { printf(\"%d \", tail->data); tail = tail->prev; }}

📊 三、双链表的优缺点分析

🔍 四、应用场景

1. 操作系统：进程调度队列（快速增删）。
2. 数据库索引：B+树叶子节点双向链接（范围查询）。
3. LRU缓存淘汰：链表尾部表示最少使用数据。
4. 文本编辑器：撤销/重做操作的历史记录栈。

🧠 五、常见问题与陷阱

1. 内存泄漏：删除节点后未释放内存 → 需严格配对malloc/free。
2. 断链问题：插入/删除时未更新相邻节点的指针 → 务必检查边界（头/尾）。
3. 空指针解引用：操作前检查node->next或node->prev是否为NULL。

💻 六、完整代码示例

#include #include // 节点结构定义typedef struct DNode { int data;  // 数据域（以int为例，可自定义） struct DNode* prev; // 指向前驱节点 struct DNode* next; // 指向后继节点} DNode, *DLinkedList;// 初始化、插入、删除、遍历函数（函数见上文二）int main() { DLinkedList list = initList(); insertAtTail(&list, 10); insertAtHead(&list, 20); insertAfter(list, 30); // 在头节点后插入30 traverseForward(list); // 输出: 20 30 10 deleteNode(list->next); // 删除30 return 0;}

📝 总结

线性双链表通过牺牲空间换取操作效率，成为动态数据管理的利器。核心在于指针的精确维护，尤其在边界处理时需格外谨慎。掌握双链表能为学习更复杂结构（如跳表、平衡树）奠定基础。