单链表

末蓝、 2023-10-05 19:06 5阅读 0赞

### 回顾 ###

在 [线性表][Link 1] 中，介绍了线性表定义、顺序存储结构以及链式存储结构这两种存储结构。

先回顾下线性表的链式存储结构的一些内容：

1.  链表是线性表的表现形式之一，既然线性表是有首有尾的，那么链表也一样。回顾下在 [线性表][Link 1] 中说到的「为了快速找到下一个元素的地址，咱们需要把下一个元素的地址存在当前节点中」，咱们对链表结构进行更专业的定义，以便下文中使用。
2.  为了表示每个数据元素  a i a\_i ai 与其直接的后继数据元素  a i + 1 a\_\{i+1\} ai\+1 间的逻辑关系，对数据元素  a i a\_i ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
3.  我们把存储数据元素信息的域称为 **数据域**，把存储直接后继位置的域称为 **指针域**，指针域中存储的信息称做 **指针**或 **链**。这两部分信息组成数据元素  a i a\_i ai 的存储映像，称为 **结点**（Node）。

### 定义 ###

n 个结点链结成一个链表，即为线性表（ a 1 a\_1 a1、 a 2 a\_2 a2、 a 3 a\_3 a3…… a n a\_n an）的链式存储结构，由于此链表中的每个结点只包含一个指针域，所以叫做单链表。大概就是下图所示：  
![在这里插入图片描述][20210209003952836.png]

### 其它定义 ###

头指针：我们把链表中的第一个结点的存储位置叫做 **头指针**，整个链表的存取必须从头指针开始进行。那最后一个结点呢？最后一个，意味着直接后继不存在了，所以我们规定最后一个结点指针为「空」，用 null 或 ^ 表示。大概就是下图所示：  
![在这里插入图片描述][20210226201720894.png]

头结点：为了对链表进行方便地操作，会在单链表的 **第一个结点前** 再附设一个结点，称为 **头结点**。数据域可以不存任何信息，也可以存线性表的长度等附加信息，其指针域存储指向第一个结点的指针。如下图所示：  
![在这里插入图片描述][20210226201803318.png]

> 头结点与头指针区别  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]

再对单链表做一个补充：  
![在这里插入图片描述][20210226201955100.png]

### 常见描述 ###

空表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 1]

### 操作单链表 ###

#### 读取 ####

当我们现在要获取第 i 个元素的数据时，就用到了单链表的读取操作，说下大概思路：

1. 定义一个结点 p 指向链表的第一个结点，初始化从 j=1 开始；
2. 如果 j<i，则遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1；
3. 如果到链表末尾了，p 还是为空，说明第 i 个元素不存在；
4. 否则查找成功，返回此时结点 p 的数据。

#### 插入 ####

在单链表的第 i 个数据插入结点思路：

1. 声明一个结点 p 指向链表的第一个结点，初始化 j 从 1 开始；
2. 当 jnext = p->next;`， `p->next = s;`；
7. 返回成功。

第 6 步的图解：  
![在这里插入图片描述][20210220200554120.png]

#### 删除 ####

单链表第 i 个数据删除结点的思路：

1. 声明一个结点 p 指向链表的第一个结点，初始化 j 从 1 开始；
2. 当 jnext 赋值给 q；
5. `p->next = q->next`；
6. 将 q 结点的数据赋值给 e，作为返回；
7. 释放 q 结点；
8. 返回成功

大概图示：  
![在这里插入图片描述][20210220200949668.png]

### 与顺序存储结构对比 ###

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th>存储分配方式</th> 
 <th>时间性能</th> 
 <th>空间性能</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>单链表</td> 
 <td>采用链式存储结构</td> 
 <td>查找：O( n n n)；插入删除：O( 1 1 1)</td> 
 <td>不需要预先非配存储空间</td> 
 </tr> 
 <tr> 
 <td>顺序存储结构</td> 
 <td>用一段连续的存储单元依次存储线性表的数据元素</td> 
 <td>查找：O( 1 1 1)；插入删除：O( n n n)</td> 
 <td>需要预先分配存储空间，如果分大了浪费空间，分小了容易溢出</td> 
 </tr> 
 </tbody> 
</table>

给我们的一些启示：

1.  需要频繁插入和删除时，宜选用链表结构；
2.  需要频繁读取时，宜选用顺序存储结构。

### 写在最后 ###

此篇文章简单介绍了单链表相关的定义和一些常见的操作，至于有关的 Java 代码，敬请期待以后与之结合的 LeetCode 题解~

下篇 [循环链表][Link 2] 见~

[Link 1]: https://mindartisan.blog.csdn.net/article/details/113271849
[20210209003952836.png]: https://img-blog.csdnimg.cn/20210209003952836.png
[20210226201720894.png]: https://img-blog.csdnimg.cn/20210226201720894.png
[20210226201803318.png]: https://img-blog.csdnimg.cn/20210226201803318.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2021022620183055.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[20210226201955100.png]: https://img-blog.csdnimg.cn/20210226201955100.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210226202034659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[20210220200554120.png]: https://img-blog.csdnimg.cn/20210220200554120.png
[20210220200949668.png]: https://img-blog.csdnimg.cn/20210220200949668.png
[Link 2]: https://mindartisan.blog.csdn.net/article/details/114151779