数组和链表的区别

从底层的存储结构上看一下数组和链表的区别：

数组需要一块连续的内存空间来存储，对内存的要求比较高。
链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

常见的链表结构：单链表、双向链表和循环链表。

单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。

我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址，尾结点指针指向一个空地址NULL。

链表的插入和删除操作，只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。

链表要想随机访问第k个元素，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，需要O(n)的时间复杂度。

循环链表

循环链表是一种特殊的单链表，它的尾结点指针是指向链表的头结点。

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

双向链表

双向链表，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。

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

• 从结构上来看，双向链表可以支持O(1)时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

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

• 删除结点中“值等于某个给定值”的结点；
• 删除给定指针指向的结点。

对于第一种情况，不管是单链表还是双向链表，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过指针操作将其删除。删除操作时间复杂度是O(1)，但遍历查找的时间复杂度为O(n)，所以总时间复杂度为O(n)。

对于第二种情况，因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要O(n)的时间复杂度，而双向链表只需要在O(1)的时间复杂度内！

插入同理。双向链表的按值查询的效率也要比单链表高一些。

LinkedHashMap其中就用到了双向链表。

链表VS数组性能大比拼

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

链表与数组最大的区别：

• 数组的缺点是大小固定
• 链表本身没有大小的限制，天然地支持动态扩容。

解答开篇
如何基于链表实现LRU缓存淘汰算法？

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

1. 如果此数据已经被缓存在链表中，遍历、删除这个数据对应的结点，然后再插入到链表头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   1. 缓存未满，插入到链表头部；
   2. 缓存已满，删除链表尾结点，将新数据结点插入链表头部。

因为需要遍历链表，所以时间复杂度为O(n)。