0x01 链表结构
与数组相反，链表通过指针将一组零散的内存串联起来使用
常见有三种链表：单链表、双向链表、循环链表
单链表
单链表只有一个方向，每个链表元素包含数据和一个指向下一结点的指针，尾节点指向null
单链表的插入和删除操作时间复杂度都是O(1)，查找需要从头结点开始遍历，所以时间复杂度是O(n)
这里插入和删除都是在明确结点位置的情况下位O(1)，但是在实际情况中，一般要先找到结点才能进行插入和删除操作
循环链表
循环链表是一种特殊的单链表，循环链表的尾结点指向头结点，整个链表构成一个环
循环链表的优点是从链表尾到链表头非常方便，当要处理的数据具有环形结构特点时适合使用循环链表，例如约瑟夫问题
双向链表
双向链表每个结点包含数据和指向前驱和后继的两个指针
相比单链表，双向链表通过前驱指针，可以方便的找到前驱结点，在插入和删除的时候，就有很大优势
- 删除
如果我们已经找到要删除的元素，我们还需要找到删除元素的前驱结点，从而把前驱结点指向正确的位置，这时候双向链表可以很方便的找到前驱结点
- 插入
同理当我们要在指定元素前面插入结点时，双向链表也可以很方便的找到前驱结点，从而实现插入操作
所以，尽管单链表更省空间，实际编程语言中大多使用双向链表，例如java中的LinkedList就是使用的双向链表
数组 VS 链表
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入、删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
在实际的使用过程中，也不能局限于时间复杂度去选择，数组操作方便，但是占用的是连续的内存，并且大小固定，如果超出数组大小，需要手动扩容，迁移整个数组，开销很大，链表内存空间不连续，大小没有限制，但是每个结点相比数组都多了指针，所以会占据更多空间
0x02 问题 LRU缓冲算法
缓存淘汰策略
当缓存被用满时，哪些数据应该被清理出去，常见的策略有三种
1、先进先出FIFO(first in first out)
2、最少使用策略LFU(least frequently used)
3、最近最少使用策略LRU(least recently used)
所谓LRU就是将最近使用最少的删除
链表实现
思路
1、维护一个单链表，每个结点都是缓存的元素，越后面的结点是越少访问的
2、每次有新元素，从头遍历链表，如果找到了，那么从链表中删除，并在头结点插入这个元素
3、如果没有找到，那么直接在头结点插入元素，如果缓存满了，删除尾结点，然后在头部插入元素
这里每次查找缓存都要遍历链表，可以优化一下，使用散列表记录数据，后面学到散列表在补上代码
0x03 课后思考
如何判断一个字符串是否是回文字符串的问题，使用单链表
// 定义单链表类型
case class Node[E](var data:E,var next:Option[Node]){}
// scala case class可以直接使用==比较，不比较地址
def checkPhrase(node:Option[Node]): Boolean ={
if (node.isEmpty || node.get.next.isEmpty){
return true
}
// 定义快慢指针
var slow,fast = node
// fast总是在奇数位置，从1到3到5到7 slow指向中点或者后半段第一个结点
while (fast.isDefined && fast.get.next.isDefined){
slow = slow.get.next
fast = fast.get.next.get.next
}
var pre:Option[Node] = None
var current:Option[Node] = node
while (current != slow){
var tmp = current.get.next
current.get.next = pre
pre = current
current = tmp
}
// fast为空，则共有偶数个结点，slow位于后半段的第一个
if (fast.isEmpty){
pre == slow
}else{
pre == slow.get.next
}
}
