1、常见数据结构参考（https://blog.csdn.net/yeyazhishang/article/details/82353846）

数据结构分类

2、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

int[] data = new int[100]；data[0]  = 1;

优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。

适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。

3、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

栈

栈常应用于实现递归功能方面的场景，例如斐波那契数列。

4、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队

队列

因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

5、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

链表

链表的优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

public class LinkedList {

    private Node head;      //头节点

    //新增节点,在尾部新增
    public void addHead(Node node) {
        //头节点是否存在
        if (head == null) {
            head = node;
            return;
        }
        Node currentNode = head;
        while (currentNode.next != null) {
            currentNode = currentNode.next;
        }
        currentNode.next = node;
    }

    //新增节点，在头部新增
    public void addTail(Node node) {
        node.next = head;
        head = node;
    }

    //删除下标为k的节点
    public boolean delete(int k) {
        if (k < 0 || k > length() - 1) {
            //todo 下标越界异常处理
            return false;
        }
        if (k == 0) {
            head = head.next;
            return true;
        }
        int j = 1;
        Node currentNode = head;
        Node nextNode = currentNode.next;
        while (j < k) {
            currentNode = currentNode.next;
            nextNode = nextNode.next;
            j++;
        }
        currentNode.next = nextNode.next;
        return true;
    }

    //查询下标为k的节点
    public Node query(int k) {
        if (k < 0 || k > length() - 1) {
            return null;
        }
        if (k == 0) {
            return head;
        }
        Node currentNode = head;
        int j = 0;
        while (currentNode.next != null) {
            currentNode = currentNode.next;
            j++;
            if (j == k) {
                return currentNode;
            }
        }
        return null;
    }

    //查询链表长度
    public int length() {
        if (head == null) {
            return 0;
        }
        int length = 1;
        Node currentNode = head;
        while (currentNode.next != null) {
            length++;
            currentNode = currentNode.next;
        }
        return length;
    }

    //遍历节点
    public void getAllNode() {
        if (head == null) {
            return;
        }
        Node currentNode = head;
        System.out.print(head.data + ", ");
        while (currentNode.next != null) {
            System.out.print(currentNode.next.data + ", ");
            currentNode = currentNode.next;
        }
    }

    //在下标为k的位置插入节点
    public boolean insert(int k, Node node) {
        if (k < 0 || k > length() - 1) {
            //todo 下标越界异常处理
            return false;
        }
        if (k == 0) {
            node.next = head;
            head = node;
            return true;
        }
        Node currentNode = head;
        int i = 1;
        while (i < k) {
            currentNode = currentNode.next;
            i++;
        }
        node.next = currentNode.next;
        currentNode.next = node;
        return true;
    }

    //排序节点
    public void sort() {
        if (head == null) {
            return;
        }
        Node currentNode = head;
        while (currentNode != null) {
            Node nextNode = currentNode.next;
            while (nextNode != null) {
                if (currentNode.data > nextNode.data) {
                    int temp = currentNode.data;
                    currentNode.data = nextNode.data;
                    nextNode.data = temp;
                }
                nextNode = nextNode.next;
            }
            currentNode = currentNode.next;
        }
    }

    //链表反转，遍历法  输入原链表头节点，返回反转后链表的头节点(即原链表的尾节点)
    public Node reversal(Node head) {
        if (head == null || head.next == null) return head;
        Node preNode = head;                //上个节点
        Node currentNode = head.next;       //当前节点
        Node temp;                          //临时节点，用于保存当前节点的下一个节点
        while (currentNode != null) {       //假如当前节点为null，说明此时位于尾节点
            temp = currentNode.next;
            currentNode.next = preNode;     //节点指向反转

            //节点向后移动
            preNode = currentNode;
            currentNode = temp;
        }
        head.next = null;
        return preNode;
    }

    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
        Node node5 = new Node(50);
        Node node6 = new Node(60);
        ll.addHead(node1);
        ll.addHead(node2);
        ll.addHead(node5);
        ll.addHead(node3);
        ll.addHead(node6);
        ll.addHead(node4);

        System.out.print("排序前：");
        ll.getAllNode();
        ll.sort();
        System.out.print("\n排序后：");
        ll.getAllNode();

        System.out.println("\n链表长度=" + ll.length());
        ll.delete(2);
        System.out.print("\n删除下标为2的节点：");
        ll.getAllNode();
        System.out.println("\n删除后长度=" + ll.length());

        System.out.println("\n下标为0的节点=" + ll.query(0).data);

        Node reversal = ll.reversal(node1);
        //遍历反转后的链表
        System.out.print("\n 反转后的链表：" +reversal.data + ", ");
        while (reversal.next != null) {
            reversal = reversal.next;
            System.out.print(reversal.data + ", ");
        }

    }

}

6、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

6.2 树的分类：

image.png

• 平衡二叉树
  它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
  
  image.png
  
  二叉树遍历：
  a. 前序遍历，根左右
  b. 中序遍历，左根右
  c. 后序遍历，左右根
  
  
  前序：abdefgc
  中序：debgfac
  后序：edgfbca

   //前序遍历
    public void preOrderTraverse(DataNode node){
        if (node==null) {
            return;
        }
        System.out.print(node.data);
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }
    //中序遍历
    public void inOrderTraverse(DataNode node){
        if (node==null) {
            return;
        }
        inOrderTraverse(node.leftChild);
        System.out.print(node.data);
        inOrderTraverse(node.rightChild);
    }
        //后序遍历
    public void postOrderTraverse(DataNode node){
        if (node==null) {
            return;
        }
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.print(node.data);
    }

• 二叉搜索树
  若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值，若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值。对它进行中序遍历得到的是有序的数组。
  

  image.png

• 红黑树 参考
  自平衡的二叉查找树，红黑树也属于平衡二叉树。
  性质1：每个节点要么是黑色，要么是红色。
  性质2：根节点是黑色。
  性质3：每个叶子节点（NIL）是黑色。
  性质4：每个红色结点的两个子结点一定都是黑色。
  性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
  一棵n个结点的红黑树始终保持了logn的高度，所以红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
  

  image.png
  
  
  左旋
  
  
  右旋

• B树 参考
  B树属于多叉树又名平衡多路查找树
  每个节点都存储Key和data，所有的节点组成这棵树，并且叶子节点指针为null。
  

  image.png

一个m阶的B树具有如下几个特征：

1. 根结点至少有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4. 所有的叶子结点都位于同一层。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

• B+树 参考

只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针，后来加上了顺序访问指针。

image.png

一个m阶的B+树具有如下几个特征：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B树和B+树的区别：
B树中关键字分布在整个树中，叶节点不包含任何关键信息，B+树的关键信息在叶子节点中，非叶子节点只存储索引；B树的关键字只存在一个节点中，B+树的关键字必须在叶子节点，非叶子节点可能存在。

7、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

记录的存储位置=f(key)

这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

8、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

  
  
  image.png
  
  

  一般升序采用大顶堆，降序采用小顶堆。

9、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
图在代码里主要通过邻接列表和邻接矩阵来实现。

邻接列表

邻接矩阵

• 深度优先算法DFS
  沿着图的深度遍历图的节点，尽可能深的搜索图的分支。 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。 这一过程一直进行到已发现从源节点可达的所有节点为止。
  步骤：

1. 从最开始的节点A开始，获取与它相邻的节点B
2. 判断这个节点是否被访问过，如果访问过，那么就不再重复访问，如果没有则进行下一步
3. 已当前的节点B为当前节点，进行深度优先搜索算法
   3.1. 将当前节点的访问状态设为已访问
   3.2. 获取当前节点的下一个相邻节点C
   3.3. 判断相邻节点C是否是终止节点，如果是终止节点，那么算法结束
   3.4. 判断当前节点是否被访问过，如果没有被访问过，那么重复将访问状态设为已访问，如果访问过了，
   那么获取下一个相邻节点，然后重复3.1至3.4

• 广度优先算法BFS
  从根节点开始，沿着图的宽度遍历图的节点。
  步骤：

1. 从最开始的节点A开始，获取与它相邻的所有节点B，C等，如果元素没有被访问过就加入队列
2. 从队列获取之前加入的元素B作为当前元素，获取与它相邻的元素D，E等，如果元素是终点就结束，如果元素没有被访问过就加入队列
3. 重复步骤2直到找到终点