数据结构 - 双向链表

双向链表定义

双向链表的节点包含数据域和两个指针域（前驱指针prev、后继指针next），结构定义如下：

typedef int data_t; typedef struct node { data_t data; // 数据域 struct node *next; // 后继指针（指向后一个节点） struct node *prev; // 前驱指针（指向前一个节点） } node_t;

核心操作及实现思路

创建--增（插入）--删--改--查--销毁

创建双向链表（初始化头节点）

功能：创建空的双向链表，头节点的prev和next均设为NULL。

node_t *creat_doublist(void) { node_t *phead = (node_t *)malloc(sizeof(node_t)); phead->prev = NULL; phead->next = NULL; return phead; }

判断链表是否为空

//判断是否为空的函数 int is_empty(node_t *phead) { return phead->next == NULL && phead->prev == NULL; } // int doublist_print(node_t *phead) { if(phead == NULL) { return -1; } node_t *p = phead->next; while(p!=NULL) //尾节点也需要打印，Ｐ要走到ＮＵＬＬ { printf("%d ",p->data); p = p->next; } putchar('\n'); return 0; }

插入操作

双向链表的插入需注意前驱和后继指针的双向维护，分为头插和尾插。

头插法（在链表头部插入新节点）

步骤：

• 创建新节点p_new，填充数据。
• 调整指针（保证双向链接）：
  • p_new->next = phead->next（新节点的后继指向原头节点的下一个节点）
  • p_new->prev = phead（新节点的前驱指向头节点）
  • phead->next = p_new（头节点的后继指向新节点）
  • 若原头节点有后继（p_new->next != NULL），则p_new->next->prev = p_new（原后继节点的前驱指向新节点）

void doublist_insert_head(node_t *phead, data_t data) { node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->next = phead->next; p_new->prev = phead; phead->next = p_new; if (p_new->next != NULL) { p_new->next->prev = p_new; } }

尾插法（在链表尾部插入新节点）

步骤：

• 创建新节点p_new，填充数据。
• 找到链表的尾节点（遍历至p->next == NULL的节点）。
• 调整指针：
  • p_new->next = p->next（新节点的后继设为NULL，因为尾插后新节点是尾）
  • p_new->prev = p（新节点的前驱指向原尾节点）
  • p->next = p_new（原尾节点的后继指向新节点）

遍历操作

• 正向遍历：从head节点的next开始，依次访问next指针，直到NULL。
• 逆向遍历（逆序打印）：从尾节点开始，通过prev指针反向访问，直到回到head节点。

查找操作

功能：根据给定值data，在链表中查找节点。

node_t *doublist_find_key(node_t *phead, data_t data) { node_t *p = phead->next; while (p != NULL) { if (p->data == data) { return p; } p = p->next; } return NULL; }

修改操作

功能：将链表中值为old的节点，修改为new。

node_t *doublist_update_key(node_t *phead, data_t old, data_t new) { node_t *p = doublist_find_key(phead, old); if (p != NULL) { p->data = new; } return p; }

长度统计

功能：统计链表中有效节点（不含头节点）的个数。

int length(node_t *phead) { int count = 0; node_t *p = phead->next; while (p != NULL) { count++; p = p->next; } return count; }

销毁操作（可选但重要）

功能：释放链表所有节点的内存（包括头节点）。

void destroy_doublist(node_t *phead) { node_t *p = phead; while (p != NULL) { node_t *temp = p; p = p->next; free(temp); } }

双向链表的特点

• 优点：支持双向遍历（可从前向后、从后向前），插入/删除时可快速定位前驱和后继，操作更灵活。
• 缺点：每个节点多一个指针域，空间开销略大；插入/删除时需维护两个方向的指针，代码复杂度稍高。

示例：头插法完整代码

#include <stdio.h> #include <stdlib.h> typedef int data_t; // 假设数据类型为int typedef struct node { data_t data; struct node *next; struct node *prev; } node_t; // 创建空双向链表 node_t *creat_doublist(void) { node_t *phead = (node_t *)malloc(sizeof(node_t)); phead->prev = NULL; phead->next = NULL; return phead; } // 头插法插入节点 void doublist_insert_head(node_t *phead, data_t data) { node_t *p_new = (node_t *)malloc(sizeof(node_t)); p_new->data = data; p_new->next = phead->next; p_new->prev = phead; phead->next = p_new; if (p_new->next != NULL) { p_new->next->prev = p_new; } } // 遍历打印（正向） void print_doublist(node_t *phead) { node_t *p = phead->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { node_t *phead = creat_doublist(); doublist_insert_head(phead, 1); doublist_insert_head(phead, 2); doublist_insert_head(phead, 3); print_doublist(phead); // 输出：3 2 1 destroy_doublist(phead); return 0; }