封面画师：ツチヤ封面ID：82372386

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

1. 复杂度

1.1 算法的评估

事后统计法

如果从执行效率上进行评估，会想到这么一种方案：比较不同算法对同一组输入的执行处理时间。这种方法也叫作： 事后统计法

但是这种方式有明显的缺点 ：

执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写响应的代码
测试数据的选择比较难保证公正性

那么我们应该怎么评判一个算法的优劣呢？

正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
时间复杂度（Time Complexity）：估算程序指令的执行次数（执行时间）
空间复杂度（Space Complexity）：估算所需占用的存储空间

1.2 时间复杂度的估算

本节涉及的 n 不是指参数，而是指数据规模

public static void test1(int n) {
    // 1 + 2n + n * (1+ 3n)
    // 3n^2 + 3n + 1
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            System.out.println("test");
        }
    }
}

上述示例时间复杂度为： 3n² + 3n + 1

大O表示法为： O(n²)

public static void test2(int n) {
    // 忽略 while 内判断次数，只算输出语句执行次数
    // 假设 n = 16, 则：8 4 2 1 会执行4次， 16 = 2^4
    // 4 = log2(16)
    while ((n = n / 2) > 0){
        System.out.println("test");
    }
}

上述示例时间复杂度为： log₂ n

大O表示法为：O(logn)

public static void test3(int n){
    // 1 + 2 * log2(n) + log2(n) * (1 + 3n)
    for (int i = 1; i < n; i+= i){
        // 1 + 3n
        for (int j = 0; j < n; j++){
            System.out.println("test");
        }
    }
}

上述示例时间复杂度为： 3log₂ n + 3nlog₂ n + 3n +2

大O表示法为：O(nlogn)

虽然上述的方式可以估算出程序的执行次数，但是对于某些算式的计算仍然很复杂，因此，我们需要借助另一种方式来计算。

大 O 表示法（Big O）

我们可以可以用大 O 表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度

使用大 O 表示法时，我们 会忽略常数、系数、低阶 ，比如：

9 >> O(1)

2n + 3 >> O(n)

n² + 2n + 6 >> O(n²)

4n³ + 3n² + 22n + 100 >> O(n³)

对于对数，根据换底公式， log₂ n = log₂ 9 * log₉ n，在大 O 表示法中，我们会忽略常数，因此：所有为对数的复杂度，我们都写成： logn

注意：大 O 表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个程序的时间复杂度。

常见时间复杂度

常见复杂度对比：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

时间复杂度的分析

在实际分析时，我们一般会从下面三个方面来分析时间复杂度：

最好情况复杂度
最坏情况复杂度
平均情况复杂度

1.3 空间复杂度的估算

空间复杂度就是估算所需占用的存储空间。比如定义了多少个变量，空间复杂度就有多少。

如今，随着技术的提升，磁盘空间越来越大，我们更加关心时间复杂度，而不是空间复杂度。

1.4 斐波那契数列

// 0 1 1 2 3 5 8 13 ...

// 递归 （存在性能问题）
public static int fib1(int n) {
    if (n <= 1) {return n;}
    return fib1(n - 1) + fib1(n - 2);
}

// 循环
public static int fib2(int n) {
    if (n <= 1) {return n;}
    
    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

这两种方式的时间复杂度：

对于循环方式： O(n)

对于递归方式（存在大量重复调用）：O(2ⁿ)

对比了斐波那契数列的两种算法后，我们发现，算法对于程序的影响很大，那么我们应该怎么优化算法呢？

1、用尽量少的储存空间

2、用尽量少的执行步骤（执行时间）

3、根据情况，还可以“空间换时间”或者“时间换空间”

2. 动态数组

2.1 线性表

什么是数据结构

数据结构是计算机存储、组织数据的方式，数据结构包括：

线性结构（数组、链表、栈、队列、哈希表）
树形结构（二叉树、AVL 数、红黑树、B 树、堆、Trie、哈弗曼树、并查集）
图形结构（邻接矩阵、邻接表）

线性表

线性表是具有 n 个相同类型元素的有限序列（n >= 0）

线性表每一个元素都有一个索引。

假设现在有一个线性表，从 a1 - an：

此时，a1 是首节点（首元素），an 是尾节点（尾元素）。a1 是 a2 的前驱，a2 是 a1 的后继。

2.2 数组

数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。

在 Java 中，这么定义数组：int[] array = new int[]{11, 22, 33};

假设一个 int 类型数据占 4 个字节，那么数组的结构为：

在很多编程语言中，数组有个致命的缺点：无法动态修改容量。但是在实际开发中，我们更希望数组的容量可以动态改变。这个时候就需要用到动态数组。

2.3 接口设计

动态数组（Dynamic Array）接口设计：

清空所有元素 clear()
获取元素的数量 size()
判断动态数组是否为空 isEmpty()
判断是否包含某个元素 contains(E element)
添加元素到尾部 add(E element)
获取某个位置的元素 get(int index)
设置某个位置的元素 set(int index, E element)
向某个位置添加一个元素，且支持插入null add(int index, E element)
删除某个位置的元素 remove(int index)
查看某个元素的索引 indexOf(E element)
数组扩容 / 容量确保（不考虑线程安全） ensureCapacity(int capacity)
封装越界异常 outOfBounds(int index)
普通的范围检查 rangeCheck(int index)
添加元素时的范围检查 rangeCheckForAdd(int index)
打印数组 toString()

2.4 简单接口实现

属性、变量、构造方法

/**
 * @author 默烦
 * @date 2020/6/17
 */
// 动态数组
/*使用范型后，会出现内存管理问题*/
public class ArrayList<E> {
    // 元素的数量 值大于0
    private int size;
    // 所有的元素 存放的地址 而非元素本身1
    private E[] elements;

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    // capacity 动态数组容量
    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        // Java 中所有的类都继承至 java.lang.Object
        // 注意是：Object ， 不是Objects
        elements = (E[]) new Object[capacity];
    }

    public ArrayList() {
//        elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }
}

方法的封装

// 越界异常封装
private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}

// 普通范围检查
private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

// 添加元素的范围检查
// 允许 index = size，当 index 等于 size 时，相当于在数组末尾添加元素
private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}
@Override
public String toString() {
    // 打印效果 size = 3, [99,88,77]
    StringBuilder builder = new StringBuilder();
    builder.append("size=").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0){
            builder.append(", ");
        }
        builder.append(elements[i]);
        /* if (i != size - 1){
                builder.append(", ");
            }*/
    }
    builder.append("]");
    return builder.toString();
}

简单接口实现

// 元素的数量
public int size() {
    return size;
}

// 判断是否为空
public boolean isEmpty() {
    return size == 0;
}

// 判断是否包含某个元素
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}
// 获取index位置的元素
public E get(int index) {
    rangeCheck(index);
    return elements[index];	// O(1)
}

// 设置index位置的元素
public E set(int index, E element) { // O(1)
    rangeCheck(index);
    E old = elements[index];
    elements[index] = element;
    return old;
}

2.5 容量确保

设计思路

1、获取当前数组的容量

2、如果当前容量大于想要设置的容量，不做操作，直接返回

3、反之，设置新容量（假设新容量为旧容量的 1.5 倍）

4、创建一个具有新容量大小的数组

5、将原来的数据拷贝到新数组

6、使用新数组覆盖原数组

代码实现

// 保证要有 capacity 的容量(不考虑线程安全)
private void ensureCapacity(int capacity) {
    // 当前elements.length 为 10，因为默认容量为 10
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    // 新容量为新容量的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
    System.out.println(oldCapacity+"扩容为"+newCapacity);
}

2.6 添加元素

设计思路

根据接口设计，需要设计两种元素添加方式，首先是直接在尾部插入一个元素，然后是在指定位置插入元素。针对第一种方式，只需要将第二种方式指定的位置设置为 size 就可以实现在尾部插入元素。

针对第二种方式：

1、判断参数 index 是否越界

2、容量确保

3、插入位置及其以后的元素全部向后移一个位置

4、需要插入的元素覆盖插入位置的元素

5、数组元素数量加一

代码实现

// 向 index 位置添加一个元素 且默认支持插入空数据 null
public void add(int index, E element) {
    // 如果设计成不插入null
    // if (element == null) return;
    rangeCheckForAdd(index);
    ensureCapacity(size + 1);
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}
// 添加元素到尾部
public void add(E element) {
    // size 值为多少，就往数组下标为 size 的位置添加元素
    //        elements[size++] = element;
    add(size,element);
}

时间复杂度分析

add(int index, E element)：

最好：O(1)
最坏：O(n)
平均：O(n)

add(E element)：

最好：O(1)
最坏：O(n)
平均：O(1)
均摊：O(1)

均摊复杂度

当经过 连续的 多次复杂度比较低的情况后，出现个别复杂度比较高的情况时，需要使用 均摊复杂度 。

所谓均摊，就是将复杂度高的操作的复杂度均摊到前面每一个复杂度低的操作中，然后算得均摊复杂度。

一般来说，均摊复杂度与最好复杂度是相等的。

2.7 清空元素

设计思路

当使用范型后，动态数组可以存储任意类型的元素，但是需要注意的是：

动态数组存储的内容不再是元素本身，而是元素所在的地址。

下面给出的图可以帮助理解：

如果我们要清空动态数组中的元素，首先想到的就是消去栈空间指向堆空间的指针，即：elements = null。但是不建议使用这种方法，因为使用了这种方式，等到后面还要使用这个动态数组时，就需要重新创建对象（新创建对象会消耗资源）。

然后还有第二种方式，可以直接让 size = 0，只要满足了这个条件，数组将相当于清空（因为 size = 0 之后，用户无法访问到数据，就相当于清空了）。在使用了范型后，动态数组内存储的不再是元素本身，而是元素所在的地址 ，这时候还是直接使用 size = 0 的话，对象并没有被销毁，还是会占用空间，并没有达到清空的目标。

因此，还需要将动态数组中存储的地址清空。

代码实现

// 清除所有元素
/*坚持一个思想：
*   能够循环利用的空间留下
*   不能循环利用的空间销毁
* */
public void clear() {
    // 使用范型后
    // 将数组中指向的内存空间进行销毁
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // 表面情况，实际只是 size = 0
    size = 0;
}

2.8 删除元素

设计思路

假设我们需要删除 index = 3 位置的元素时（size = 6），首先想到的是删除这个元素，然后将其后面的元素向前移。其实，我们可以使用后面的元素进行逐一覆盖。

后面的元素会覆盖删除位置的元素，覆盖完成后使用 size-- 即可，但是在使用了范型后，数组中存储的是对象的地址，如果依旧使用前面的方式，最后一个元素将一直得不到销毁，因此使用范型后，还需要将最后一个元素进行销毁。

代码实现

// 删除 index 位置的元素
public E remove(int index) {
    rangeCheck(index);
    E old = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    /*size--;
        elements[size] = null;*/
    // 合并为
    elements[--size] = null;
    return old;
}

// 可以根据传递的元素进行删除
/* public void remove(E element){
        remove(indexOf(element));
    }*/

时间复杂度分析

最好：O(1)
最坏：O(n)
平均：O(n)

2.9 获取索引

设计思路

想要获取索引就要传递一个值（这个值可以是空值），然后遍历数组，将数组中的值与传递的值进行比较，如果相等就返回地址，反之则返回 ELEMENT_NOT_FOUND。

在这里就会涉及一个比较的问题，我们常用的比较方式是 ==，但是使用了范型后，再使用==进行比较，比较的是地址。虽然直接比较地址也是可行的，但如果要 自定义比较方式 就不行了。

如果要自定义比较方式，可以在类中重写 equals() 方法，然后就可以进行比较了。

因此，在编写获取索引的代码时，一般不使用 == 进行比较，而是使用 equals()。

那么如果类中没有重写equals()方法，那岂不是会报错？

并不会！如果没有重写，就默认比较地址。

代码实现

// 查看元素的索引
public int indexOf(E element) {
    // 处理空值
    if (element == null){
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i;
        }
    }else {
        for (int i = 0; i < size; i++) {
            /*if (elements[i] == element) return i;*/
            /* 使用这种方式可以自定义比较方式
                 *  使用这种方式时，实体类需要重写equals()方法才可以自定义
                 * */
            // 注意：是element调用的equals()方法，因为这个时候element一定不为空
            if (element.equals(elements[i])) return i;
        }
    }
    return ELEMENT_NOT_FOUND;
}

2.10 缩容

为什么要缩容

当动态数组经过扩容并添加元素后，然后又可能会出现删除元素或清空数组的情况，出现这种情况后，如果扩容的数组大小没有改变，可能会造成内存的浪费。因此，我们可以考虑缩容。

与扩容一样，缩容也是开辟一个新空间，将原空间数据复制进去，然后销毁原空间。

代码实现

复制一份 ArrayList.java，将其命名为 ArrayList2.java 放置于当前目录下，在 ArrayList2.java 中添加以下代码：

// 当剩余空间占总容量的一半时,就会进行缩容
private void trim(){
    int oldCapacity = elements.length;
    int newCapacity = oldCapacity >> 1;
    // 不缩容的情况
    if (size >= (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) return;
    // 缩容操作
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
    System.out.println(oldCapacity+"缩容为"+newCapacity);
}
// 删除 index 位置的元素
public E remove(int index){
    rangeCheck(index);
    E old = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[--size] = null;
    trim();	// 缩容
    return old;
}

测试：

public static void main(String[] args) {
    ArrayList2<Integer> list = new ArrayList2<>();
    for (int i = 0; i < 50; i++) {
        list.add(i);
    }
    for (int i = 0; i < 50; i++) {
        list.remove(0);
    }
    System.out.println(list);
}

清空数组时也可以进行缩容：

public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
    // 缩容
    if (elements != null && elements.length > DEFAULT_CAPACITY){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
}

2.11 复杂度震荡

如果扩容倍数、缩容实际设计不得当，可能会造成复杂度震荡的问题。

问题示例

比如，数组默认容量为 4，扩容倍数为 2 倍，缩容倍数为 1/2。当我们添加 1-4 个元素时，时间复杂度都是 O(1)，如果还要添加第五个元素时，就会进行扩容，容量变为 8，添加第五个元素的时间复杂度为 O(n)；这个时候又删除第五个元素，数组长度是容量的一半，就会进行缩容，删除第五个元素的时间复杂度为 O(n)。如此反复进行，最开始时间复杂度都是 O(1)，突然时间复杂度变为 O(n)，这就是复杂度震荡。

避免方式

如果 扩容倍数 * 缩容倍数 = 1，就会发生复杂度震荡，因此在设计时避免这种情况就可以了。

比如扩容倍数是 1.5 倍，缩容倍数是 2 倍。

2.12 完整代码

ArrayList.java（不包含缩容操作）：

/**
 * @author 默烦
 * @date 2020/6/17
 */
// 动态数组
/*使用范型后，会出现内存管理问题*/
public class ArrayList<E> {
    // 元素的数量 值大于0
    private int size;
    // 所有的元素 存放的地址 而非元素本身1
    private E[] elements;

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    // capacity 动态数组容量
    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        // Java 中所有的类都继承至 java.lang.Object
        // 注意是：Object ， 不是Objects
        elements = (E[]) new Object[capacity];
    }

    public ArrayList() {
//        elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    // 清除所有元素
    /*坚持一个思想：
    *   能够循环利用的空间留下
    *   不能循环利用的空间销毁
    * */
    public void clear() {
        // 使用范型后
        // 将数组中指向的内存空间进行销毁
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        // 表面情况，实际只是 size = 0
        size = 0;
    }

    // 元素的数量
    public int size() {
        return size;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    // 添加元素到尾部
    public void add(E element) {
        // size 值为多少，就往数组下标为 size 的位置添加元素
//        elements[size++] = element;
        add(size,element);
    }

    // 获取 index 位置的元素
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    // 设置 index 位置的元素
    public E set(int index, E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    // 向 index 位置添加一个元素 且默认支持插入空数据 null
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    // 删除 index 位置的元素
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        /*size--;
        elements[size] = null;*/
        // 合并为
        elements[--size] = null;
        return old;
    }

    // 可以根据传递的元素进行删除
   /* public void remove(E element){
        remove(indexOf(element));
    }*/

    // 查看元素的索引
    public int indexOf(E element){
        // 处理空值
        if (element == null){
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        }else {
            for (int i = 0; i < size; i++) {
                /*if (elements[i] == element) return i;*/
                /* 使用这种方式可以自定义比较方式
                 *  使用这种方式时，实体类需要重写equals()方法才可以自定义
                 * */
                // 注意：是element调用的equals()方法，因为这个时候element一定不为空
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // 保证要有 capacity 的容量(不考虑线程安全)
    private void ensureCapacity(int capacity){
        // 当前 elements.length 为 10，因为默认容量为 10
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // 新容量为新容量的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity+"扩容为"+newCapacity);
    }

    // 越界异常封装
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // 普通范围检查
    private void rangeCheck(int index){
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    // 添加元素的范围检查
    // 允许 index = size，当 index 等于 size 时，相当于在数组末尾添加元素
    private void rangeCheckForAdd(int index){
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    @Override
    public String toString() {
        // 打印效果 size = 3, [99,88,77]
        StringBuilder builder = new StringBuilder();
        builder.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0){
                builder.append(", ");
            }
            builder.append(elements[i]);
           /* if (i != size - 1){
                builder.append(", ");
            }*/
        }
        builder.append("]");
        return builder.toString();
    }
}

Student.java：

/**
 * @author 默烦
 * @date 2020/6/18
 */
public class Student {
    private int age;
    private String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("Student - finalize");
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (obj instanceof Student){
            Student stu = (Student) obj;
            return this.age == stu.age;
        }
        return false;
    }
}

Main.java：

/**
 * @author 默烦
 * @date 2020/6/17
 */
public class Main {
    public static void main(String[] args) {
        ArrayList<Student> list = new ArrayList<>();
        list.add(new Student(10,"Tom"));
        list.add(null);
        list.add(new Student(12, "Jerry"));
        list.add(null);
        System.out.println(list.indexOf(null));
        list.clear();
        System.gc();
        /*如果我们想在动态数组中使用多个类型
        * 可以：使用ArrayList<Object> list = new ArrayList<>();
        * */
    }
}