一、 单向链表
1. 动态数组对比链表有一个明显的缺点是什么？
- 不能做到需要多少内存就申请内存
2. 我们在进行链表方法设计的时候，发现链表的方法和动态数组的方法基本是一样的。这时如果我们采用让它们都继承共同父类 List 这种做法好吗？
- 这种使用继承的做法不好，因为他们虽然有共同的
方法声明，但是基本没有共同的方法实现，所以不适合使用继承的方式。 - 最佳的方式应该是使用
接口
3. 在我们使用 List 作为动态数组和链表的共同接口后，继续进行链表实现时，我们发现动态数组和链表还是有共同代码的，比如对 inde 的边界检查代码、size() 、isEmpty() 等等。这时候该怎么办呢？
- 让他们共同继承一个
AbstractList，这个抽象父类，这个父类通常不对外暴露，仅仅是存放公共代码
4. 思考：static final int ELEMENT_NOT_FOUND = -1 这句代码，应该存放在 抽象类 AbstractList 中还是放在 接口 List 中?
- 放在 AbstractList 和 List 中，外部都可以使用
- 但是我们设计的初衷是 List 是对外暴露的，AbstractList 是不对外暴露的，所以我们应该放在 List 中，调用的时候可以如下使用
list.indexOf(20) == List.ELEMENT_NOT_FOUND即可
设计过程（左图）、最终方案（右图）
5. 我们在对链表相关思考的时候，怎么绘制链表示意图，帮助我们思考问题呢？
image.png
5. 面试问题总结（链表问题大部分可以用什么方法解决？）
无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。然而面试的时候经常碰见诸如获取倒数第k个元素，获取中间位置的元素，判断链表是否存在环，判断环的长度等和长度与位置有关的问题。这些问题都可以通过灵活运用双指针来解决。
- Tips：双指针并不是固定的公式，而是一种思维方式~
6. 练习：删除链表中的节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
7. 练习：链表反转
- 迭代取出链表的每一个节点，往新链表的头部插入
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode();
ListNode oldHead = new ListNode();
oldHead.next = head;
while (oldHead.next != null) {
ListNode tempNode = oldHead.next;
oldHead.next = oldHead.next.next;
tempNode.next = newHead.next;
newHead.next = tempNode;
}
return newHead.next;
}
}
8. 练习（说解题关键点）：判断一个链表是否有环
- 解题关键
快慢指针的使用 ； 为什么设计快指针走两步、慢指针走一步呢？ - 快慢指针只差一步，这样可以保证有环的情况下，一定会相遇（不会错过）
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
9. 单向链表练习（TODO）
image.png
二、 动态数组 和 单向链表 的复杂度分析
1. ArrayList 的 get、set 方法的时间复杂度是多少？
- O(1)
2. ArrayList 的 remove、add 方法的最好时间复杂度、最坏时间复杂度、平均时间复杂度分别是多少？
- 最好时间复杂度：O(1)
- 最坏时间复杂度：O(n)
- 平均时间复杂度：O(n)
3. LinkedList 的 get、set、add、remove 方法的时间复杂度是多少？
- 最好时间复杂度：O(1)
- 最坏时间复杂度：O(n)
- 平均时间复杂度：O(n)
image.png
4. 什么是均摊时间复杂度？什么时候使用这个时间复杂度进行估算？
- 均摊时间复杂度：经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
- 比如调用动态数组 add 函数的时候（时间复杂度是
O(1)），可能会触发扩容(时间复杂度是O(n))
image.png
5. 如果要对动态数组进行缩容，在什么时机对其进行缩容操作？缩容的思路是什么？
- 在 remove 方法里面进行缩容
- 缩容的方式和扩容类似（不是相反哟）
image.png
6. 如果动态数组的 扩容倍数 和 缩容倍数 设计不得当，有可能导致出现复杂度的什么问题？
- 如果扩容倍数 乘以 缩容倍数
等于 1，就会导致复杂度震荡问题
三 、双向链表
1. 绘制出单向链表、双向链表的结构图？并说出双向链表对于单向链表的优势？
单向链表
双向链表
2. 思考如下 clear 代码，能让双向链表中存储的对象成功被释放吗？会存在循环引用吗？
public void clear() {
size = 0;
first = null;
last = null;
}
- 会存在循环引用；但是能被 gc 回收。
- 因为 gc 在判断有没有引用的时候，还会判断引用的类型。如果不是
gc root 对象（比如局部变量指向的对象），就会被释放。
3. 绘图描述向双向链表中添加节点？（一般情况是什么？临界情况有几个？）
- 首先声明：
先考虑一般情况，再看临界情况，这种思路在开发中超级重要 - 一般情况：链表中有数据，且 size > 2，然后往
非头部、非尾部添加节点 - 临界情况：① 往
链表头部添加 ② 往链表尾部添加 ③ 往空链表中添加
4. 双向链表 VS 单向链表的删除节点操作的时间复杂度对比？
image.png
5. 什么时候使用双向链表 或 动态数组？分别描述在各种情况下的选择(至少说三种)？
牢记此图
四、循环链表
1. 绘制单向循环链表的结构图？
image.png
2. 绘制出双向循环链表的结构图？
image.png
3. 练习 - 约瑟夫问题？（TODO）
image.png
