音乐网站建设费用,专业网站建设基本流程,网络托管运营,龙岩做网站公司在哪里目录引言#xff1a;打破“单行道”的束缚一、双向链表的核心节点操作1.插入操作2.删除操作二、构建双向循环链表三、双向循环链表C语言实现1.定义结构体与接口2.初始化链表3.核心辅助函数4.头插法5.尾插法6.展示链表7.删除链表中的节点8.销毁链表9.测试函数四、总结#xff…
目录引言打破“单行道”的束缚一、双向链表的核心节点操作1.插入操作2.删除操作二、构建双向循环链表三、双向循环链表C语言实现1.定义结构体与接口2.初始化链表3.核心辅助函数4.头插法5.尾插法6.展示链表7.删除链表中的节点8.销毁链表9.测试函数四、总结工程领域的“链表之王”引言打破“单行道”的束缚
在之前的探索中我们已经掌握了单向链表。但它有一个无法回避的痛点它是一条“单行道”。一旦我们从一个节点走向下一个那么就再也无法轻松地回头。这时候如果我们需要查找某个节点的前驱我们只能从头开始重新遍历一遍。
这种“一去不返”的特性让单向链表在许多需要灵活操作的工程场景中显得力不从心。我们不禁要问能不能为这条路开辟一条逆行车道让数据节点可以来去自如呢
答案是肯定的只需在每个节点中除了next指针外再添加一个指向前驱节点的prev指针。这样我们就构建了一条双向链表。
实际应用中我们多使用双向链表它即可往前又可往后的特点在进行操作时非常方便比如在删除元素的时候它不需要像单向链表一样找前置节点这是因为它的节点结构包含两个指针域在这个节点上就可以找到指向上一个节点的指针。 图1 双向链表的一个节点结构但普通的双向链表在进行尾插操作时依然会遇到与单向链表一样的问题从头一步步走到尾再进行插入。所以我们效仿单向链表的解决方法引入循环将双向链表的头尾相连构建出它的终极形态也是我们这篇文章的重点——双向循环列表。它几乎是工程应用中最常用、最强大的链表形态。
一、双向链表的核心节点操作
双向链表的节点中同时包含两个指针因此每次操作的时候都要注意处理好这两个指针。
1.插入操作
想象一下我们要在两个节点节点1和节点3之间插入一个新的节点new_node。如图2。 图2 待插入的链表和新节点对于插入操作为了方便我们首先给每个节点都放一个指针分别为prevnew_nodenext。 图3 为三个节点都赋予指针整个过程需要4个步骤来修改指针将new_node完美地接入到链表中。一个安全且不易出错的顺序是先处理新节点本身再修改原有链表。
new_node-prev prev; // 步骤①新节点的prev指向前驱节点。new_node-next next; // 步骤②新节点的next指向后继节点。prev-next new_node; // 步骤③前驱节点的next指向新节点。next-prev new_node; // 步骤④后继节点的prev指向新节点。
图4 新节点的prev指向前驱节点图5 新节点的next指向后继节点图6 前驱节点的next指向新节点图7 后继节点的prev指向新节点这个操作是所有插入头插、尾插、中插的核心。我们可以将它封装成一个函数便于调用
static void addDNode(DNode* new_node, DNode *prev, DNode* next)
{next-prev new_node;new_node-next next;new_node-prev prev;prev-next new_node;
}2.删除操作
对于删除一个节点节点2的操作则相对简单一些只需要让它的前驱节点1和后继节点3跳过节点2直接相连即可。
这个过程只需要2个步骤
prev-next next; // 步骤①前驱的next指向后继。next-prev prev; // 步骤②后继的prev指向前驱。
图8 删除节点2我们同样将其封装成函数
static void delDNode(DNode* prev, DNode* next)
{next-prev prev;prev-next next;
}二、构建双向循环链表
掌握了对节点的核心操作后我们来构建一个带头节点的双向循环链表。它的空链表形态是这样的头结点header的next和prev指针都指向它自己形成一个最小的闭环。 双向循环链表的带头节点的空链表如下图所示。 图9 带头节点的双向循环空链表在这个结构下我们将用到之前封装的addDNode函数
头插在 header 和 header-next (原第一个节点) 之间插入新节点。
insertHead(new_node, header, header-next)图10 带头节点的双向循环空链表头插示意图尾插在 header-prev (原最后一个节点) 和 header 之间插入新节点。
insertTail(new_node, header-prev, header)图10 带头节点的双向循环链表尾插示意图无论是头插还是尾插我们都调用了同一个核心函数区别只是传递不同的“前驱”和“后继”。这正是带头结点的循环结构带来的优雅与统一。
三、双向循环链表C语言实现
1.定义结构体与接口
#include stdio.h
#include stdlib.htypedef int Element;
typedef struct _node {Element val;struct _node *next;struct _node *prev;
} DNode, DList; // 我们起了两个别名防止理解错误/* 使用一个带头节点的双向循环链表头节点让用户来管理提供初始化接口 */
void initDList(DList *header);
void releaseDList(DList *header);// 实现头插、尾插
void insertDListHeader(DList *header, Element val);
void insertDListRear(DList *header, Element val);
// 显示链表
void showDList(const DList *header);
// 删除一个元素
void deleteDList(DList *header, Element e);2.初始化链表
void initDList(DList* header)
{header-val 0;header-next header-prev header;
}3.核心辅助函数
// 核心插入函数 (static表示为内部使用)
static void addDNode(DNode* new_node, DNode *prev, DNode* next)
{new_node-prev prev;new_node-next next;prev-next new_node;next-prev new_node;
}// 核心删除函数 (static表示为内部使用)
static void delDNode(DNode* prev, DNode* next)
{prev-next next;next-prev prev;
}4.头插法
void insertDListHeader(DList *header, Element val)
{DNode *new_node malloc(sizeof(DNode));new_node-val val;addDNode(new_node,header, header-next);header-val;
}5.尾插法
void insertDListRear(DList *header, Element val)
{DNode *new_node malloc(sizeof(DNode));new_node-val val;addDNode(new_node, header-prev, header);header-val;
}6.展示链表
void showDList(const DList *header)
{DNode *pos header-next;printf(show:);while (pos ! header){printf(%d\t, pos-val);pos pos-next;}printf(\n);
}7.删除链表中的节点
void deleteDList(DList *header, Element e)
{// 1.找到这个元素就可以删除不需要再找到前置节点DNode *pos header-next;while (pos ! header pos-val ! e){pos pos-next;}// 2.找到没有if (pos ! header){delDNode(pos-prev, pos-next);pos-next pos-prev NULL;free(pos);--header-val;} else{printf(Not find %d element!\n,e);}
}8.销毁链表
void releaseDList(DList* header)
{DNode *pos header-next;DNode *tmp NULL;while (pos ! header){tmp pos;delDNode(pos-prev, pos-next);pos pos-next;free(tmp);--header-val;}
}9.测试函数
DList stu_table; // 创建一个DList类型的全局变量stu_table
int main()
{initDList(stu_table);for (int i 0; i 5; i){//insertDListHeader(stu_table, i 100);insertDListRear(stu_table, i 100);}insertDListHeader(stu_table, 60);insertDListHeader(stu_table, 80);showDList(stu_table);printf(\n);deleteDList(stu_table, 102);showDList(stu_table);releaseDList(stu_table);printf(num:%d\n,stu_table.val);return 0;
}结果为
四、总结工程领域的“链表之王”
至此我们已经掌握了双向循环链表。虽然每个节点都增加了一个指针带来了额外的内存开销但它换来的是无与伦比的操作便利性
双向遍历既能从前到后也能从后到前。O(1)复杂度的两端操作无论是头插、头删还是尾插、尾删都快如闪电。O(1)复杂度的邻居节点查找给定任意一个节点都能立刻找到其前驱和后驱。
正是这些强大的特性使得双向循环链表在实际工程中备受青睐成为许多底层库和系统的实现基础例如著名的 Linux 内核中的list_head就是一个经典的双向循环链表实现。
我们的线性结构探索之旅到这里就告一段落了。从最简单的顺序表到最灵活强大的双向循环链表我们一步步见证了数据结构为了应对不同挑战而进行的精妙演化。接下来我们将迈入一个全新的维度探索更加复杂和强大结构比如“栈”和“队列”。
