0x01 链表结构

与数组相反，链表通过指针将一组零散的内存串联起来使用

常见有三种链表：单链表、双向链表、循环链表

单链表

单链表只有一个方向，每个链表元素包含数据和一个指向下一结点的指针，尾节点指向null

单链表的插入和删除操作时间复杂度都是O(1)，查找需要从头结点开始遍历，所以时间复杂度是O(n)

image

这里插入和删除都是在明确结点位置的情况下位O(1)，但是在实际情况中，一般要先找到结点才能进行插入和删除操作

循环链表

循环链表是一种特殊的单链表，循环链表的尾结点指向头结点，整个链表构成一个环

循环链表的优点是从链表尾到链表头非常方便，当要处理的数据具有环形结构特点时适合使用循环链表，例如约瑟夫问题

双向链表

双向链表每个结点包含数据和指向前驱和后继的两个指针

相比单链表，双向链表通过前驱指针，可以方便的找到前驱结点，在插入和删除的时候，就有很大优势

• 删除

如果我们已经找到要删除的元素，我们还需要找到删除元素的前驱结点，从而把前驱结点指向正确的位置，这时候双向链表可以很方便的找到前驱结点

• 插入

同理当我们要在指定元素前面插入结点时，双向链表也可以很方便的找到前驱结点，从而实现插入操作

所以，尽管单链表更省空间，实际编程语言中大多使用双向链表，例如java中的LinkedList就是使用的双向链表

数组 VS 链表

在实际的使用过程中，也不能局限于时间复杂度去选择，数组操作方便，但是占用的是连续的内存，并且大小固定，如果超出数组大小，需要手动扩容，迁移整个数组，开销很大，链表内存空间不连续，大小没有限制，但是每个结点相比数组都多了指针，所以会占据更多空间

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
    }
}