算法之美-[数据结构基础]

1. 算法概述

• 什么是算法$(algorithm)$？
  • 在计算机领域里，算法就是一系列程序指令，用于处理特定的运算和逻辑问题。衡量算法优劣的主要标准是时间复杂度和空间复杂度。

• 什么是数据结构$(data \ structure)$？

  • 数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
  • 数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。

• 什么是时间复杂度？

  • 时间复杂度是对一个算法运行时间长短的量度，用大O表示法，记作$T(n)=O(f(n))$。
  • 常见的时间复杂度按照从低到高的顺序，包括$O(1),O(logn),O(n),O(nlogn),O(n^2)$等。
• 什么是空间复杂度？
  • 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，用大O表示法，记作$S(n)=O(f(n))$。
  • 常见的空间复杂度按照从低到高的顺序，包括$O(1),O(N),O(n^2)$等。其中递归算法的空间复杂度和递归深度成正比。

2. 数据结构基础

2.1 数组和链表

2.1.1 数组

数组是有限个相同类型的变量所组成的有序集合，每个数组中的变量被称为元素。数组在内存中是顺序存储的，因此可以很好的实现逻辑上的顺序表。

• 数组读取元素和更新元素的时间复杂度都是$O(1)$。

插入数组元素存在3种情况：

• 尾插入：直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。复杂度$O(1)$。
• 中间插入：由于数组中的每个元素都是其固定的下表，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再将要插入的元素放到对应的数组位置上。$O(n)$。
• 超范围插入：会涉及到数组的扩容，可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素全部过去，就实现数组的扩容了。$O(n)$。

数组删除元素操作和插入操作相反，如果是中间删除，那么其后的元素都要前移。

2.1.2 数组小结

数组的插入操作，数组扩容的时间复杂度是$O(n)$，插入并移动元素的时间复杂度也是$O(n)$，综合起来插入操作的时间复杂度为$O(n)$。删除操作只涉及到元素的移动，复杂度也是$O(n)$。

• 数组的优势

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫二分查找法，就是利用了数组的这个优势。

• 数组的劣势

数组的劣势体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

数组适合的是读操作多、写操作少的场景。

2.1.3 链表

链表是一种在物理上非连续、非顺序的数据结构，由若干节点(node)所组成。单向链表的每个节点细分为两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。

private static class Node{
    int data;
    Node next;
}

链表的第一个节点被称为头节点，最后一个节点被称为尾节点，尾节点的next指针指向null。

2.1.4 双向链表

双向链表比单向链表稍微复杂一下，它每个节点除了拥有data和next指针，还有指向前置节点的prev指针。

链表在内存中的存储方式是随机存储，链表采用了见缝插针的存储方式，每个节点分布在内存的不同位置，依靠next指针关联起来，这样可以灵活有效地利用零散的碎片空间。

• 链表中的数据只能按顺序逐级查找，最坏的时间复杂度是$O(n)$。
• 链表的插入和删除操作，复杂度是$O(1)$。

2.1.5 数组和链表小结

数组和链表相关操作的性能对比

	查找	更新	插入	删除
数组	$O(1)$	$O(1)$	$O(n)$	$O(n)$
链表	$O(n)$	$O(1)$	$O(1)$	$O(1)$

数组的优势在于能快速定位元素，对于读操作多、写操作少的场景非常适合。相反，链表优势在于能够灵活地进行插入和删除操作，如果需在尾部频繁插入、删除元素，用链表更合适。

2.2 栈和队列

2.2.1 物理结构和逻辑结构

• 物理结构

如果把数据结构比作人类，那么物理结构就是人的血肉和骨骼，看得见摸得着实实在在的。例如数组和链表都是内存中实实在在的存储结构。

• 逻辑结构

在物质的人体之上，还存在着人的思想和精神，它们看不见、摸不着。提供把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是数据存储的逻辑结构。逻辑结构是抽象的概念，它依赖于物理结构而存在。

2.2.2 栈

栈是一种线性数据结构，栈中的元素只能先入后出(First In Last Out,简称FILO)。最早进入的元素存放位置叫栈底(bottom)，最后进入的元素存放位置叫栈顶(top)。栈这种数据结构既可以用数组实现，也可以用链表。

• 入栈

入栈操作(push)就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将成为新栈顶。

• 出栈

出栈操作(pop)就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

• 代码实现如下

/**
 * @Author: zero
 * @Description: 使用数组实现栈的基本操作
 * Date: Create in 2020/3/21 8:40
 * Modified By:
 */

public class MyStack {
    private int[] array;
    private int top;

    public MyStack(int capacity){
        this.array = new int[capacity];
    }

    /**
     * 压栈
     * @param element 入栈元素
     * @throws Exception
     */
    public void push(int element) throws Exception {
        if (top > array.length){
            throw new Exception("StackOverflowError");
        }
        array[top++] = element;
    }

    /**
     * 弹栈
     * @throws Exception
     */
    public void pop() throws Exception {
        if (top == 0){
            throw new Exception("No ElementError");
        }
        delete(top - 1, array);
        top--;
    }

    /**
     * 栈元素的删除操作
     * @param index 出栈元素索引
     * @param array 操作数组
     */
    public void delete(int index, int[] array) {
        // 新建一个数组为原数组-1
        int[] arrNew = new int[array.length - 1];
        // 打印出栈元素
        System.out.println(array[index]);
        // 数组元素转移，也可以直接调用api
        // for (int i = 0; i < array.length - 1; i++) {
        //     arrNew[i] = array[i];
        // }
        // 调用api实现数组元素转移
        System.arraycopy(array, 0, arrNew, 0, arrNew.length);
        this.array = arrNew;
    }

    public void show(){
        System.out.println(Arrays.toString(this.array));
    }

    public static void main(String[] args) throws Exception {
        MyStack myStack = new MyStack(8);
        System.out.println("压栈");
        for (int i = 1; i <= 8; i++) {
            myStack.push(i);
        }
        myStack.show();
        for (int i = 0; i <= 7; i++) {
            System.out.print("弹栈");
            myStack.pop();
        }
        myStack.show();
    }
}

• 出栈入栈只会影响最后一个元素，因此时间复杂度都是${O(1)}$。

2.2.3 队列

队列(queue)是一种线性数据结构，它跟单向隧道类似，队列中的元素只能先入先出(First In First Out，简称FIFO)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。

• 入队

入队(enqueue)就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

• 出队

出队(dequeue)操作就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

• 循环队列

如果按照上面的方式不断出队，队头指针右移，队头左边的空间就失去作用了，故用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。

• 什么是循环队列

你可以把它理解为一个首尾相连的圆环，其中有两个指针：队头指针和队尾指针。这两个指针始终按照同一个方向前进，两个指针互相追赶着对方；入队操作时队尾指针（队尾指针会占据一个空闲空间）一直前进，直到遇到队头指针便代表空间用完了，停止入队；出队操作就是标记释放空间（数组内实际没有删除元素），队头指针一直前进，直到遇到队尾指针便代表空间释放完了，停止出队。下面就是循环队列的简单示意图：

• 循环队列如何实现

那么如何做到队头队尾指针能持续前进的同时不超过数组大小呢？我们可以用到取余%操作符，当队头或队尾值达到数组最大值时，重新归零，当队头队尾值相同时不做添加删除操作，以实现数组的循环。

• 实现过程

  • 入队操作：队尾下标 = (队尾下标+1)%数组长度
  • 出队操作：队头下标 = (队头下标+1)%数组长度
  • 队列空间满的条件：(队尾下标+1)%数组长度==队头下标

• 代码实现

/**
 * @Author: zero
 * @Description: 使用数组实现循环队列
 * Date: Create in 2020/3/23 10:20
 * Modified By:
 */

public class MyQueue {
    private int[] array;
    // 队头
    private int front;
    // 队尾
    private int rear;

    public MyQueue(int capacity){
        // 因为队尾始终要占一个空间，故这里把空间补上
        this.array = new int[capacity + 1];
    }

    /**
     * 入队操作
     * @param element 入队的元素
     */
    public void enQueue(int element) throws Exception{
        if ((rear + 1) % array.length == front){
            throw new Exception("The Queue is Full!");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }

    /**
     * 出队操作
     * @return
     * @throws Exception
     */
    public int deQueue() throws Exception{
        if (rear == front){
            throw new Exception("The Queue is Empty!");
        }
        int deQueueElement = array[front];
        front = (front + 1) % array.length;
        return deQueueElement;
    }

    /**
     * 输出队列
     */
    public void output(){
        for (int i = front; i!=rear ; i=(i+1)%array.length) {
            System.out.println(array[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        MyQueue myQueue = new MyQueue(6);
        myQueue.enQueue(3);
        myQueue.enQueue(5);
        myQueue.enQueue(2);
        myQueue.enQueue(7);
        myQueue.enQueue(4);
        System.out.println("输出一下");
        myQueue.output();
        myQueue.deQueue();
        myQueue.deQueue();
        System.out.println("输出二下");
        myQueue.output();
        myQueue.enQueue(8);
        myQueue.enQueue(6);
        myQueue.enQueue(1);
        System.out.println("输出三下");
        myQueue.output();
    }
}

• 循环队列充分利用了数组的空间，也避免了数组元素的整体移动，入队和出队的时间复杂度都是${O(1)}$

2.3 栈和队列的应用

• 栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。例如实现递归操作，就可以用栈来代替，因为栈可以回溯方法的调用链。还有一个经典的应用场景就是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。

• 队列的应用

队列的输出顺序和输入顺序相同，所有队列通常用于对“历史”的回放，也就是按照顺序，把“历史”重演一遍。例如在多线程中争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序。网络爬虫实现网站抓取时，也是把待爬取的网站URL存入队列中，在按照存入的顺序依次抓取和解析的。

• 双端队列

双端队列(deque)这种数据结构，结合了栈和队列的优点，从队头一端可以入队或出队，从队尾一端也可以入队或出队。

• 优先队列

优先队列遵循谁优先级高谁先出队，元素被赋予优先级。当访问元素时，高优先级的优先被访问到。

2.4 散列表

散列表也叫做哈希表(hash table)，这种数据结构提供了键(key)和值(value)的映射关系。只要给出一个key，就可以高效查找到它所匹配的value，时间复杂度接近于${O(1)}$。

2.4.1 哈希函数

在Java及大多数面向对象的语言中，每个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标志。无论对象自身的类型是什么，它的hashcode都是一个整型变量。既然是整型变量那么转化为数组下标也不难实现，最简单的转化方式是按照数组长度进行取模运算。在Java中的哈希函数并没有直接采用取模运算，而是利用了位运算的方式来优化性能。

2.4.2 散列表的读写

2.4.2.1 写操作(put)

写操作就是在散列表中插入新的键值对(JDK中叫Entry)。例如调用hashMap.put("002931","王五")，就是插入一组key为002931、value为王五的键值对。具体操作如下：

1. 通过哈希函数，计算key的哈希值，然后通过取模运算转化为数组的下标5。
2. 如果数组下标5对应的位置没有元素，就把Entry填充到数组下标5的位置。

由于数组的长度是有限的，当插入的Entry越来越多时，不同的key通过哈希函数获得的下标可能是相同的。这种情况，就叫作哈希冲突。

解决哈希冲突主要有两种方式，开放寻址法和链表法。

• 开放寻址法就是当计算出的数组下标相同时，以该冲突下标经过一定算法重新计算一个下标，再尝试放入元素，如果还冲突就如上操作继续计算，直到不冲突为止。
• 链表法就是在发生冲突时将具有相同哈希值的元素放到同一个单链表中。

Java集合类HashMap就是使用链表法解决哈希冲突的，HashMap数组的每个元素不仅是一个Entry对象，还是链表的头节点。当新的Entry映射到冲突的数组位置时，只要插入到对应的链表中即可。

2.4.2.2 读操作(get)

读操作就是通过给定key，在散列表中查找对应的value。具体操作如下：

1. 通过哈希函数，把key转换为数组下标5。
2. 找到数组下标5对应的元素，如果这个元素的key为002936，那么就找到了；如果不是，就遍历该位置的链表，看能否找到与key相匹配的元素。

2.4.2.3 扩容(resize)

当经过多次元素插入后，散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高。如此就会形成大量元素拥挤在相同的数组下标位置，形成很长的链表，对插入和查询操作的性能都有很大影响。

此时，散列表就需要进行扩容操作。对于HashMap来说，影响扩容的因素有两个：

• Capacity，即HashMap当前的长度
• LoadFactor，即HashMap的负载因子，默认值为0.75f。
• threshold，经上述两个值计算出的临界值。

扩容操作步骤：

1. 扩容，创建一个新的Entry空数组，长度是原数组的两倍。
2. 重新Hash，遍历原Entry数组，把所有的Entry重新hash到新数组中。

2.5. 小结

• 什么是数组：数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是${O(1)}$，中间插入、删除数组元素的时间复杂度是${O(n)}$。
• 什么是链表：链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是${O(n)}$，中间插入、删除节点的时间复杂度是${O(1)}$。
• 什么是栈：栈是一种线性逻辑结构，可以用数组实现也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则(FILO)。
• 什么是队列：队列也是一种线性逻辑结构，可以用数组和链表实现。队列包含入队和出队操作，遵循先入先出原则(FIFO)。
• 什么是散列表：散列表也叫哈希表，是存储Key-Value映射的集合。对于某个Key，散列表可以在接近${O(1)}$的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。