从零开始学Java之小白速看，详解线性结构中的链表

逃离我推掉我的手 2023-10-13 13:03 13阅读 0赞

## 一. 链表简介 ##

### 1. 概念 ###

线性表可以说是一种最基础最简单的数据结构，它表示的是一种线性结构，比较常见的线性结构包括数组和链表等。

所谓的链表，顾名思义，就是链式的线性表，即链表也是一种线性表。与数组不同的是，链表采用的是链式存储，这种链式结构是**非连续、非顺序的内存空间**。链表中的每一个独立的元素被称为结点，故链表由一系列的结点组成。

**其中链式存储的含义如下：**

假如我们需要存放一堆物品，但没有足够大的空间将所有的物品一次性放下，此时该如何既放下所有的物品，又能简单的找到所有的物品位置呢？我们可以尝试采用如下解决方案：存放物品时，每放置一件物品就在该物品上贴一个小纸条，标明下一件物品放在哪里。这样，我们只需要记住第一件物品的位置，从第一件物品上的小纸条，就可以找到第二件物品，再根据第二件物品纸条的内容就找到第三件物品。按照这个方法依次类推，我们便可以找到所有的物品，这就是所谓的链式存储。

### 2. 表示方式 ###

链表中的每个结点都由两部分组成：**数据域、指针域**。数据域用来存放当前结点需要存储的数据内容，指针域用于存放当前结点的下一个结点的地址。如下图所示：

![format_png][]

图1-链表的结构示意图

上图所示的节点细节如下：

>  *  首个结点中next1存放的是第二结点的内存地址，因此用一个箭头指向第二个结点，就可以表示两个结点之间的关系。
>  *  最后一个结点的后面不再有其他结点，因此最后结点的next5指针域中没有地址内容，编程中可以用null表示。

### 3. 特点 ###

通过上文所述，**壹哥**就可以给大家总结出链表的主要特点：

> (1). 从内存结构来看，**链表**的内存结构**是不连续的内存空间**，是将一组零散的内存块串联起来，从而进行数据存储的数据结构；
> 
> (2). **链表由一系列结点组成**，每个结点包括两个部分，**一个是**存储数据元素的**数据域**，另**一个是**存储下一个结点地址的**指针域**。链表中数据元素的逻辑顺序就是通过地址指针实现的；
> 
> (3). **链表和数组相比，内存空间消耗更大**，因为每个存储数据的结点都需要额外的空间存储地址指针。

## 二. 链表分类 ##

在工作实践中，开发者接触到的链表主要有三种：**单向链表、双向链表、循环链表**。下面**壹哥**给大家逐一进行介绍一下。

### 1. 单向链表 ###

**单向链表的每一个结点包含两部分，一部分是存放数据的变量data，另一部分是指向下一个结点的指针next。** 单链表只能单向读取，其结构如下所示：

![format_png 1][]

图2-单向链表结构示意图

我们以Java为例，给出单向链表的结构定义：

java

复制代码

`class Node{ Object value; Node next; }`

### 2. 双向链表 ###

**双向链表，表示链表结点由三部分组成：数据域、下一结点指针域、前一结点指针域。** 在双向链表结构中，既可以从首个结点出发，根据下一结点指针域依次找到所有结点；同理，也可以从指定的某个结点，根据结点中的前一结点指针地址，向前依次得到前面的结点。具体地，双向链表的结构示意图如下所示：

![format_png 2][]

图3-双向链表结构示意图

如上图所示：

>  *  第1个结点作为整个链表的首结点，该结点的prev1指针内容为null，表示没有前一个结点。
>  *  第5个结点作为整个链表的最后结点，next5指针内容为null，表示后续没有下一个结点。
>  *  除此之外，中间三个结点，next指针和prev指针分别指向下一个结点和前一个结点，可以实现双向查找。

使用Java进行双向链表的结点结构定义如下：

java

复制代码

`class Node{ Object value; Node next; Node prev; }`

### 3. 循环链表 ###

如果，我们将链表的最后结点的next指针域做下修改，由原来的指向null修改为指向第1个结点，则整个链表就变成了一个环路。以单向链表进行操作，如下图所示：

![format_png 3][]

图4-单向循环链表示意图

如上图，每个结点有数据域和指针域两个部分，这种循环链表被称之为**单向循环链表**。在计算机领域中，单向循环链表又称约瑟夫环（Josephu Loop），这一点仅做了解即可。当然，双向链表也可以调整为循环的链表，被称之为双向循环链表，如下图所示：

![format_png 4][]

图5-双向循环链表示意图

## 三. 存储原理 ##

数组在内存中的存储方式是顺序存储（连续存储），链表在内存中的存储方式则是随机存储，如下图所示：

![format_png 5][]

图6-链表的内存存储示意图

链表的每一个结点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。链表的第一个结点被称为头结点，没有任何结点的next指针指向它，它的前置结点为空null。头结点用来记录链表的基地址。有了它，就可以遍历得到整条链表的数据。链表的最后一个结点被称为尾结点，它的next指向为空null。

## 四. 链表常见操作 ##

本篇文章内容，我们以单向链表为例，介绍链表的常见操作，主要包括：**查找结点、更新结点、插入结点和删除结点**等操作。

### 1. 查找结点 ###

在查找元素时，链表只能从头结点开始向后，一个结点一个结点逐一查找，如下图所示：

![format_png 6][]

图7-单向链表查找结点示意图

时间复杂度分析，分两种情况：

>  *  查找头结点：头结点是链表的第一个结点，直接就能得到结果，因此查找头结点时间复杂度是O(1)。
>  *  查找非头结点：如果查找非头结点，则需要从头结点向后依次查找，知道整个链表的末尾，因此查找非头结点的其他结点时，时间复杂度是O(n)，最坏情况下时间复杂度也是O(n)。

### 2. 更新结点 ###

更新结点操作需要两个步骤：

>  *  找到要更新的结点；
>  *  将旧数据替换成新数据。

如下图所示：

![format_png 7][]

图8-单向链表更新结点数据操作示意图

与查找结点操作时间复杂度情况类似，更新时间复杂度分两种情况：

>  *  **更新头结点**：单向链表更新头结点的时间复杂度是O(1)；
>  *  **更新非头结点**：更新其他结点的最坏情况时间复杂度是O(n)。

### 3. 插入结点 ###

#### 3.1 尾部插入 ####

尾部插入即把最后一个结点的next指针指向新插入的结点即可，如下图所示：

![format_png 8][]

图9-单向链表尾部插入结点示意图

时间复杂度分析：如上图所示，若尾部插入结点，则需要从头开始遍历，因此单向链表添加尾结点的时间复杂度是O(n)。

#### 3.2 头部插入 ####

头部插入新结点需要两个步骤：

> (1). 把新结点的next指针指向原先的头结点；
> 
> (2). 把新结点变为链表的头结点。

如下图所示：

![format_png 9][]

图10-单链表头部插入结点示意图

时间复杂度分析：因为直接将新节点的指针域指向头结点即可完成操作，因此添加头结点的时间复杂度是O(1)。

#### 3.3 中间插入 ####

在链表的中间位置插入结点同样需要三步：

> (1). 从头结点开始向后查找，找到要插入的结点的位置；
> 
> (2). 新结点的next指针指向插入位置的结点；
> 
> (3). 插入位置前置结点的next指针指向新结点；

示意图如下：

![format_png 10][]

图11-单向链表中间位置插入结点

时间复杂度分析：若执行插入结点操作，首先需要从头结点向后查找，找到要插入的位置。很明显，与链表的规模有关，因此中间插入结点操作的时间复杂度是O(n)。

### 4. 删除结点 ###

#### 4.1 尾部删除 ####

若希望删除链表的最后一个结点，只需要将倒数第二个结点的指针域指向null即可，如下图所示：

![format_png 11][]

图12-单向链表尾部删除结点示意图

时间复杂度分析：因为要从头开始遍历，所以单向链表删除尾结点的时间复杂度是O(n)。

#### 4.2 头部删除 ####

头部删除与头部插入操作类似，只需要把链表的头结点设为原先头结点的next指针即可如图：

![format_png 12][]

图13-单向链表头部删除结点示意图

时间复杂度分析：删除头结点的时间复杂度也是O(1)。

#### 4.3 中间删除 ####

中间位置删除结点操作类似于中间插入操作，需要三步：

> (1). 从头结点开始向后，找到要删除结点的位置；
> 
> (2). 找到删除结点的前一个结点和后一个结点；
> 
> (3). 将要删除结点的前置结点的next指针，指向要删除元素的下一个结点；

如下所示：

![format_png 13][]

图14-单向链表中间删除结点示意图

时间复杂度分析：因为需要从头结点开始进行查找，因此时间复杂度与链表的规模有关，故单向链表删除中间位置结点的时间复杂度是O(n)。

\------------------------------**正片已结束，来根事后烟**\----------------------------

## 五. 结语 ##

本篇文章，我们一起学习了链表的概念，认识了单向链表、双向链表、循环链表等不同的链表类型。并以单向链表为例，分析了链表中的结点炒作及对应的时间复杂度分析，不知道你现在对链表了解了吗？

另外如果你独自学习觉得有很多困难，可以加入**壹哥**的学习互助群，大家一起交流学习。

[format_png]: https://img-blog.csdnimg.cn/img_convert/6e0b89c5dab283cd92717a2b19c4c5eb.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/79b30f8cd7b4f7496fd26e01f9e89b11.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/85618fb2360100c0f33859464a4976ee.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/88ca70f9cc45a702fcf4a8cb1b34748e.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/d80d8b5f9b72578ce234593ecf19ca2f.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/66d1d47cf3c3c5789fa0723f70732f5a.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/630b02dbe8a448e6dd8a6368d0c61d9b.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/f747cd0b491a90e7fe8d478ddee4b33b.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/25926a0e99546a8402ecb979098e3d1d.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/01c34d2f187b741f316c67cff1592676.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/7a25c0fa289d28f5f2939071186976c4.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/c4cd83f3dc8cb8daa5be7f1f1e7bd193.webp?x-oss-process=image/format,png
[format_png 12]: https://img-blog.csdnimg.cn/img_convert/83b4bd85d03a21ba2e46391e1100a126.webp?x-oss-process=image/format,png
[format_png 13]: https://img-blog.csdnimg.cn/img_convert/754b22944271a917d915d6b5a09455f4.webp?x-oss-process=image/format,png