链表

数组须要一块间断的内存空间来存储，对内存的要求比拟高。如果咱们申请一个 100MB 大小的数组，当内存中没有间断的、足够大的存储空间时，即使内存的残余总可用空间大于 100MB，依然会申请失败。
而链表恰恰相反，它并不需要一块间断的内存空间，它通过“指针”将一组零散的内存块串联起来应用，所以如果咱们申请的是 100MB 大小的链表，基本不会有问题。

它跟数组一样，也是十分根底、十分罕用的数据结构。不过链表要比数组略微简单，从一般的单链表衍生进去好几种链表构造，比方双向链表、循环链表、双向循环链表。和数组相比，链表更适宜插入、删除操作频繁的场景，查问的工夫复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行比照，综合来抉择应用两者中的哪一个。

单链表

循环链表

双向链表

双向循环链表

应用链表实现一个 LRU 缓存

保护一个有序单链表，越凑近链表尾部的结点是越早之前拜访的。当有一个新的数据被拜访时，咱们从链表头开始程序遍历链表。

1. 如果此数据之前曾经被缓存在链表中了，咱们遍历失去这个数据对应的结点，并将其从原来的地位删除，而后再插入到链表的头部。

2. 如果此数据没有在缓存链表中，又能够分为两种状况：

   1. 如果此时缓存未满，则将此结点直接插入到链表的头部；
   2. 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。这样咱们就用链表实现了一个 LRU 缓存