引入

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

为什么需要双链表

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

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

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

A -> B -> C -> D

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

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

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

发刊词

数学不好，加上有点强迫症，而又需要或者想学习数学的成年人。这是一个真正的给成年人看的低等数学，这是真的零基础，我们将从幼儿园的等级出发。你将以一个成年人的智慧，来重新看待这些「恼人的数学」，愿你我重新找回数学的乐趣。

引入

我们知道，数学最基础的是由数组成的，那么对于数你又知道多少呢？今天我们看看与数有关的基础知识。

阿拉伯数字

我们将现在使用的数字，称为阿拉伯数字

0 1 2 3 4 5 6 7 8 9

我们可以将这些数字从1数到9，例如下面的 # 号

1：#
2：# #
3：# # #
4：# # # #
5：# # # # #
6：# # # # # #
7：# # # # # # #
8：# # # # # # # #
9：# # # # # # # # #

引入

我们学习了这么多单循环链表的知识，那么该如何运用到生活中呢？或者该如何灵活的使用这些单循环链表的知识呢？

魔术师发牌问题

大概的情景是这样得

• 13张牌

• 从1~13，A~K

• 数一张，放下是 A，把 A 放桌面上

• 数两张，第一张放到牌堆最下面，第二张放下是2 ，把2放桌面上

• 数三张，第一张、第二张放到牌堆最下面，第三张放下是3 ，把3放桌面上

• 以此类推，所有13张牌都发完，桌面上正好是A~K

  大概思路

  • 跟约瑟夫问题类似
  • 移动指针，找到牌
  • 删除结点，重新构成链表
  • 再次移动指针，找到出牌顺序
  • 赋值 A~K，顺序输出即可

引入

上一节，我们学习了尾指针，并且利用尾指针。尾指针可以轻松的操作头结点和尾结点，可以将两个单循环链表组成了一个单循环链表，我们今天再看看，尾指针还有什么其它玩法。

单链表中的环

首先要明白，单链表有环的状态是什么样子得

其实就是，尾指针指向了链表中的某个结点。

如何判断单链表中是否有环

方法 1

• 设置 p 、q 两个指针
• p 向前走，q 从头走，p 向前走尾部应该会到 NULL。
• 每个结点，p 走的步数应该和 q 一样
• 如果不一样，就像上面的图，p 的地址等于 q
• 但是，p 走到3用了6步，q 则用了2步
• 步数不相等，那么就存在环

方法 2

• 设置 p 、q 两个指针
• p 每走一步，q 就走两步，快慢指针
• 快指针应该很快到 NULL
• 如果 p==q 了，则存在环

引入

我们学习了循环链表的基本操作，也学习了一个有趣的约瑟夫问题，我们之前说过有头指针也有尾指针，头指针指向头结点，尾指针指向尾结点。那么尾指针有哪些有趣的用法呢？

单循环链表的问题

我们知道，在单向循环链表中，我们有头指针

• O ( 1 ) 的时间去找到第一个结点，因为 next 就是头结点
• O ( n ) 的时间去找最后一个结点，因为第 n 个才是尾结点

如何在访问头结点和尾结点得时候，都是O( 1 )时间复杂度呢？

尾指针应运而生！

• 尾指针指向的是尾节点
• 而尾节点得下一个就是头结点

所以尾指针访问头结点和尾节点的时间都是 O ( 1 ) 。
撒花~~~

尾指针

引入

罗马占领乔塔帕特之后，39个犹太人与 Joseph 及1个朋友躲进山洞避难，39个人宁死也不愿意被敌人抓到，决定了一种自杀方式：

• 41 个人排成一个圆圈（39个犹太人 + Joseph + 1 个朋友）
• 第 1 个人开始报数，每报数到第3人，这个人就自杀
• 然后再从下一个，也就是原来的第 4 人开始，数到第 3 人自杀
• 直到所有人都自杀身亡为止

但是 Joseph 和朋友并不想死，所以就有如下那排

• 朋友去了 16 号
• Joseph 去了 31 号
• 于是，逃过了死亡游戏

约瑟夫问题

那么这个有趣得约瑟夫和朋友逃难的问题跟我们得循环链表有什么关系呢？我们想用计算机帮助我们把41个人的自杀编号输出出来：

代码实现

引入

我们讲了顺序存储结构、单链表、静态链表，今天我们学习一种新的链表，单循环链表，单循环链表很简单，其实就是在单链表的基础上，将头尾相连，形成一个单向环装循环。

单循环链表

我们知道，单链表非常有趣，虽然不连续，但却根据指针一个连着一个，但是单链表有一个问题，我们如果不从头结点出发，就无法访问所有结点。
解决方法也非常简单，就是把链表终端结点得指针由 NULL 改成指向头结点。也就是链表最后一个结点存储得指针为头结点得指针，也就是原来 head 存储的地址。
既然head 和 最后一个结点 都指向头结点，那么我们就称这种头尾相接得单链表位单循环链表。

单循环链表的特点

既然头尾相接，那么单循环链表有新增了下面几种特性

• head 指向头结点，尾部也指向头结点
• 判断空表得时候，只要头结点和头部指向得内容都是该结点本身，那么这个表就是空表。
• 头结点即尾部，头结点指向头结点，head 指向头结点
• 原来是 head->next 是否为 NULL，是就为空表。
• 现在是 head 是否等于 head->next，即头结点指针指向它自己
• 我们把最后一个结点得指针称为 rear

引入

按照惯例，我们学习了如何初始化、插入、删除一个静态链表，那么静态链表打底有什么优缺点呢？链表还有什么高级玩法呢？
我们一起来看看~

静态链表的优缺点

• **优点：**插入和删除时，只需要求改游标，不需要移动元素，从而改进了顺序存储结构中需要大量移动元素的缺点。
• **缺点：**没有解决连续存储分配带来得表长难以确定的问题。

总之，静态链表是一个很好的尝试，在没有动态创建、释放内存空间得情况下，利用数组，完成了静态链表。

练习

创建一个20个元素的动态链表，然后快速找到其中间结点。

引入

我们知道了如何初始化一个静态链表，并且知道如何在静态链表中插入一个结点，今天我们来看看如何删除一个结点，并将删除得结点 Free 。

思路

我们先想一下，如果要移除静态链表中的一个结点，会发生什么。

• 该结点的上一个结点找不到移除的这个结点了，链表断了
• 移除的结点内得数据还有，游标指向的是其原来的下个结点
• 移除的结点成了备用链表中的一个结点，0下标的第一个可用结点也需要修改

所以，我们总结如下得思路

• 移除结点，找到前一结点，指向移除结点的后一结点
• 清空移除的结点内的数据
• 移除结点的游标改为0下标指向的第一个可用结点得下标
• 0下标指向的第一个结点为移除的结点

引入

我们说过动态链表是使用malloc( ) 和 free( )这两个函数来实现的，动态插入，动态释放。那么静态链表该如何实现这样的功能呢？

静态链表中插入数据

简单来说就是要分清楚哪些没有使用过，哪些已经在使用了。
我们说

• 备用链表存放的是所有可以用的下标，用游标链接。
• 数组的第一个元素，存放的是备用链表的第一个可用下标
  所以
  每次插入新节点，都可以从备用链表取得第一个结点作为待插入结点。

步骤分解
1、先获取0下标指向的备用链表的第一个可写入下标。
2、第一个可写入的结点的游标传递给0下标。
3、判断插入地址是否合法，不能小于1，不能大于结点长度+1的位置。
4、对第一个可写的节点的 data 赋值
5、通过循环从最后一个结点向前找到要插入的节点之前的结点
6、找到之后新结点的游标改成之前结点的游标
7、前一结点的游标指向新节点的下标。