链表
空间利用率链表>数组
链表分类
单链表
双向链表
LinkedHashMap循环链表
双向循环链表
双向链表多了一个指针存储前驱指针，空间换时间思想
应用：LinkedHashMap？？
数组与链表的比较
时间复杂度
- 插入:数组O(n) 链表O(1)
- 随机访问:数组O(1) 链表O(n)
数组连续存储空间
- 可借助CPU缓存机制，预读数组中的数据效率更高
- 大数组对碎片化内存利用不足，易导致内存不足；
链表
- 额外指针存储浪费空间，不适合内存要求苛刻的场景；
- 链表频繁删除和插入，导致频繁的内存申请和释放，易造成内存碎片，如果是JAVA可能导致频繁GC
循环链表
如何判断满/空？
- 方式1
rear 尾进，front头出
空队列 rear==front
满队列 （rear+1）% size = front
缺点：少用一个空间 - 方式2、3
思考题
字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？
- 快慢指针确定中间节点
判断快指针next和next.next不为空，
偶数时得到的节点是前半部分最后一个节点d1
奇数时得到的节点是中间节点d1
获取得到节点d1的next都是后半部分节点头结点 - 翻转后半部分
- 比较前后两部分是否相同。
- 还原