当前位置：首页 > news >正文

数据结构之双链表

news 来源：原创 2025/7/26 9:37:04

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 - 码云 - 开源中国

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 总结

相关文章：