单向链表在内存中是连续存储的（单向链表已经可以实现非连续存储为什么还需要双向链表）



根据百科的描述：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

它大致长这样： 图片来源：wikipedia

链表有很多种结构，比如：单向链表、双向链表、循环链表、块状链表等，本文内容只会涉及单向、双向和循环这三种。

链表有时候看代码会不是很容易理解，建议在学习的同时多在草稿纸上画画图可以辅助理解。

根据百科的描述：

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

需要了解一下这几个名词：

头结点：单链表的第一个结点

尾结点：单链表的最后一个结点

当前结点：遍历链表时使用的一个中间变量保存的当前指向的结点

哨兵结点（或哑结点）：没有实际意义，用于在执行链表操作时，用来方便操作的一个结点

因为一个链表是由一个个结点组成的，定义链表的结点我们可以使用构造函数或者 class 来定义：

有了链表结点的构造函数，接下来为了方便咱们后面学习链表的算法，需要提前准备好一个链表， 创建链表的方法有两种，分别是头插法和尾插法。

为了方便随机生成数字，使用一个工具函数

创建链表之：头插法

头插法，顾名思义就是在链表头部插入结点的方法，这样得到的链表是一个倒序的。

创建链表之：尾插法

尾插法，顾名思义就是在链表尾部插入结点的方法，这样得到的链表是一个正序的。

上面那两个方法适用于快速创建一个链表，实际使用的并不是很多，更多的操作是将一个结点插入到链表中。

一般要将一个结点插入到链表中，需要知道要插入的位置，如果不知道待插入的位置，那么你还得想法去找到这个位置，比如搜索某个结点在链表中的位置，这个后面会讲到。

上面这个插入的方法是基于链表头不是哑结点的方式来操作的，如果你的链表头有一个哑结点，那么上述的代码就要做一下相应的修改，其实跟上面的代码大同小异的，如果你有兴趣，可以自己写一下。

有了插入链表的方法，那么创建链表我们就可以使用这个方法来做了。

使用 insert 方法创建链表

我们现在得到了一个链表，那么如何遍历这个链表把每个结点是数据都输出出来呢？

知道如何遍历链表后，接着咱们再来找一下链表中的某个结点。

首先来个简单的，查找指定值所在的结点

再加点难度，找到指定值所在的结点后，再看看它的位置是多少

再换种方式，假设我们已经知道结点的位置，但是不知道结点的内容，这个也简单：

加油，再学完咋删除链表中的结点就差不多该完事了。

删除结点有两种情况，一种是知道要删除的位置，一种是知道结点的值（需要结点中的值各不相同才行）。

接下来为大家介绍的是知道要删除的位置来删除结点，另外一种情况也是大同小异的。

咱们现在已经学完了链表的数据结构以及一些最基本算法：创建链表、插入、遍历、查找、删除。

接下来的内容将会以上述基本算法为依托来进一步加深问题难度，咱们再学习一下要如何来求解这些问题。

翻转链表就是要把链表里面的结点的指向改成与原来相反的方向，比如原来的链表是：A -> B -> C -> D -> null 这样的顺序，翻转后就会变成：D -> C -> B -> A -> null

有一个问题是这样描述的：

给定一个这样的链表：A -> B -> C -> D -> E -> B，请问如何检测这个链表是否有环，也就是尾结点指向了另一个结点，这就叫链表有环。

更特殊的有：A -> B -> C -> D -> E -> A，即尾结点指向了头结点，这个链表就构成了一个循环链表。

对于这个问题，有的同学会这样回答：我遍历整个链表，把链表中的值存到一个临时变量中，如果某次遍历的时候发现当前的值等于临时变量的值，就说明有环了。这个思路也对，但不是最好的办法。

解决这个问题，可以利用在操场跑圈的办法来解决，两位同学同时朝一个方向跑，其中一位跑的快，另一位跑的慢，如果快的那位同学追上了慢的那位同学，就说明这个操场是环形的了。

有两个递增排序的链表，现在需要合并这两个链表并使新链表中的节点仍然是递增排序的。

示例，给定两个链表：

L1: 1->2->4

L2: 1->3->4

合并后，返回：1->1->2->3->4->4

给定一个链表：A -> B -> C -> D -> E -> null 输入 2，则表示要删除这个链表的倒数第二个结点也就是 D 所在的这个结点。 返回结果：A -> B -> C -> E -> null

我们最容易想到的办法就是先遍历链表得到长度，然后 长度 - n 就是要删除的那个结点，再执行删除操作即可。

但是这需要两次遍历的操作，我们可以这样来考虑优化一下解法：

两个同学在操场跑 100 米，假设 A、B 两同学的速度是一样的，那么当 A 跑了 50 米的时候 B 开始跑，那么 A 到终点的时候 B 刚好跑了 50 米。而 50 米这个点就可以看作是待删除的结点了。

这个思路在解决链表有没有环的时候也用到过，大家习惯称这种思路叫：快慢指针。也有的叫龟兔赛跑。

这道题也容易想到两次遍历的做法，但是使用快慢指针会更好。

基本算法跟单向链表差不多，只是多了个前驱结点。

单链表把尾指针指向头指针后就是循环链表了。

双向链表就是尾指针指向头，头指针指向尾。

具体的双向链表和循环链表的题就不带大家做了，有兴趣的可以去找来做做。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/67581.html