mock模拟的数据能增删改查吗_数据结构与算法（3）链表

梦里梦外; 2023-01-03 14:13 6阅读 0赞

为什么要讲链表呢？这是因为java中有很多集合类底层都是通过链表来实现的。而且面试的时候，链表的实现是经常考的一个知识点。所以这篇文章的重点在于，如何使用代码去实现这些数据结构。但是这篇文章我不打算直接上来就讲链表，而是先从线性表开始。按照惯例先给出这篇文章的大致脉络吧。

> 首先，是对数据结构中线性表，做一个回顾。还讲了其两大存储结构，顺序存储结构和链式存储结构。  
> 接下来，重点讲各种链表的介绍，以及常用方法和特点  
> 最后，对java中使用链表的集合类，进行一个介绍。  
> 当然，还有一些常见的面试题。

OK，开始。

**一、线性表**

为了很好的描述这个概念，先从一个例子开始吧，比如幼儿园的小朋友放学之后，都是手拉手排着队走出校园，这些小朋友从外表来看就像是一条链子，而线性表就和这个链子一样，这些小朋友就像是线性表里面的数据元素，从外面看一个接一个。比较正式的定义那就是：**线性表：0个或者多个数据元素的有限序列**。

刚刚我提到的都是从表面来看都是一样的，说明在内部的实现方式是不一样的，下面就是线性表的两种存储结构：**顺序存储结构和链式存储结构。**

*  顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
 *  链式存储结构：地址可以连续也可以不连续的存储单元存储数据元素

今天主要讲的就是基于链式存储结构的链表。你可以这样理解，比如说你要找一个人，名字叫张三，你首先跑到A，发现没有，A告诉你B可能知道，你跑到了B。B说C可能知道，你跑到了C，张三果然在C那里，如果没有就这样一直不停的去找。一张图看一下

![797d5e1978024236c115d05acc4589a2.png][]

但是这只是基础，对线性表的描述，不想花费太多时间在这。下面用一张图表述吧。

![903ee2869541607c9ef2cd7b1f0b2e29.png][]

有了上面这张图，相信对分类等都有了了解和认识了。下面开始今天的主题单链表。

下面在对这两种存储结构进行一个对比。

![e3fd476ec773b2d9d69023ba8627f44a.png][]

**二、链表**

**1、单链表**

对于链表，里面主要有几个重要的信息，对于每一个节点（比如上一节讲到的A,B,C三处）都有下一个节点的地址和当前节点的数据。下面代码实现一下：

首先是节点的定义（由于直接上传代码，效果不好，这里就给出图片了））：

![50d0455eaca4803764720e5434fe4363.png][]

接下来无非是对节点的增删改查罢了，先看基本的操作。

![451b025b97b60eed977dca6b953857ac.png][]

下面就是正删改查了，但是有一个思路需要我们要牢记，这样在使用其他语言实现的时候，就能快速的掌握，这是我自己的方法。上面已经描述了通过索引查找元素，所以下面只考虑，插入删除操作就好了。

> 首先，我们要判断当前的空间是否满足增删该查的条件  
> 接下来，判断增删改查的位置是否正确  
> 最后，增删改查之后没有副作用产生。

**第一个操作：插入（三种方式：头插入、尾插入、中间插入）**

对于插入操作，使用一张图简单表述一下

![9a62a5f0d28251cb96e2d63a00ebdcbc.png][]

![0aa61cc0ac0d3c5381e92577a8e9acbc.png][]

![25ecc73e3f33173815d7313bde773df2.png][]

**第二种操作：删除**

对删除操作同样一张图

![58bc62cbad1e3ef54011787304a35266.png][]

![00f42aed996527e5d97efdce48cdb5d8.png][]

小结：上述是对单链表的增删改查操作，对于其他链表关键就在于对单链表的更改。当然这里只给出了链表的代码实现。对于顺序存储结构的顺序表实现。同样也是这个道理。你只需要定义一个节点进行增删改查就好了。

**2、循环链表**

如果你对单链表的操作能够掌握的话，剩下的这几种链表，我相信你也能很快掌握，只不过把node中的基本数据改一下，增删的时候多一两行代码。对于循环链表，你可以想象成y一个闭环的链表。也就是最后一个元素又指向了第一个元素。其特点是这里的讨论重点。

![d3fdc16a985d537127d7720925e22e4d.png][]

特点

（1）适合合并两个循环链表：有了尾指针直接合并，比如说下面有两个循环链表。

![8591683e188e5feb792f4f27fbbe8e1d.png][]

现在使用尾指针合并他们。

![a8cb4dd8e2df3344e72353932a53775f.png][]

（2）从表中任何一个节点出发，都能访问链表的全部节点。这一点很好理解。

**3、双向链表**

从名字就可以看出，每一个节点既指向前驱又指向后继。

![dc4c84433110fcf33cbbed1921dac304.png][]

这个双向链表相对于单链表还是比较复杂的，毕竟每个节点多了一个前驱，因此对于插入和删除要格外小心。双向链表的优点在于对每个节点的相邻接点操作时候，效率会比较高。

**三、java中的线性表表**

最典型的就是Collection接口了。下面还包括了一些他的实现类，比如List接口，ArrayList类和LinkList类，其底层都是实现了线性表。我们只需要知道Collection这些全部都是使用了线性表，因此在遇见面试题的时候，如果要求不能使用java中提供的集合类。那么我们应该学会使用上述的线性表表的操作去解决问题。

**四、常见面试题，你会几个？**

对于面试题，由于篇幅问题，所以这里只给出思路，本来我把代码放进来了，但是又删除了**（原谅我颤抖的手）**

1、单链表的创建和遍历

本题上面已经给出答案，这里不再说了。

2、求单链表中节点的个数

这一题相当于，遍历一遍链表

3、查找单链表中的倒数第k个结点（剑指offer，题15）

先计算出链表的长度size，然后直接输出第(size-k)个节点就可以了

4、查找单链表中的中间结点

你可以先获取整个链表的长度N，N/2就好了。

5、合并两个有序的单链表，合并之后的链表依然有序【出现频率高】

这个类似于归并排序，你创建一个新链表，然后把上面两个链表依次比较，插入新链表

6、单链表的反转【出现频率最高】（剑指offer，题16）

这个是对插入操作的考察，在上面写了三种插入操作实现方式，从头到尾遍历链表，取出当前链表节点，插入新链表的头结点。这样第一个取出的节点，在新链表就是最后一个

7、从尾到头打印单链表（剑指offer，题5）

8、判断单链表是否有环

这里也是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。因此，我们用两个指针去遍历：first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。

9、取出有环链表中，环的长度

10、单链表中，取出环的起始点（剑指offer，题56）。

11、判断两个单链表相交的第一个交点（剑指offer，题37）

12、 已知一个单链表中存在环，求进入环中的第一个节点

基本上就写这么多吧，由于是基础内容，也比较容易理解，在大学的时候都学到过，这里算是一个复习巩固吧。

有什么问题，还请批评指正。谢谢

最后给出我的微信公众号吧，只要坚持下去，希望总有一天关注的人会越来越多的，谢谢

![62b4dadd78a0e86bd8009a34160b435c.png][]

[797d5e1978024236c115d05acc4589a2.png]: /images/20221119/2c3e10aa91d648e19f1fbf7248cb2b27.png
[903ee2869541607c9ef2cd7b1f0b2e29.png]: /images/20221119/9a7bf231ff2040afa15a40ed9a302cc2.png
[e3fd476ec773b2d9d69023ba8627f44a.png]: /images/20221119/1cfda33c4e24460a81885bf3819bf1ef.png
[50d0455eaca4803764720e5434fe4363.png]: /images/20221119/b5f0ad21fe7848db8a47655f3bd1ea6b.png
[451b025b97b60eed977dca6b953857ac.png]: /images/20221119/77a87988571e4e9a8f43d391051db69e.png
[9a62a5f0d28251cb96e2d63a00ebdcbc.png]: /images/20221119/46e0a0beead74e3ea0f9903ce8d1a2d7.png
[0aa61cc0ac0d3c5381e92577a8e9acbc.png]: /images/20221119/d163b7547caa458cbeb1bc83614f4b08.png
[25ecc73e3f33173815d7313bde773df2.png]: /images/20221119/92d559c5632b4cfcb20d14e9b751c4a2.png
[58bc62cbad1e3ef54011787304a35266.png]: /images/20221119/846c39b8e8b342dbba5258474b5a89b9.png
[00f42aed996527e5d97efdce48cdb5d8.png]: /images/20221119/2e43548bab1a4bfbb6e407866d111fa3.png
[d3fdc16a985d537127d7720925e22e4d.png]: /images/20221119/a9f657803f9e4796acb5d832428850d9.png
[8591683e188e5feb792f4f27fbbe8e1d.png]: /images/20221119/4e1de78fc4614f90a342f467e4c044c3.png
[a8cb4dd8e2df3344e72353932a53775f.png]: /images/20221119/1336b07c289843209c314b788a14286d.png
[dc4c84433110fcf33cbbed1921dac304.png]: /images/20221119/6f2b286603bd4bf4ae11a6aa18cd2ff1.png
[62b4dadd78a0e86bd8009a34160b435c.png]: /images/20221119/b29edb63417e44f5ac1b67f3c74e08fb.png