2.2 链表（一）

五花八门的链表结构

链表比数组稍微复杂一点。
同样是非常基础非常常用的数据结构。

链表不需要一块连续的内存空间，通过"指针"将一组零散的内存块串联起来使用。

三种常用的链表：单链表、双链表和循环链表。

单链表：
存在头结点和尾结点，尾结点指向空地址NULL。

链表的插入和删除操作不需要为了保存内存的连续性而搬移节点。插入和删除操作只需要考虑相邻节点的指针改变，所以对应的时间复杂度为O(1).

同时因为数据并非连续存储，链表的随机访问没有数组那么高效，需要根据指针一个节点一个节点得一次遍历，需要O(n)的时间复杂度。

循环链表：特殊的单链表，尾结点指针指向头节点，首尾相连。当处理的数据具有环形结构特点时，优先考虑。

双向链表：每个节点不止有一个后继指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。虽然两个指针比较浪费存储空间，但是支持双向遍历。

删除操作：
单纯的删除操作复杂度是O(1),但是遍历找到节点的时间为O(n),所以根据假发法则，删除指定节点的的总时间复杂度为 O(n).

如果要删除了指定节点p后，我们需要找到p的前驱节点o，并把其指向p的后继节点q。

双向指针有效避免了以上的问题，双链表删除指定节点只需要O(1).

新增同理。如java设计的LinkedHashMap也使用了双向链表这种数据结构。

注意设计思想：空间换时间、时间换空间。

链表VS数组

image.png

注意 链表的频繁插入、删除操作会导致频繁的内存申请和释放，容易造成内存碎片，在java中则会导致频繁的GC.

开篇问题

如何用链表来实现LRU缓存淘汰策略呢？

Least Frequently Used: 最近最不常用算法,根据数据的历史访问频率来淘汰数据
核心思想是：
最近使用频率高的数据很大概率将会再次被使用,而最近使用频率低的数据,很大概率不会再使用。

当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，需要比较数据，时间复杂度为O(N)；
当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。
如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(n)。

此文章为2月Day2学习笔记，内容来源与极客时间《数据结构与算法之美》