数据结构之线性表-双循环链表-学习笔记-27

引入

我们介绍了单链表、介绍了将单链表头尾相连组成循环链表，又讲了循环链表中一些有趣得应用，现在是时候了解线性表中的大拿，双循环链表了。

为什么需要双链表

在单循环链表中，链表中的各个节点是这样的，一个结点指向下一个结点

A -> B -> C -> D -> E -> F

如果我们需要从 A 到达 D 结点，那么需要

A -> B -> C -> D

如果到了 D 之后，有需要到 C，那么就麻烦了

D -> E -> F -> A -> B -> C

明明相邻得两个结点，为什么要转一圈才能找到彼此呢？
答案很简单，因为结点都是向后指的，单循环链表嘛~
而解决这个问题的答案更简单，那我们就把结点
既指向它的前驱节点，也指向它的后继节点不就好了~
这就是双向链表。

双向链表

我们定义一个双向链表的结构体

typedef struct DualNode{
ElemType data;
struct DulaNode *prior;  //前驱结点
struct DulaNode *next;  //后继结点
};

我们观察到，再定义一个双链表时，在指针域，除了单链表的next指针外，还有一个prior 指针，我们称：

• Prior 指针：指向前驱结点的指针，指向前一个结点；
• Next 指针：指向后继结点的指针，指向后一个结点；

双向循环链表

既然单链表有循环链表，那么双链表同样也有循环链表。

在双向循环链表中

• 头结点的前驱是尾节点的地址
• 头结点的后继是头结点的下一个地址
• 尾结点的前驱是尾节点的前一个地址
• 尾结点的后继是头节点的地址

跟单循环链表一样，头尾相连即可。

双链表插入结点

因为链表的结点多了一个前驱节点，我们在执行插入的时候会带来哪些变化和注意事项呢？还是那句话，顺序最重要！

• 最终的要记住，先操作新的，再操作旧的，先新后旧。
• 新结点的后继指向前一结点的后继
• 新节点的前驱指向前一结点
• 前一结点后继的前驱指向新结点
• 前一结点的后继指向新结点

代码实现

S 为要插入的新节点，P 为前一结点

s->next=p->next;  //新的后继为前结点的后继
s->prior=>p;          // 新的前驱为前结点
p->next->prior=s; // 前结点的后继的前驱为新节点
p->next=s;            //前结点的后继为新结点

顺序就是：新的后继，新的前序，前的后继的前驱，前的后继。

双链表删除结点

删除结点还是比较好操作的，就是跨过当前节点

• 前驱的后继等于删除结点的后继
• 后继的前驱等于删除结点的前驱

也就是说，我们不操作要删除的结点本身，而是让前驱和后继相连，从而跳过当前结点。

总结

其实双链表比单链表多的就是 prior 指针，prior 的出现，需要在创建、插入和删除的时候注意顺序，一定要格外小心。
不过还记得前面我们要从 D 结点到前一结点 C 的例子吗？双链表的出现其实就是在用空间换取时间。用多存储一倍的指针地址，达到快速移动结点的效果。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。