文章为极客时间《数据结构与算法之美》的学习笔记。
学习要点：空间换时间的设计思想。
什么是链表？
链表通过指针将一组零散的内存块串联在一起。把内存块称为链表的“结点”。为了将所有结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，将记录下个结点地址的指针叫做后继指针next。
第一个阶段叫做头结点，最后一个结点叫做尾结点。
单链表.png
在链表中插入或者删除一个数据，非常快速，不需要像数组一样为了保持内存的连续性而搬移结点，因为链表的存储空间是不连续的。
但是链表想要随机访问某个元素，需要依次从遍历找到相应的阶段，没有数组高效。
常见链表结构：
- 单链表：尾结点指向空地址
- 循环链表：特殊的单链表，尾结点指向链表的头结点，首尾相连
- 双链表：每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点
- 双向循环链表：结合了循环链表和双链表的特性
链表与数组的性能比较：
链表和数组是两种截然不同的内存组织方式，因为内存存储的区别，在插入、删除、随机访问操作的时间复杂度正好相反：
| 复杂度 | 数组 | 链表 |
|---|---|---|
| 删除、插入 | O(n) | O(1) |
| 访问 | O(1) | O(n) |
数组的缺点是大小固定，一经声明就要占用整块连续内存空开，而链表本身没有大小的限制，天然支持动态扩容，这也是它与数组最大的区别。
实战
1.基于链表实现LRU(最近最久未使用)算法
思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
class LRUCache(val capacity: Int) {
private var map: HashMap<Int, Node> = hashMapOf()
private var linkedList = LinkedList()
fun get(key: Int): Int {
val value = map[key]?.value ?: return -1
put(key, value)
return value
}
fun put(key: Int, value: Int) {
val node = Node(key, value)
//key 是否存在,存在的话从map获取key 并且更新内容返回,更新链表的头结点
//key 当前不存在,更新链表头结点
if (map.containsKey(key)) {
linkedList.delete(map[key])
linkedList.addToHead(node)
} else {
//容量已经满了,获取出需要清除的key
if (capacity == map.size) {
linkedList.deleteTail()
map.remove(key)
}
linkedList.addToHead(node)
}
map[key] = node
}
}
class LinkedList {
private var headNode = Node(0, 0)
private var tailNode = Node(0, 0)
init {
headNode.next = tailNode
}
//删除链表的某个结点
fun delete(node: Node?) {
}
//将新结点添加到链表的头部
fun addToHead(node: Node) {
}
//删除链表的最后一个结点
fun deleteTail() {
}
}
class Node(var key: Int, var value: Int, var next: Node? = null)
2.基于数组实现LRU算法
3.判断一个字符串是否是回文字符串
4.链表反转
课外阅读：
- 约瑟夫问题（丢手绢问题）：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
- LinkedHashMap 的实现原理中用到了双向链表这种数据结构。
- LFU：选择最近时期使用最少的数据进行淘汰
