链表
链表 【转载】
原文:https://www.jianshu.com/p/2351eabde3ef
空间换时间 & 时间换空间
空间换时间的设计思想: 当内存空间充足的时候，为了追求代码更快的执行速度，就可以选择空间复杂度度相对较高，使用时间复杂度相对很低的算法或数据结构
时间换空间的设计思想：内存空间比较紧缺时，可以选择空间复杂度相对较低，但时间复杂度相对很高的算法或数据结构，来节省内存
缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果通过缓存技术，事先将数据加载到内存中，虽然会比较消耗内存空间，但是每次数据查询速度就大大提高了。
对于执行较慢（消时长）的程序，可以通过消耗更多的内存来进行优化；
对于内存消耗过多的程序，可以通过消耗更多的时间来减低内存的消耗
链表的存储结构
数组需要一块连续的内存空间来存储，需要事先申请需要的内存空间；而链表通过"指针"将一组零散的内存块串联起来使用，不会占用还未使用的内存空间
image
三种常见的链表结构
单链表
链表通过指针将一组零散的内存块串联在一起，内存块称为链表的结点。每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，叫做后续指针next
image
上图中有两个特殊的结点，分别是第一个结点（头结点）和最后一个结点（尾结点）。
头结点用来记录链表的基地址，用它可以遍历得到整条链表。
尾结点指向一个空地址Null，表示这是链表上最后一个几点。
循环链表
循环链表跟单链表的区别在尾节点指针式指向链表的头结点
image
和单链表相比，循环链表的优点是从链尾到链头比较方便。
当要处理的数据结构具有环形结构的特点时，采用循环链表实现代码会简洁很多。
双向链表
双向链表支持两个方向，每个结点同时有后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点
image
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，存储同样的数据，双向链表要比单链表占用更多的内存空间。
优点是双向链表可以支持O(1)时间复杂度情况下找到前驱结点。
双向循环链表
image
三种基本操作
删除操作
从链表中删除一个数据有两种情况:
- 删除结点中“值等于某个给定值”的结点
该情况下，各种链表都需要从头开始遍历对比，直到找到值等于给定的值的结点，然后再删除
单纯的删除操作时间复杂度都是O(1)，但是遍历查找的时间复杂度是O(n)。链表操作的总时间复杂度为O(n)
- 删除给定指针指向的结点
删除某个结点q需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以单链表还是要从头开始遍历链表，直到 p --> next = q ，说明 p 是 q 的前驱结点。
双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。
所以，单链表删除操作的需要O(n)的时间复杂度，而双向链表需要O(1)的时间复杂度
image
插入操作
image
如果希望再链表的某个结点前插入一个点解，双向链表需要O(1)的时间复杂度；
单向链表需要O(n)的时间复杂度，因为单向链表需要从头结点开始遍历，知道找到前驱结点。
查询操作
链表的随机访问第k个元素，必须根据指针一个结点一个节点的依次遍历，直到找到相应的结点。链表随机访问需要O(n)的时间复杂度
对于一个有序链表，双向链表的按值查询的效率会比单链表高一点。记录上次查找的位置 p ，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，双向链表平均只需要查找一半的数据。
链表Vs数组的性能比较
数组和链表的时间复杂度比较
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入删除 | O(n) | O(n) |
| 随机访问 | O(1) | O(n) |
数组简单易用，在实现上是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。
链表再内存中并不是连续存储的，所以对CPU缓存不友好，没办法有效预读
数组存在拷贝现象，假如你的数组大小已经填满，而你想扩容，此时为了扩容就会把原先的数据全部拷贝到新创建的数组中，这个操作的开销是非常大的。
但如果对内存的使用非常苛刻数据就更适合，因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。
对链表进行频繁的插入，删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，对于java语言，就有可能导致频繁的GC(Garbage Collection，垃圾回收)。
LUR 缓存
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的```CPU缓存、数据库缓存、浏览器缓存``等等。
常见的缓存淘汰策略
- 先进先出策略FIFO（First In, First Out）
- 最少使用策略LFU （Least Frequently Used）
- 最近最少使用策略LRU （Least Recently Used）
假如你买了很多本技术书，但有一天发现，这些书太多了，太占书房空间了，你要做个大扫除，那这个时候，扔掉一些书籍。你会选择扔掉那些书呢？
LRU缓存的实现
思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表
- 如果此数据之前已经被缓存链表了，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表头部
- 如果此数据没有在缓存链表中，则将此结点插入到链表的头部。
如果此时缓存超过容量，则链表末尾结点删除。
public class LRU {
public static void main(String[] args) {
@SuppressWarnings("serial")
Map<String, String> map = new LinkedHasMap<String, String>(15, 0.75f, true){
// 重写这个方法的目的是当entry超过5的时候，会将最先放入（即最近最少使用）的entry 删除
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(Map.Entry<String, String> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));)
}
return sb.toString();
}
};
}
}
以上
