1.链表的一个景点应用场景 

 LRU缓存淘汰算法: 缓存是一种提高数据读取性能的技术,在硬件设计、软件发开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。 缓存的大小有限,当缓存被用满时,那些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定,常见的缓存淘汰策略有三种:先进先出策略FIFO(First In First Out),最少使用策略LFU(Least Frequently Used),最近最少使用策略LRU(Least Recently Used)。 

那么,如何使用链表来实现LRU缓存淘汰策略呢?

 2.链表的底层结构 

数组需要一块连续的内存空间来存储,相对于数组,链表不需要连续的内存块,它通过“指针”将一组零散的内存块串联起使用,链表的结构有很多,最常见的三种链表结构有:单链表、双向链表、循环链表。 

 2.1单链表

 链表通过指针将一组零散的内存块串联在一起,其中,我们把内存块称为链表的“结点”。为了将链表的所有结点串起来,每个结点除了存储数据之外,还需要记录链表上边下一个结点的地址。我们将这个记录下一个结点的指针叫做后继指针next。 在单链表中,有两个结点比较特殊,分别是第一个结点最后一个结点,我们习惯性地将第一个结点叫做头结点最后一个结点叫做尾结点。其中,头结点用来记录链表的基地址,我们可以通过它来遍历整个链表。而尾结点的特殊之处在于:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表的最后一个结点。  

链表也同数组一样支持查找、插入、删除操作。数组在进行插入、删除的操作的时候,为了保持内存空间的连续性,需要做大量的数据搬移,所以时间复杂度是O(n)。而在链表中插入或者删除一个数据,并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就是不连续的。针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以,链表进行插入和删除的时间复杂度为O(1)

有利就有弊,链表想要随机访问第K个元素,就没有数组那么高效了,由于链表中的数据存储并非是连续的,所以无法像数组那样根据首地址和下标,通过寻址公式直接获得对应元素的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的节点。

2.2循环链表

循环链表是一种特殊的单链表。它与单链表的唯一区别就在尾结点单链表尾结点指针指向空地址,表示这是最后的结点了。而循环链表尾结点指针指向链表的头结点,像一个一样首尾相连,所以叫做"循环"链表

与单链表相比,循环链表的优点是从链尾到链头比较方便,当要处理的数据具有环型结构特点时,就特别适合采用循环链表,比如著名的约瑟夫问题

2.3双向链表

单链表只有一个方向,结点只有一个后继指针next指向后面的节点。而双向链表,顾名思义,它支持两个方向,每个结点不止有一个后继指针next指向后面的结点还有一个前驱指针prev指向前面的结点。由于双向链表需要额外的两个空间来存储后继结点个前驱结点,所以,存储同样多的数据,双向链表比单向链表占用更多的内存空间。虽然浪费空间,但是双向链表支持双向遍历,这带来了双向链表操作的灵活性。


双向链表适合解决哪种问题?

双向链表可以支持O(1)时间复杂度的情况下找到前驱结点,正是这样一个原因,使得双向链表在某些情况下的插入、删除等操作比单链表简单、高效。

在实际的软件开发中,从链表中删除一个数据无外乎这两种情况

a)删除结点中“值等于某个给定值”的结点;

b)删除给定指针指向的结点

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,然后再通过之前说的指针操作将其删除。

尽管单纯的删除时间复杂度是O(1),但是遍历查找的时间是主要的耗时点,对应的时间复杂度为O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为O(n)

对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点q需要知道其前驱结点,而单链表并不支持直接获取前驱结点,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到p->next=q,说明p是q的前驱结点,

但是对于双向链表来说,这种情况就比较有优势了,因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要O(n)的时间复杂度,而双向链表只需要在O(1)的时间复杂度内就搞定了。

同理,我们在链表的某个指定结点前面插入一个结点,双向链表可以再O(1)的时间复杂度内搞定,而单向链表需要O(n)的时间复杂度。

java LinkedHashMap容器的实现原理使用了双向链表这种数据结构。

这里有一个很重要的思想:用空间换时间的设计思想。当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高,但时间复杂度相对较低的算法或者数据结构。


开篇缓存的例子就是应用了空间换时间的设计思想。

对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化,而消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。


循环链表和双向链表可以整合成新的版本:双向循环链表。


3.链表和数组性能比较

数组:插入删除->O(n),随机访问->O(1)

链表:插入删除->O(1),随机访问->O(n)


数组和链表的比较,并不能局限于时间复杂度,而且在实际的软件开发中,不能仅仅利用复杂度就决定使用哪个数据结构来存储数据。


数组简单易用,在实现上使用的是连续的内存空间,可以借助CPU的缓存机制预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。

数组的缺点大小固定,一经声明就要占用整个块连续内存空间。如果声明的数组过大,系统没有足够的连续内存空间分配给它,导致“内存不足(out of memory)” 。如果声明的数组过小,则可能出现不够用的情况,这是只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时链表本身没有大小的限制,天然地支持动态扩容


4.开篇解答

维护一个单链表越靠近链表尾部的结点是越早之前访问的,当有一个新的数据被访问时,从链表头开始顺序遍历链表

a)如果此数据之前已经被缓存在链表中,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部

b)如果此数据不在缓存链表中,又可以分为两种情况:

b1)如果此时缓存没满,直接将此结点插入到链表的头部

b2)如果此时缓存已满,则将链表尾结点删除,将新的数据结点插入链表的头部


在不用其他数据结构优化的情况下,这种方案的缓存访问的时间复杂度是O(n)


5小结

链表和数据一样,也是非常基础、非常常用的数据结构。不过链表要比数组稍微复杂,从普通的单链表衍生出来好几种链表结构,比如双向链表、循环链表、双向循环链表

和数组相比,链表适合插入、删除操作频繁的场景查询的时间复杂度较高。在具体的软件开发中,要对数组和链表的各种性能进行对比,综合来选择使用两者中的哪一个。