（三）线性表 ---→ 链表

水深无声 2021-12-10 03:23 267阅读 0赞

### 文章目录 ###

*   *  定义
     *  分类
     *  特点
     *  复杂度分析
     *  \`java\`代码实现

--------------------

## 定义 ##

> 摘抄自 维基百科

**链表**（`Linked list`）是一种常见的 **基础数据结构** *（**按照博主的理解，链表应该属于数据类型范畴对应于 `java` 的 `LinkedList` 类型**）*，是一种 **线性表**，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针( **Pointer**)。由于不必须按顺序存储，链表在插入的时候可以达到 `O(1)` 的复杂度，比另一种 **线性表顺序表** 快得多，但是查找一个节点或者访问特定编号的节点则需要 `O(n)` 的时间，而 **顺序表** 相应的时间复杂度分别是 `O(logn)` *（**这里的 `o(logn)` 指的是在最优解的情况下，数组本来就有序，此时用 二分查找 可以将复杂度由 `o(n)` 优化到 `o(logn)`**）*和 `O(1)`。

其中关于到底是 **数据结构** 还是博主理解的 **数据类型** ，在维基百科的链表介绍中，历史介绍有如下一段话：  
![在这里插入图片描述][2019071514245747.png]

顺便 `diss` 下百度百科：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvdW5neW91dGg_size_16_color_FFFFFF_t_70]  
不应该是 **线性表和顺序表**，应该是 **顺序表** 。

--------------------

## 分类 ##

链表属于**逻辑上的线性结构，物理上的链式存储结构**的线性表

--------------------

## 特点 ##

之前说出了 **顺序表** 的缺点产生的原因：数据逻辑上的有序，映射到物理内存上的有序，导致插入、删除操作，需要移动大量的元素。

主要是物理内存上的有序，导致的。为了克服这个缺点，干脆物理内存上不再有序，有新元素插入的时候，内存哪有空位子，就放哪。让前一个元素记住这个位置，即可完成了逻辑还是有序的。

这样在插入、删除的时候，不再去需要移动元素，只需要告诉前一个元素，后一个的位置发生变化，，记住新位置的地址即可。

物理内存的无序，克服了插入、删除操作，移动大量元素的缺点，但是也丢失了 **随机访问** 能力 ；

优点：

1.  插入、删除的复复杂度都是 `O(1)`
2.  插入新元素，才会申请空间，不会浪费空间

缺点：

1.  存、取的复杂度都是 `O(n)`
2.  需要额外空间去维护前后元素的关系

--------------------

## 复杂度分析 ##

这里说下，插入、删除操作的复杂度 `o(1)` 。

其实，细想下，就会发现这句话有问题，凭什么链表你能说，插入、删除的复杂度是 `o(1)` ，链表没有随机访问能力，要删除某个节点，只能遍历，遍历需要花时间，遍历的时间复杂度是 `o(n)` 。

所以乍一分析，链表的插入、删除操作的时间复杂度应该是 `O(n+1) = O(n)` ，和顺序表没有什么差别。

但是呢，这里面有个读和写的差别。链表插入、删除是 读 占了 `O(n)` ，写 占了 `O(1)` ；而顺序表的插入、删除，是实打实的读写都是 `O(n)` 。读 和 写 ，是有很大差别的，读和写 比起来，读可以忽略不算。写很占用时间。因此，这里分析的，都将双方的读，都省去的结果。因此，需要大量插入、删除等操作的时候，需要选择 **链表**，顺序表 在这种情况下，写的太多了，处于劣势 。

--------------------

## `java`代码实现 ##

链表有诸多版本，不再这一一写出来。

[2019071514245747.png]: /images/20211209/90add5ee099147daaeedf4a488ddddbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvdW5neW91dGg_size_16_color_FFFFFF_t_70]: /images/20211209/2a5a3c5c1f1d43e08a6b6ff4423cfd4b.png