链表是有序的列表，但是在内存中存储图下图所示

1. 链表是以 节点 的方式来存储，是 链式存储
2. 每个节点包含 data 域、next 域，指向下一个节点
3. 链表的各个节点 不一定是连续存储，如上图所示
4. 链表还分：带头节点、不带头节点，根据实际需求来确定

上面进行了一个简单的介绍，下面分几部分来讲解：

单链表

单链表（带头节点）逻辑结构 示意图如下，当下一个节点为 空 的时候，该链表就结束了

注意：是逻辑结构，前面说过，在内存中节点不是一个接一个的。

考虑这样一个场景：使用带 head 头的 单向链表 实现水浒英雄排行榜管理

1. 完成对英雄人物的 增删改查 操作

2. 第一种方法：在添加英雄时，直接添加到链表的尾部

3. 第二种方法：在添加英雄时，根据排名将英雄插入到指定位置

   如果有这个排名，则添加失败，并给出提示

如上图所示，添加流程。我们创建 节点，他的定义如下

next 指向下一个节点，为空则代表该链表结束。其他的字段则是上面所说的数据了。

测试输出

可以看到，已经实现了，如果将 no=4 提前加入

测试数据如下

编号就是无序的了。下面来实现有序的

添加思路如下：

1. 首先 找到 新添加节点的位置(新节点遍历比较排名，来查找要插入的位置)，通过辅助变量 temp，然后循环遍历查找

2. 如果有这个排名，则添加失败，并给出提示，没有则进行下面的步骤

3. =

4. 将 =

   注：temp辅助节点为要插入点的前一个节点。

简单一点就是：通过排序规则（当前是从小到大）遍历找到要插入的位置，然后改变 next 的指向。

代码实现，在原有的代码基础上新增了一个添加方法，如下

测试用例如下

输出信息

如果重复添加的话，会输出如下类似的信息

在原来的代码基础上新增 update 方法

测试用例

测试输出

如上图所示，思路如下：

1. 先找到需要删除的这个节点的 前一个节点 temp

   为什么要找到前一个？因为是单向链表，找目标节点就无法完成删除了。

3. 被删除的节点，如果没有其他的引用的话，会被垃圾回收机制回收

测试代码

输出信息

tip：学会思想，将其灵活运用到所需项目中。

单链表面试题

为了加深理解，来看几个面试题

思路：直接循环统计就行

测试用例

输出

新浪面试题

测试用例

输出信息

腾讯面试题，这个有点难度。

思路：

1. 定义一个新的 reverseHead 节点
2. 从原链表中依次取出节点，并 始终添加到 reverseHead 的第一个节点
3. 将原 head 节点的 next 指向 reverseHead.next

头插法

如下图所示：

测试用例

输出信息

百度面试题，要求方式：

1. 反向遍历

思路：

1. 反向遍历 ：使用前面翻转操作后，再打印

   有一个问题：会破坏原链表的结构

2. Stack 栈：利用栈先进后出的特点

   该数据结构看后面的博客讲解，这里做个简单的介绍

   

   如上图所示：

   1. 入栈操作：数据 栈底 压入
   2. 出栈操作：数据 栈顶 弹出

   将原链表遍历，以此将每个节点压入栈中，然后遍历栈打印即可

测试用例

输出信息

双向链表

从前面的练习题，包括实现单向链表中会发现 单向链表 的以下问题：

• 查找方向 只能是单向

• 不能自我删除

  需要靠辅助节点，要找到删除节点的上一个节点和删除节点，才能完成删除

而以上问题，双向链表：

• 可以双向查找
• 可以自我删除

双向链表的结构如上图所示，每个节点都有 和 变量，所以它可以往前查找或则往后查找。

那么下面先分析下双向链表的：遍历、添加、删除 操作思路，之后再去实现：

• 遍历：和单向链表类似，只是可以双向遍历了

• 修改：和单向链表一样的方式

• 添加：默认添加到双向链表的最后一个节点

  1. temp.next = newNode
  2. newNode.pre = temp

• 删除

  

  如上图所示，双向链表可以自我删除：

  1. 遍历找到要删除的那个节点 temp

可以基于单向链表上的部分代码进行修改。

测试用例：

测试输出

实现：双向链表的第二种添加方式，按照编号顺序添加

实现和单向添加是一样的

测试用例

测试输出

单向环形链表-Josephu 问题

约瑟夫（Josephu）问题，也就是丢手帕问题，他的规则如下

• 有编号为 1 ~ n 的 n 个人围坐在一起
• 约定编号为 K( 1 <= k <=n) 的人从 1 开始报数
• 数到 m 的那个人出列，它的下一位又从 1 开始报数

循环以上过程，直到所有人都出列，并列出出列人的编号。

该问题其实可以使用 单循环链表（单向环形链表）来解决，思路如下：

1. 先构成一个有 n 个节点的单循环链表
2. 然后由 k 节点起从 1 开始计数
3. 计数到 m 时，对应节点从链表中删除，然后从下一个节点又从 1 开始计数

循环以上过程，直到最后一个节点从链表中删除，算法结束

它的逻辑结构就如下图，形成了一个环状。

需求如下：

• ：有 5 个人
• ：从第一个人开始数
• ：数两次

没有动图，那么使用下面的描述来讲解：

1. 第一轮：2 出队列，1.next = 3

   还剩下：1、3、4、5

2. 第二轮：4 出队列，3.next = 5；（从 3 开始报数，第 2 个的出队列，也就是 4）

   还剩下：1、3、5

3. 第三轮：1 出队列，5.next = 3

   还剩下：3、5

4. 第四轮：5 出队列，3.next = 3

   还剩下：3，自己的 next 就是自己

5. 第五轮：3 出队列，队列中无元素，结束

那么最终的出队列顺序就是：2、4、1、5、3

约舍夫问题可以使用数组来解决，这里使用单向环形链表，比较好理解

1. 第 1 个节点被添加进来时

   

   使用一个 first 变量来表示这是第一个节点，和带头节点的链表一样，不能去改变他，使用 变量来辅助我们解决添加的过程，并让 指向自己，形成一个环形

2. 第 2 个节点被添加进来时，boy是新要添加进来的节点

   

   将该节点加入到已有的环形变量，并把指向这个新节点，下面的以此类推

3. 第 3 个节点被添加进来时

   

1. 先让一个辅助变量 ，指向 first 节点
2. 通过一个 while 循环遍历链表，当 时，就遍历完了

测试用例：

测试输出：为了验证前面 5 个小孩的说明是否正确，这里也添加 5 个小孩

还是以这个需求来分析：

用户输入如下：

• ：有 5 个人
• ：从第一个人开始数
• ：数两次

1. 需要一个 来帮助出圈，当出圈报数开始时，报数完的时候所指到的节点出圈，而helper就是来帮助出圈的，如下图所示

   

2. 将 first 定位到 k ， helper紧随其后 （k 从第几个小孩开始报数）

   将 first 和 helper 移动 次

3. 小孩报数时：移动 first 到出圈的节点上，hepler 始终在 first 后面

让 first 和 helper 同时移动 m-1 次，是因为 开始数数的人 也要占用一个位置(自己本身也要数)：比如上图，从 1 开始，first在编号 2 时，就数了 2 下了，它该出圈

1. 小孩出圈（下图是经过报数（2）后的图，原图first在 1 的位置）

   

   先将 （first指向下一个节点），然后将 （将出圈小孩的后面一个小孩的next指向变化后的first），那么就如上图所示了，出圈的 first 被孤立出圈了，别人没有引用它了，就会被垃圾回收机制销毁了。

注意：只有 小孩报数和出圈是重复 的，其他的只是这个游戏开始前的一些设置初始化。

在原来的环形队列上添加游戏开始方法（计算出圈顺序）

测试用例

测试输出

可以尝试修改下从第 3 个小孩开始报数

小结

需要正视的一个点：现在在学习数据结构，比如数组可以模拟 队列，数组可以模拟 环形队列，队列也是一个数据结构，主要是思路。