前言

本篇文章主要解决如下几个问题：

链表和数组相比有哪些不同点？它的优缺点是什么？
链表有哪些类别？它们各自的优缺点是什么？
如何使用链表实现LRU算法？

链表相对于数组而言，是两种不同的内存组织方式，链表不需要连续的内存空间，天然支持动态扩容，而且不像数组扩容那样需要搬运数据。链表大小等于实际使用大小，不存在浪费空间的现象。链表适合插入和删除操作，时间复杂度为O(1)，但是并不意味着适合非常频繁地插入和删除，因为那样会导致频繁地申请内存和释放内存，容易造成内存碎片，从而提高GC的频率。

一、单链表

每一块内存区域称为一个节点，每个节点有两块区域，数据域保存节点数据，指针域指向下一个节点的地址。其中，头节点是整个链表的基地址，通过它可以遍历整个链表；尾节点的指针值为空，不指向任何地址。

单链表比较适合插入和删除操作，时间复杂度为O(1)，注意此处不包含查找到该元素的时间，但是查询操作效率较低，时间复杂度为O(n)；

单链表结构示意

二、双向链表

每一块内存区域称为一个节点，每个节点有三块区域，前指针域指向上一个节点的地址，数据域保存节点数据，后指针域指向下一个节点的地址。和单链表相比，存储相同多的数据，双向链表需要的存储空间更多。

双向链表的插入、删除和查询操作都要比单链表的相同操作的效率更高：

插入

如果需要在第k个节点处插入一个新的节点，那么单链表需要找到前一个节点，时间复杂度为O(n)，而双向链表只需要往前遍历一个节点就能找到，时间复杂度为O(1)。
删除

如果是需要删除给定的元素，那么就只能从第一个节点开始遍历，这种情况两种链表的时间复杂度是一样的；但是如果是给定需要删除元素的指针，那么单链表因为要找到前一个元素p，使得p.next指向待删除元素的下一个节点，所以时间复杂度为O(n)，而双向链表则只需要往前遍历一个节点就能找到，时间复杂度为O(1)。
查询

对于有序链表，每次查找元素k，双向链表可以根据和当前节点的值的大小比较来决定往前遍历还是往后遍历，而单链表只能往后或者从头结点重新开始遍历。

因此，即便双向链表比较占用空间，但这是一种空间换时间的设计思想，使用场景反而比单链表更多。