# 链表
- 链表（Linked list）通过“指针”将一组零散的内存块串联起来使用；而数组需要一块连续的内存空间来存储
- 链表结点，除了储存数据之外，还需要记录链上的下一个结点的地址：后继指针；单链表中，尾结点指向空。
- 链表本身没有大小的限制，天然地支持动态扩容；但链表相比数组，内存消耗会翻倍；对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片

- 数组的插入、删除操作，时间复杂度是 O(n)；链表的插入和删除操作，只需要考虑相邻结点的指针改变，对应的时间复杂度是 O(1)
- 数组访问元素，通过寻址公式就能直接计算出对应的内存地址，O（1）时间复杂度；而链表访问元素，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点 O(n)

- 循环链表：与单链表唯一区别是，尾结点指针指向链表的头节点；
- 双向链表：结点不仅储存后继指针，还有前驱指针，指向前面的结点；
    - 双向链表要比单链表占用更多的内存空间
    - O(1) 时间复杂度的情况下找到前驱结点，在**某些情况**下的插入、删除等操作都要比单链表简单、高效。
        - 删除结点中“值等于某个给定值”的结点：需要从头结点开始遍历对比，直到找到值等于给定值的结点，然后删除
        - 删除给定指针指向的结点：删除某个结点 q 需要知道其前驱结点，而单链表需要遍历查找 O(n)，而双向链表直接获取，O(1)
        - 插入操作同理
        - 对于有序链表，双向链表的按值查询的效率也要比单链表高一些
- 双向循环链表        
        
- **空间换时间**的设计思想  
- 缓存实际上就是利用了空间换时间的设计思想，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了
- 链表实现 LRU：
    - 有序单链表，越靠近链表尾部的结点是越早之前访问的
    - 当有一个新的数据被访问时，我们从链表头开始顺序遍历链表：
        - 遍历得到对应结点，并将其从原来的位置删除，然后再插入到链表的头部
        - 结点不在链表中，则：
            - 缓存未满，则将此结点直接插入到链表的头部；
            - 缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部