数据结构02-双向链表

一、双向链表的定义与结构① 双向链表Doubly Linked List是一种每个节点都包含两个指针一个指向前驱节点一个指向后继节点的线性数据结构。② 双向链表是一种链表其中每个节点都包含三个部分数据域data存储数据前驱指针prev指向前一个节点后继指针next指向后一个节点③ 单向链表无法通过当前结点访问前驱结点双向链表增加指向前驱结点的指针域即可从前向后遍历也可从后向前遍历④ 双向链表的核心特点特点说明动态大小不需要预先分配固定内存节点按需创建理论上只受限于系统内存总量。非连续存储节点在内存中可分散在任意位置通过前后指针链接能有效利用内存碎片。双向访问每个节点同时持有前驱和后继指针既可以从前往后遍历也能从后往前回溯不需要从头开始查找前驱节点。插入/删除更灵活在已知插入/删除位置持有对应节点指针的情况下插入和删除只需修改前后指针时间复杂度O(1)相比单向链表不需要额外遍历找前驱操作更方便。随机访问低效要访问第 i 个节点仍然必须从头/尾开始遍历时间复杂度 O(n)。空间开销稍大每个节点需要额外存储一个前驱指针相比同节点数量的单向链表会多消耗一部分指针存储空间。二、双向链表的实现2.1 链表结点类型和链表对象类型定义声明//链表中存储的数据类型 typedef struct stu { int id; char name[32]; int score; }DataType_t; //链表结点类型 typedef struct dnode { DataType_t data; //双向链表存储的数据 struct dnode *ppre; //指向前驱结点的指针 struct dnode *pnext; //指向后继结点的指针 }DNode_t; //双向链表对象类型 typedef struct dlink { DNode_t *phead; //头结点指针 int clen; //当前结点个数 }DLink_t;2.2 创建双向链表对象//创建双向链表对象 DLink_t *create_doulink() { //使用 malloc 动态分配 DLink_t 大小的内存 DLink_t *pdlink malloc(sizeof(DLink_t)); if (NULL pdlink) //检查内存分配是否成功 { printf(malloc error\n); return NULL; } pdlink-phead NULL; //头指针置空表示链表为空 pdlink-clen 0; //链表长度为0表示没有节点 return pdlink; //返回初始化好的链表管理结构体指针 }2.3 创建双向链表节点//创建双向链表新节点 DNode_t *create_node(DataType_t data) { //使用 malloc 在堆区动态分配一个节点所需的内存 DNode_t *pnode malloc(sizeof(DNode_t)); if (NULL pnode) //检查分配是否成功 { printf(malloc error\n); return NULL; } pnode-data data; //将传入的数据存储到节点的数据域 pnode-pnext NULL; //将后继指针置空 pnode-ppre NULL; //将前驱指针置空 return pnode; }2.4 判断双向链表是否为空int is_empty_dlink(DLink_t *pdlink) { if (NULL pdlink-phead) //访问链表管理结构体中的头节点指针 { return 1; //表示链表为空 } return 0; //表示链表不为空 }2.5 遍历双向链表遍历方向 //dir 1非0正向遍历从头到尾 //dir 0反向遍历从尾到头 void show_doulink(DLink_t *pdlink, int dir) { if(is_empty_dlink(pdlink)) //判断链表是否为空 { return ; } DNode_t *ptmp pdlink-phead; //创建临时指针ptmp指向链表头节点 if (dir) //dir 为真非0 { while (ptmp) //ptmp 不为 NULL { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-pnext; } } else //dir 0 { while (ptmp-pnext) { ptmp ptmp-pnext; //移动到尾节点 } while (ptmp) //从尾到头遍历 { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-ppre; //通过 ppre 向前移动 } } printf(\n); }2.6 双向链表插入数据头插法//双向链表的头部插入一个新节点 int insert_doulink_head(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); //调用 create_node() 创建新节点并初始化 if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) //如果链表为空直接将新节点设为头节点 { pdlink-phead pnode; } else { pnode-pnext pdlink-phead; //新节点的 pnext 指向原来的头节点 pdlink-phead-ppre pnode; //原头节点的 ppre 指向新节点 pdlink-phead pnode; //更新头指针 } pdlink-clen; //更新链表长度 return 0; }2.7 双向链表插入数据尾插法int insert_doulink_tail(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); if (NULL pnode) { return -1; } DNode_t *ptmp pdlink-phead; //创建临时指针指向头节点 if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { while (ptmp-pnext ! NULL) //遍历找到尾节点 { ptmp ptmp-pnext; } ptmp-pnext pnode; //原尾节点的 pnext 指向新节点 pnode-ppre ptmp; //新节点的 ppre 指向原尾节点 } pdlink-clen; //更新链表长度 return 0; }2.8 双向链表删除数据头删法int delete_doulink_head(DLink_t *pdlink) { if (is_empty_dlink(pdlink)) // 判断链表是否为空 { return -1; } DNode_t *ptmp pdlink-phead; //创建临时指针ptmp 保存当前头节点的地址 pdlink-phead ptmp-pnext; //将头指针指向原头节点的下一个节点 if (ptmp-pnext ! NULL) //检查原头节点是否有下一个节点 { //将新头节点的 ppre 设为 NULL确保新头节点的前驱为空 ptmp-pnext-ppre NULL; } free(ptmp); //释放原头节点占用的内存防止内存泄漏 pdlink-clen--; //更新链表长度 return 0; }2.9双向链表删除数据尾删法int delete_doulink_tail(DLink_t *pdlink) { if (is_empty_dlink(pdlink)) //判断链表是否为空 { return -1; } DNode_t *ptmp pdlink-phead; while (ptmp-pnext ! NULL) //遍历找到尾节点 { ptmp ptmp-pnext; } if (ptmp-ppre ! NULL) { ptmp-ppre-pnext NULL; //将前驱节点的 pnext 设为 NULL } else { //链表只有一个节点将头指针设为 NULL链表变为空 pdlink-phead NULL; } free(ptmp); //释放尾节点占用的内存 pdlink-clen--; return 0; }2.10 双向链表中根据指定数据查找匹配的节点//双向链表中根据姓名查找匹配的节点 DNode_t *find_doulink(DLink_t *pdlink, char *name) { DNode_t *ptmp pdlink-phead; //创建临时指针指向头节点 while (ptmp ! NULL) { if (0 strcmp(ptmp-data.name, name)) //比较两个字符串 { return ptmp; //找到匹配节点立即返回该节点指针 } ptmp ptmp-pnext; } return NULL; }2.11 双向链表中根据指定数据查找节点并更新该节点的数据//双向链表中根据姓名查找节点并更新该节点的成绩。 int change_doulink(DLink_t *pdlink, char *name, int score) { //创建临时指针并初始化为 NULL用于接收 find_doulink 的返回值 DNode_t *ptmp NULL; //调用 find_doulink 函数在链表中查找指定姓名的节点 ptmp find_doulink(pdlink, name); if (ptmp ! NULL) { ptmp-data.score score; //修改节点的成绩 return 0; } return -1; }2.12双向链表中删除指定结点//根据姓名删除指定节点的函数 int delete_point_node(DLink_t *pdlink, char *name) { if (is_empty_dlink(pdlink)) //检查链表是否为空 { return -1; } DNode_t *ptmp NULL; //创建临时指针并初始化为 NULL ptmp find_doulink(pdlink, name); //调用 find_doulink 查找指定姓名的节点 if (NULL ptmp) { return -1; } if (NULL ptmp-ppre) //删除的是头节点 { delete_doulink_head(pdlink); } else if (NULL ptmp-pnext) //删除的是尾节点 { delete_doulink_tail(pdlink); } else { ptmp-ppre-pnext ptmp-pnext; //前驱节点跳过 ptmp 指向后继 ptmp-pnext-ppre ptmp-ppre; //后继节点跳过 ptmp 指向前驱 pdlink-clen--; free(ptmp); } return 0; } 删除中间节点 删除前 [头A] ⇄ [B] ⇄ [C] ⇄ [D尾] ptmp C (要删除) 执行步骤 1. ptmp-ppre-pnext ptmp-pnext B-pnext D 2. ptmp-pnext-ppre ptmp-ppre D-ppre B 删除后 [头A] ⇄ [B] ⇄ [D尾] (C节点被跳过但内存未释放)2.13 释放双向链表void destroy_doulink(DLink_t *pdlink) { while (!is_empty_dlink(pdlink)) //链表不为空 { delete_doulink_head(pdlink); } free(pdlink); }三、其他链表介绍3.1循环链表① 循环链表是链表的一种特殊形式其中最后一个节点的指针不是指向NULL而是指向第一个节点头节点形成一个环状结构。② 循环链表分类1单向循环链表每个节点只有一个指针域pnext尾节点的pnext指向头节点只能单向遍历2双向循环链表每个节点有两个指针域pnext和ppre头节点的ppre指向尾节点尾节点的pnext指向头节点可以双向遍历③ 循环链表的优缺点1优点任意节点都可作为起点没有NULL指针遍历方便适合实现循环队列约瑟夫环等问题的理想数据结构2缺点遍历时容易死循环需要判断终止条件实现比普通链表复杂空链表判断特殊调试相对困难3.2 有环链表① 有环链表部分环是指链表中存在一个环Cycle即从某个节点开始沿着指针域next指针不断前进最终会回到这个节点形成一个闭环3.3 内核链表① 内核链表Linux Kernel Linked List是Linux内核中一种经典且强大的数据结构。它的核心设计理念是“侵入式”Intrusive。② 传统链表在节点中直接包含数据指针而内核链表的思路恰恰相反它定义了一个纯粹的、不包含数据域的双向循环链表结构struct list_head然后将这个结构嵌入到我们自定义的数据结构内部。四、附件代码① doulink.h#ifndef __DOULINK_H__ #define __DOULINK_H__ //链表中存储的数据类型 typedef struct stu { int id; char name[32]; int score; }DataType_t; //链表结点类型 typedef struct dnode { DataType_t data; //双向链表存储的数据 struct dnode *ppre; //指向前驱结点的指针 struct dnode *pnext; //指向后继结点的指针 }DNode_t; //双向链表对象类型 typedef struct dlink { DNode_t *phead; //头结点指针 int clen; //当前结点个数 }DLink_t; extern DLink_t *create_doulink(); extern DNode_t *create_node(DataType_t data); extern int insert_doulink_head(DLink_t *pdlink, DataType_t data); extern void show_doulink(DLink_t *pdlink, int dir); extern int insert_doulink_tail(DLink_t *pdlink, DataType_t data); extern int delete_doulink_tail(DLink_t *pdlink); extern int delete_doulink_head(DLink_t *pdlink); extern void destroy_doulink(DLink_t *pdlink); extern int change_doulink(DLink_t *pdlink, char *name, int score); extern DNode_t *find_doulink(DLink_t *pdlink, char *name); extern int delete_point_node(DLink_t *pdlink, char *name); #endif②doulink.c#include doulink.h #include stdio.h #include stdlib.h #include string.h DLink_t *create_doulink() { DLink_t *pdlink malloc(sizeof(DLink_t)); if (NULL pdlink) { printf(malloc error\n); return NULL; } pdlink-phead NULL; pdlink-clen 0; return pdlink; } DNode_t *create_node(DataType_t data) { DNode_t *pnode malloc(sizeof(DNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } pnode-data data; pnode-pnext NULL; pnode-ppre NULL; return pnode; } int is_empty_dlink(DLink_t *pdlink) { if (NULL pdlink-phead) { return 1; } return 0; } int insert_doulink_head(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { pnode-pnext pdlink-phead; pdlink-phead-ppre pnode; pdlink-phead pnode; } pdlink-clen; return 0; } void show_doulink(DLink_t *pdlink, int dir) { if(is_empty_dlink(pdlink)) { return ; } DNode_t *ptmp pdlink-phead; if (dir) { while (ptmp) { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-pnext; } } else { while (ptmp-pnext) { ptmp ptmp-pnext; } while (ptmp) { printf(%d %s %d\n, ptmp-data.id, ptmp-data.name, ptmp-data.score); ptmp ptmp-ppre; } } printf(\n); } int insert_doulink_tail(DLink_t *pdlink, DataType_t data) { DNode_t *pnode create_node(data); if (NULL pnode) { return -1; } DNode_t *ptmp pdlink-phead; if (is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext pnode; pnode-ppre ptmp; } pdlink-clen; return 0; } int delete_doulink_head(DLink_t *pdlink) { if (is_empty_dlink(pdlink)) { return -1; } DNode_t *ptmp pdlink-phead; pdlink-phead ptmp-pnext; if (ptmp-pnext ! NULL) { ptmp-pnext-ppre NULL; } free(ptmp); pdlink-clen--; return 0; } int delete_doulink_tail(DLink_t *pdlink) { if (is_empty_dlink(pdlink)) { return -1; } DNode_t *ptmp pdlink-phead; while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } if (ptmp-ppre ! NULL) { ptmp-ppre-pnext NULL; } else { pdlink-phead NULL; } free(ptmp); pdlink-clen--; return 0; } void destroy_doulink(DLink_t *pdlink) { while (!is_empty_dlink(pdlink)) { delete_doulink_head(pdlink); } free(pdlink); } DNode_t *find_doulink(DLink_t *pdlink, char *name) { DNode_t *ptmp pdlink-phead; while (ptmp ! NULL) { if (0 strcmp(ptmp-data.name, name)) { return ptmp; } ptmp ptmp-pnext; } return NULL; } int change_doulink(DLink_t *pdlink, char *name, int score) { DNode_t *ptmp NULL; ptmp find_doulink(pdlink, name); if (ptmp ! NULL) { ptmp-data.score score; return 0; } return -1; } int delete_point_node(DLink_t *pdlink, char *name) { if (is_empty_dlink(pdlink)) { return -1; } DNode_t *ptmp NULL; ptmp find_doulink(pdlink, name); if (NULL ptmp) { return -1; } if (NULL ptmp-ppre) { delete_doulink_head(pdlink); } else if (NULL ptmp-pnext) { delete_doulink_tail(pdlink); } else { ptmp-ppre-pnext ptmp-pnext; ptmp-pnext-ppre ptmp-ppre; pdlink-clen--; } return 0; }③ main.c#include doulink.h #include stdio.h int main(int argc, const char *argv[]) { DLink_t *pdlink NULL; pdlink create_doulink(); if (NULL pdlink) { return -1; } DataType_t s[] {{1, zhangsan, 90}, {2, lisi, 100}, {3, wanger, 68}, {4, maliu, 78}, {5, zhaowu, 67}, {6, tianqi, 89}}; insert_doulink_head(pdlink, s[0]); insert_doulink_head(pdlink, s[1]); insert_doulink_head(pdlink, s[2]); insert_doulink_head(pdlink, s[3]); insert_doulink_tail(pdlink, s[4]); insert_doulink_tail(pdlink, s[5]); show_doulink(pdlink, 1); show_doulink(pdlink, 0); delete_doulink_head(pdlink); delete_doulink_tail(pdlink); delete_point_node(pdlink, lisi); show_doulink(pdlink, 1); show_doulink(pdlink, 0); change_doulink(pdlink, wanger, 100); show_doulink(pdlink, 1); show_doulink(pdlink, 0); destroy_doulink(pdlink); return 0; }