数据结构 - 双向链表

双向链表定义双向链表的节点包含数据域和两个指针域前驱指针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; }