数据结构第一季 Day03 单向链表、双向链表

一、 单向链表

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