2020-09-05 08:52 已编辑门头沟学院 Java

关注

线性数据结构

基础知识

算法

在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题

数据结构

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据

时间复杂度

O(1)，O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)

空间复杂度

例子：查找一个整数序列中重复的数
- 双重循环：每遍历一个数就回顾之前遍历的所有整数，判断有没有重复的，O(n^2)
- 利用散列表：每遍历一个数就把该数放到散列表中，"key"代表整数值，"value"代表出现的次数，没遍历一个整数，value值加一。O(n)
常量空间，线性空间，二维空间，递归空间
递归空间：计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。
- “方法调用栈”包括进栈和出栈两个行为
- 进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中
- 方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出
- 执行递归操作所需要的内存空间和递归的深度n成正比

数组

有限个相同类型的变量所组成的有序集合

数组的基本操作

读取元素：使用数组下标随机读取
更新元素：使用数组下标直接赋值
插入元素：尾部插入，中间插入，超范围常插入，数组向后挪动，空间不够需要扩容
删除元素：数组向前挪动

数组优缺点

数组拥有非常高效的随机访问能力
插入、删除元素都会导致大量元素被迫移动，影响效率
数组所适合的是读操作多、写操作少的场景

链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

链表的基本操作

查找节点:：从头指针根据next依次遍历查找，时间复杂度未O(n)
更新节点：找到对应的节点后直接更新数据
插入节点：
- 尾部插入：把最后一个节点的next指针指向新节点
- 头部插入：把新节点的next指向原先的头节点，把新节点变为头节点
- 中间插入：把新节点的next指向要插入位置的节点，把插入位置的前一个节点的next指向新节点
删除元素：
- 尾部删除：把倒数第二个节点的next指向空
- 头部删除：把头节点设为原先头节点的next
- 中间删除：把要删除节点的前置节点指向要删除节点的后一个节点。

package linkedlist;

public class LinkedList {
    private Node head = new Node(0);
    private Node last = new Node(0);
    private int size = 0;
    
    /** * 插入节点 * @param data * @param index */
    public void insert(int data, int index) throws Exception{
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        Node insertedNode = new Node(data);
        Node preNode = get(index - 1);
        insertedNode.next = preNode.next;
        preNode.next = insertedNode;
        size++;
        if(index == size) {
            last = insertedNode;
        }
    }
    
    /** * 删除节点 * @param index * @return */
    public Node remove(int index) {
        if(index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        Node preNode = get(index-1);
        Node removeNode = preNode.next;
        preNode.next = removeNode.next;
        size--;
        if(index == (size-1)) {
            last = preNode;
        }
        return removeNode;
    }
    
    /** * 输出链表 */
    public void outPut() {
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
    
    /** * 获取节点 * @param index * @return */
    public Node get(int index) {
        if(index == -1) {
            return head;
        }
        if(index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("数组越界");
        }
        Node temp = head;
        for(int i = 0;i <= index;i++) {
            temp = temp.next;
        }
        return temp;
    }

    /** * 节点类 */
    private static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public static void main(String[] args) throws Exception {
        LinkedList myLinkedList = new LinkedList();
        myLinkedList.insert(3, 0);
        myLinkedList.insert(7, 1);
        myLinkedList.insert(9, 2);
        myLinkedList.insert(5, 3);
        myLinkedList.insert(6, 1);
        myLinkedList.outPut();
    }

}

链表VS数组

栈和队列

物理结构和逻辑结构

栈

栈（stack）是一种线性数据结构，栈中的元素只能先入后出，最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）

栈的基本操作

入栈：把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
出栈：把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
入栈、出栈的时间复杂度都是O(1)。

队列

队列（queue）是一种线性数据结构，队列中的元素只能先入先出，队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）

队列的数组实现
队列的链表实现

队列的基本操作

入队：把新元素放入队列中，只允许在队尾的位置放入元素
出队：把元素移出队列，只允许在队头一侧移出元素
队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1

循环队列

（队尾下标+1）%数组长度 = 队头下标时，代表此队列真的已经满了
入队：rear = (rear+1)%length
出队：front = (front+1)%length

代码示例

package linkedlist;

public class Queue {
    private int[] array;
    private int front;
    private int rear;

    /** * 构造函数 * @param capacity */
    public Queue(int capacity) {
        this.array = new int[capacity];
    }

    /** * 入队 * @param element * @throws Exception */
    public void enQueue(int element) throws Exception {
        //队列满
        if((rear + 1)%array.length == front) {
            throw new Exception("队列已满！");
        }
        array[rear] = element;
        rear = (rear + 1)%array.length;
    }

    /** * 出队 * @return * @throws Exception */
    public int deQueue() throws Exception {
        if(rear == front) {
            throw new Exception("队列空！");
        }
        int deElement = array[front];
        front = (front + 1)%array.length;
        return deElement;
    }

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

    /** * 测试 * @param args * @throws Exception */
    public static void main(String[] args) throws Exception {
        Queue myQueue = new Queue(6);
        myQueue.enQueue(3);
        myQueue.enQueue(5);
        myQueue.enQueue(6);
        myQueue.enQueue(8);
        myQueue.enQueue(1);
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.enQueue(9);
        myQueue.output();
    }
}

栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。
栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。

队列的应用

队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。
在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。
双端队列：把栈和队列的特点结合起来，既可以先入先出，也可以先入后出。从队头一端可以入队或出队，从队尾一端也可以入队或出队。

哈希表

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

哈希函数

数组只能根据下标，像a[0]、a[1]、a[2]、a[3]、a[4]这样来访问，而哈希表的Key则是以字符串类型为主的。
我们需要一个“中转站”，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数。

Java中的HashMap

在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hashcode都是一个整型变量。

最简单的转化方式是按照数组长度进行取模运算：
- index = HashCode (Key) % Array.length
JDK中的哈希函数并没有直接采用取模运算，而是利用了位运算的方式来优化性能。
通过哈希函数，我们可以把字符串或其他类型的Key，转化成数组的下标index。

哈希表的读写操作

写操作：hashMap.put(“002931”, “哈哈”)，通过哈希函数将key转换为index
哈希冲突：当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。
解决哈希冲突的方法：
- 开放寻址法：当一个key通过哈希函数获得的数组下标被占用时，按某种策略寻找一个新的下标。(在Java中，ThreadLocal所使用的就是开放寻址法)
- 链表法(HashMap采用这种方法)：HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
读操作：读操作就是通过给定的Key，在散列表中查找对应的Value，以链表法为例，调用hashMap.get(“002936”)：
- 第1步，通过哈希函数，把Key转化成数组下标2。
- 第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果不是，顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。

哈希表的扩容

对于JDK中的散列表实现类HashMap来说，影响其扩容的因素有两个。
- Capacity：即HashMap的当前长度
- LoadFactor：即HashMap的负载因子，默认值为0.75f
衡量HashMap需要进行扩容的条件：HashMap.Size >= Capacity×LoadFactor
扩容操作：
1. 扩容，创建一个新的Entry空数组，长度是原数组的2倍。
2. 重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

小结

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