经典的链表应用场景,那就是 LRU 缓存淘汰算法
常见的缓存淘汰策略:
这些策略你不用死记,我打个比方你很容易就明白了。假如说,你买了很多本技术书,但有一天你发现,这些书太多了,太占书房空间了,你要做个大扫除,扔掉一些书籍。那这个时候,你会选择扔掉哪些书呢?对应一下,你的选择标准是不是和上面的三种策略神似呢?
数组需要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于 100MB,仍然会申请失败。
链表并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,所以如果我们申请的是 100MB 大小的链表,根本不会有问题。
image
三种最常见的链表结构
链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。
image
从单链表图中,你应该可以发现,其中有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。
插入和删除:
查找:
image
循环链表是一种特殊的单链表。
image
与单链表唯一的区别在尾节点:
与单链表比优点:从链尾到链头比较方便。
单链表只有一个方向,节点只有一个后继指针 next 指向后面的节点。 而双向链表,它支持两个方向,每个节点不止有一个后继指针 next 指向后面的节点,还有一个前驱指针 prev 指向前面的节点。(LinkedHashMap)
image
从图中可以看出来,双向链表需要额外的两个空间来存储前继节点和前驱节点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。 虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。
从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
在实际的软件开发中,从链表中删除一个数据无外乎这两种情况:
不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,然后再通过我前面讲的指针操作将其删除。
尽管单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
我们已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到 p->next=q,说明 p 是 q 的前驱结点。
双向链表这种情况比较有优势。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要 O(n) 的时间复杂度,而双向链表只需要在 O(1) 的时间复杂度内就搞定了!
如果我们希望在链表的某个指定结点前面插入一个结点,双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定,而单向链表需要 O(n) 的时间复杂度。
查询: 除了插入、删除操作有优势之外,对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。因为,我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。
image
数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别,它们插入、删除、随机访问操作的时间复杂度正好相反。
时间复杂度 | 数组 | 链表 |
---|---|---|
插入删除 | O(n) | O(1) |
随机访问 | O(1) | O(n) |
你可能会说,我们 Java 中的 ArrayList 容器,也可以支持动态扩容啊?我们上一节课讲过,当我们往支持动态扩容的数组中插入一个数据时,如果数组中没有空闲空间了,就会申请一个更大的空间,将数据拷贝过去,而数据拷贝的操作是非常耗时的。
我举一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据,这个时候已经没有空闲空间了,当我们再插入数据的时候,ArrayList 会申请一个 1.5GB 大小的存储空间,并且把原来那 1GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时?
除此之外,如果你的代码对内存的使用非常苛刻,那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针,所以内存消耗会翻倍。而且,对链表进行频繁的插入、删除操作,还会导致频繁的内存申请和释放,容易造成内存碎片,如果是 Java 语言,就有可能会导致频繁的 GC(Garbage Collection,垃圾回收)。
所以,在我们实际的开发中,针对不同类型的项目,要根据具体情况,权衡究竟是选择数组还是链表。
我的思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。
这样我们就用链表实现了一个 LRU 缓存,是不是很简单?
现在我们来看下 m 缓存访问的时间复杂度是多少。因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为 O(n)。
实际上,我们可以继续优化这个实现思路,比如引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到 O(1)。因为要涉及我们还没有讲到的数据结构,所以这个优化方案,我现在就不详细说了,等讲到散列表的时候,我会再拿出来讲。
单链表的第一个结点叫头结点,最后一个结点叫作尾结点,尾结点指向一个空指针NULL。插入和删除的时间复杂度为O(1),查找的时间复杂度为O(n)。
循环链表的最后一个结点指向链表头结点,适合处理环形数据结构。
双向链表不止有一个后继指针 next 还有一个前驱指针 prev ,同样的数据双向链表比单链表占更多的内存空间。 删除给定的结点,双向链表时间复杂度为O(1),单链表的时间复杂度为O(n)。
ArrayList:支持动态扩容的数组,但当没有空闲空间了,就会申请一个更大的空间,将数据拷贝过去,而数数据拷贝是非常耗时的。