一、链表的存储结构
链表不需要连续的存储空间，它通过”指针”将一组零散的内存块串联起来使用
后继指针：链表里面记录下一个节点的地址的指针
头结点：链表的第一个节点，头结点记录了链表的基地址，通过它可以遍历得到整条链表
尾结点：链表的最后一个结点，尾结点指向一个空地址NULL，表示这是链表的最后一个结点
二、单链表的查找、插入、删除操作
链表的插入和删除的复杂度为：O(1)
通过下标随机访问：链表比较慢，因为需要根据后置节点一个一个的遍历，直到找到相应的结点，复杂度为O(n)
三、循环链表
四、双向链表
五、通过有序单链表实现LRU缓存
维护一个有序单链表，越靠近尾结点的就是越早之前访问的
当有一个新的数据被访问时，从链表头开始顺序遍历链表
1、如果数据以后被缓存在链表中，遍历得到这个数据对应的结点，将其从原来的位置删除，再插入到链表的头部
2、如果数据没有在链表中，又分为2种情况：
- 如果此时缓存未满，则将此节点直接插入到链表的头部
- 如果此时缓存已满，则删除链表尾结点，再将新的数据插入到链表的头部
这样实现的时间复杂度为O(n)
后续我们可以通过散列表，将时间时间复杂度降到O(1)
若有收获，就点个赞吧
0 人点赞
