数据结构-2-链表

链表简介

首先，链表不需要连续的你内存空间，它通过“指针”将一组零散的内存块串联起来使用；每一个内存块实际上被称作“节点”，每个节点除了数据还有一个记录下一个节点位置的指针，比如指向后记节点叫做next 指向前一个节点地址称作prev；如果是链表的尾部，next 指向的是一个null。

常见的链表有单向链表和双向链表。

单向链表只有数据和指向下一个节点的指针，双向链表包括数据和指向上一个节点和下一个节点的两个指针。

操作复杂度分析

单链表的插入、删除操作的时间复杂度都是 O(1)：比如新增节点，只需要把上一个节点的指针指向加入的数据，并将新节点的指针指向下一个节点即可（删除同理）；

双向链表因为有了前驱指针，在特定情况下性能会更加高效，体现在：

删除：

• 删除指定值的节点

无论是单向链表还是双向链表，都需要将整个链表遍历一遍，复杂度相等，为 O(n)。

• 删除指定指针指向的节点

对于单向链表，需要将需要被删除的节点的上一个节点的 next 指针指向被删除的节点的下一个节点，所以需要从头开始遍历，如果某节点的 next 指向需要被删除的那个节点，则将它进行修改，所以复杂度是O(n);

对于双向链表，由于被山粗的节点有前驱指针，可以直接通过前驱指针找到上一个节点，修改其 next 指针，所以复杂度是O(1)；性能有提升了。

相关问题

数组和链表 复杂度对比

时间复杂度	数组	链表
随机访问	O(1)	O(n)
插入，删除	O(n)	O(1)

时间换空间

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以
选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

比如在JAVA中，我经常使用 LinkedHashMap ，其实是一个双向链表实现的，虽然他会比较费内存，但是能够保证顺序。

用链表实现了一个 LRU 缓存

常用的缓存清除策略包括：

• 先进先出策略 FIFO （ First In ， First Out ）

• 最少使用策略 LFU （ Least Frequently Used ）

• 最近最少使用策略 LRU （ Least Recently Used ）

使用链表实现一个LRU缓存淘汰算法：

维护一个有序单向链表，链表内最靠尾部的数据是最早访问的（即将被淘汰的），每当有一个新的数据被访问时，可以从头遍历链表：

• 如果查找到对应数据，将此数据提取（删除并新增）到链表的头部；
• 如果没有查找到该数据，则检查此时缓存量是否达到阈值：
  • 如果未满直接插入该数据到链表头部；
  • 如果已经满了就山粗链表尾部节点的数据，将新数据插入到链表头部；

利用 CPU 的缓存机制

CPU 在从内存读取数据的时候，会先把读取到的数据加载到 CPU 的缓存中。而 CPU 每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个
数据块 ( 这个大小我不太确定。。 ) 并保存到 CPU 缓存中，然后下次访问内存数据的时候就会先从 CPU 缓存开始查找，如果找到就不需要再从内存中取。这样
就实现了比内存访问速度更快的机制，也就是 CPU 缓存存在的意义 : 为了弥补内存访问速度过慢与 CPU 执行速度快之间的差异而引入。
对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到 CPU 缓存这样执行速度会快于存储空间不连续的链表存
储。