数据结构与算法之美笔记 —

数据结构与算法之美笔记 —— 链表

本文主要是介绍数据结构与算法之美笔记 —— 链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、链表和数组的区别

1、内存的使用

2、CPU缓存机制的预读取

3、查找、插入和删除操作

二、单链表

三、循环链表

四、双向链表

五、如何轻松的写出正确的链表代码

数据结构与算法之美-06

一、链表和数组的区别

1、内存的使用

数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。
动态扩容的成本：链表本身没有大小的限制，天然地支持动态扩容，相比于数据扩容的空间申请和数据迁移的扩容，效率更高。但是链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
内存空间的基本占用：如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。

2、CPU缓存机制的预读取

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。
链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

3、查找、插入和删除操作

链表的插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的，对应的时间复杂度是 O(1)
链表的查询，对应的时间复杂度是 O(n)，因为必须一个一个访问；

二、单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。

三、循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

四、双向链表

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

存储同样多的数据，双向链表要比单链表占用更多的内存空间。但相比于单链表，双链表是基于用空间换时间的设计思想的产物。在根据指针指向插入删除，和在有序列表中查询某个值是，双向量表可以以O(1)的时间复杂度获取到前一个节点，而单向链表只能从头开始遍历去寻找前一个节点。因此在这些操作中，双向链表的效率更高。