目录
1 简介
2 双链表的基本概念
2.1 节点结构
2.2 头插法和尾插法
3 代码实现
4 代码解析（部分）
4.1 初始化双链表
4.2 添加节点
4.3 删除节点
4.4 获取节点
4.5 插入节点
4.6 反转链表
4.7 打印链表
4.8 核心操作分析
5 总结
1 简介
双向链表（Doubly Linked List）是一种链式存储结构，每个节点包含数据域和前驱、后继指针，支持双向遍历。本代码实现了双向链表的初始化、插入、删除、查找、反转等操作，并维护头尾指针以优化性能。相比单链表，双向链表在插入和删除时无需额外查找前驱节点，适用于频繁修改数据结构的场景，如缓存管理、文本编辑器等。
2 双链表的基本概念
2.1 节点结构
双向链表的每个节点包含：
-
数据域：存储数据
-
前驱指针（prev）：指向前一个节点
-
后继指针（next）：指向后一个节点
typedef struct node {int val; // 数据域struct node* prev; // 前驱指针struct node* next; // 后继指针
} DListNode;
2.2 头插法和尾插法
-
头插法：新节点插入链表头部，时间复杂度为 O(1)
-
尾插法：新节点插入链表尾部，需维护尾指针，时间复杂度为 O(1)
3 代码实现
// Dlink.c
// 双向链表
#include <stdio.h>
#include <stdlib.h>// 定义双链表节点
typedef struct node
{char data; // 数据域struct node *prev; // 指针域(前驱节点)struct node *next; // 指针域(后继节点)
} Node;// 定义双链表
typedef struct list
{struct node *head; // 头指针struct node *tail; // 尾指针int size; // 大小
} List;void init(List *list);
void add(List *list, char n);
void show(List *list);
void insert(List *list, int index, char n);
void insert2(Node *node, char n);
Node *get(List *list, int index);
void del(List *list, int index);
void reverse(List *list);int main(int argc, char const *argv[])
{List *list = malloc(sizeof(List));init(list);add(list, 'a');add(list, 'b');add(list, 'c');add(list, 'd');add(list, 'e');show(list);insert(list, 0, 'x');show(list);del(list, 5);show(list);reverse(list);show(list);return 0;
}// 反转链表
void reverse(List *list)
{Node *current = list->head->next; // 从第一个有效节点开始Node *prev = NULL;Node *next = NULL;list->tail = current; // 原头节点将成为新的尾节点while (current != NULL){next = current->next; // 保存下一个节点current->next = prev; // 反转当前节点的后继指针current->prev = next; // 反转当前节点的前驱指针prev = current; // 更新前一个节点为当前节点current = next; // 移动到下一个节点}list->head->next = prev; // 更新头节点的后继为新的头节点if (prev != NULL){prev->prev = list->head; // 更新新头节点的前驱为头节点}
}// 删除节点
void del(List *list, int index)
{if (index < 0 || index >= list->size) // 检查索引是否有效{return;}Node *node;if (index == 0) // 删除头节点的特殊情况{node = list->head->next;list->head->next = node->next;if (node->next != NULL){node->next->prev = list->head;}else{list->tail = list->head; // 如果删除的是唯一节点，更新尾指针}}else{node = get(list, index - 1); // 获取前驱节点Node *p = node->next;node->next = p->next;if (p->next != NULL){p->next->prev = node;}else{list->tail = node; // 如果删除的是尾节点，更新尾指针}node = p;}free(node);list->size--;
}// 获取节点
Node *get(List *list, int index)
{if (index < 0 || index >= list->size){return NULL;}if (index <= list->size / 2){Node *n = list->head;for (int i = 0; i <= index; i++){n = n->next;}return n;}else{Node *n = list->tail;for (int i = 1; i < list->size - index; i++){n = n->prev;}return n;}
}// 插入节点
void insert(List *list, int index, char n)
{Node *node = get(list, index ); // 获取要插入位置的前驱节点if (node == NULL){add(list, n);return;}Node *newN = malloc(sizeof(Node));newN->data = n;newN->prev = node->prev;newN->next = node;node->prev->next = newN;node->prev = newN;list->size++;
}// 插入节点
void insert2(Node *node, char n)
{Node *p = node->prev;Node *newN = malloc(sizeof(Node));newN->data = n;node->next = p->next;node->prev = p;p->next->prev = newN;p->next = newN;
}// 初始化双链表
void init(List *list)
{list->head = malloc(sizeof(Node));list->tail = malloc(sizeof(Node));list->tail = list->head; // 头尾指针指向同一个节点list->size = 0;
}// 添加节点
void add(List *list, char n)
{Node *node = malloc(sizeof(Node));node->data = n;node->prev = list->tail; // 新节点的前驱节点指向原来的尾节点node->next = NULL; // 新节点的后继节点指向空list->tail->next = node; // 新节点成为最后一个节点(尾指针)的后继节点list->tail = node; // 尾指针指向新节点list->size++;
}// 打印双链表
void show(List *list)
{printf("大小:%d\n", list->size);printf("链表:");Node *node = list->head->next;while (node != NULL){printf("->%c", node->data);node = node->next;}printf("\n");
}4 代码解析（部分）
4.1 初始化双链表
void init(List *list) {list->head = malloc(sizeof(Node)); // 为头节点分配内存list->tail = malloc(sizeof(Node)); // 为尾节点分配内存list->tail = list->head; // 头尾指针指向同一个节点，链表初始化为空list->size = 0; // 初始化链表大小为0
}
初始化双链表时，分配了头节点和尾节点的内存，并将头尾指针都指向同一个节点，表示链表为空，大小初始化为0。
4.2 添加节点
void add(List *list, char n) {Node *node = malloc(sizeof(Node)); // 为新节点分配内存node->data = n; // 将数据赋值给新节点node->prev = list->tail; // 新节点的前驱指向当前尾节点node->next = NULL; // 新节点的后继指针为NULLlist->tail->next = node; // 当前尾节点的后继指向新节点list->tail = node; // 更新尾指针指向新节点list->size++; // 更新链表大小
}
此函数向链表尾部添加一个新节点。首先为新节点分配内存，并设置数据域和前后指针。然后更新尾指针。
4.3 删除节点
void del(List *list, int index) {if (index < 0 || index >= list->size) { // 检查索引是否有效return;}Node *node;if (index == 0) { // 删除头节点的特殊情况node = list->head->next;list->head->next = node->next;if (node->next != NULL) {node->next->prev = list->head;} else {list->tail = list->head; // 删除唯一节点时更新尾指针}} else {node = get(list, index - 1); // 获取前驱节点Node *p = node->next;node->next = p->next;if (p->next != NULL) {p->next->prev = node;} else {list->tail = node; // 删除尾节点时更新尾指针}node = p;}free(node); // 释放删除节点的内存list->size--; // 更新链表大小
}
删除节点时，首先检查索引是否合法。删除头节点时直接更新头节点的 next，并更新尾节点指针（如果链表只剩一个节点）。删除其他节点时，获取前驱节点并更新前后节点的指针，释放节点内存并更新链表大小。
4.4 获取节点
Node *get(List *list, int index) {if (index < 0 || index >= list->size) {return NULL;}if (index <= list->size / 2) { // 优化：从头部开始遍历Node *n = list->head;for (int i = 0; i <= index; i++) {n = n->next;}return n;} else { // 优化：从尾部开始遍历Node *n = list->tail;for (int i = 1; i < list->size - index; i++) {n = n->prev;}return n;}
}
此函数根据给定索引获取节点。如果索引在链表的前半部分，则从头节点开始遍历；否则，从尾节点开始遍历，优化了查询性能。
4.5 插入节点
void insert(List *list, int index, char n) {Node *node = get(list, index); // 获取目标位置的前驱节点if (node == NULL) { // 如果目标位置无效，调用add函数add(list, n);return;}Node *newN = malloc(sizeof(Node)); // 为新节点分配内存newN->data = n; // 设置数据域newN->prev = node->prev; // 新节点的前驱指向目标节点的前驱newN->next = node; // 新节点的后继指向目标节点node->prev->next = newN; // 前驱节点的后继指向新节点node->prev = newN; // 目标节点的前驱指向新节点list->size++; // 更新链表大小
}
插入节点时，首先获取目标位置的前驱节点。如果目标位置无效，则调用 add 函数将新节点添加到尾部。否则，分配新节点并将其插入到指定位置，更新前后节点的指针，并增加链表大小。
4.6 反转链表
void reverse(List *list) {Node *current = list->head->next; // 从第一个有效节点开始Node *prev = NULL;Node *next = NULL;list->tail = current; // 原头节点成为新的尾节点while (current != NULL) {next = current->next; // 保存下一个节点current->next = prev; // 反转当前节点的后继指针current->prev = next; // 反转当前节点的前驱指针prev = current; // 更新前驱节点current = next; // 移动到下一个节点}list->head->next = prev; // 更新头节点的后继为新的头节点if (prev != NULL) {prev->prev = list->head; // 更新新头节点的前驱为头节点}
}
此函数通过反转链表中的每个节点的前后指针来实现链表的反转，最后更新头尾节点指针。
4.7 打印链表
void show(List *list) {printf("大小:%d\n", list->size); // 输出链表大小printf("链表:");Node *node = list->head->next; // 从头节点的下一个节点开始遍历while (node != NULL) {printf("->%c", node->data); // 输出节点的数据node = node->next; // 移动到下一个节点}printf("\n");
}
此函数遍历链表并打印每个节点的 data 字段，帮助显示链表的内容。
4.8 核心操作分析
5 总结
本文介绍了双向链表的基本概念及其在 C 语言中的实现，涵盖了链表的初始化、节点插入、删除、查找、反转等核心操作。双向链表相比单链表，能够支持双向遍历，具有更高的操作效率，特别是在插入和删除节点时不需要额外查找前驱节点。通过维护头尾指针，能够有效优化性能。通过对每个操作的详细解析，我们可以看到双向链表在动态数据结构中的应用价值，尤其在缓存管理、文本编辑等场景中，能够提高数据处理的灵活性和效率。
源码地址：0315/Dlink.c · jkh111/Niuer_C - 码云 - 开源中国
)