常见数据结构

数组、链表、堆栈、队列、哈希表、树

1. 数组

结构：

• Array 是在内存中开辟的一块连续的空间
• 数组初始化时长度固定
• 有索引，从0开始，查询元素比较快

时间复杂度：

假如数组的长度为 n。
访问：O（1）//访问特定位置的元素
插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

优点：

• 查询快：数组的地址是连续的，我们可以通过首地址快速找到数组，通过索引快速查找某一个元素
• 支持随机访问

缺点：

• 增/删慢，因为要移动其他的元素（我们要增加/删除一个元素，必须创建一个新的数组，把原数组的数据复制过来）
• 数组的大小创建后就确定了，无法扩容
• 数组只能存储一种类型的数据

2. 链表

链表介绍：

​ 链表是物理存储单元上非连续的（不连续的内存空间）、非顺序的存储结构。链表可以充分利用计算机内存空间，实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针，每个节点包含两个部分：

• 一个是存储元素的数据区域
• 一个是存储下一个节点地址的指针域

时间复杂度：

在链表头或链表尾添加、删除节点：O（1）
在链表中间添加、删除节点：O（n）
链表中查找节点 O（n）

优点：

• 增删快，只需要改变前后两个元素节点指针指域指向的向地址即可，可以达到 O(1) 的时间复杂度（只需要重新指向引用即可，不需要像数组那样移动其他元素）

• 不需要初始化时固定链表大小，可以添加任意元素。可以实现灵活的内存动态管理

缺点：

• 查询慢，查找元素需要遍历链表，时间杂度为 O(n)
• 含有大量的引用，占用的内存空间大
• 链表不具有数组那样随机读取的优点

常见链表分类：

1. 单链表：单向，每个节点只有一个指针next指向后面的节点，结尾通常指向null
2. 双向链表：包含两个指针，prev指向前一节点，next指向后一节点
3. 循环链表：特殊的单链表，尾结点指向头节点
4. 循环双向链表：特殊的双向链表，头结点prev指向尾节点的prev，尾结点的next指向头结点的next

数组VS链表:

• 存储数据的个数不确定，且需要经常添加或删除数据的话，使用链表比较合适
• 存储数据的个数确定，不需要经常添加或删除数据，使用数组比较合适
• 数组支持随机访问而链表不支持
• 数组使用连续的内存空间对CPU缓存机制比较友好，链表则相反
• 数组的大小固定，而链表支持动态扩容，如果数组声明的空间不够，则需要重新申请一块更大的内存空间存放数组元素，将原数组拷贝进去

3. 栈(stack)

栈简介

​ 栈（stack）又称堆栈，只允许在有序的线性数据集合一端（成为栈顶top）进行加入数据（push）和移除数据（pop），先进的后出，栈常用一维数组或链表来实现。

特点：

• 先进后出（类似手抢弹夹）
• 栈的入口、出口都在栈的顶端位置
• 访问：O（n）最坏情况
• 插入删除：O（1）顶端插入和删除元素

栈常见应用场景

当我们要处理的数据符合 “后进的先出” 特性时，我们就使用栈这个数据结构。

• 浏览器前进或回退功能：

  • 只需要两个栈（Stack1 和 Stack2），比如查看顺序为1、2、3、4，我们将 1-2-3-4 顺序压入Stack1，当想回头看2这个页面的时候，点两次回退按钮，将Stack1中的4、3弹出，压入Stack2中，假如你又想看3这个页面，只需要将Stack2中的3弹出，重新压入Stack1中即可

• 检查符号是否成对出现

  给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断该字符串是否有效，比如 “()”、“()[]{}”、“{[]}” 都是有效字符串，而 “(]” 、“([)]” 则不是。

  有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

  1. 首先将括号对应规则放入 Map 中。

  2. 创建一个栈，遍历字符串，如果字符是左括号就直接加入 Stack 中，否则（是右括号）将 Stack 的栈顶元素取出与这个括号做比较，如果不相等则返回 false。遍历结束，如果 Stack 为空，返回 true

  3. 比较时，遍历符号数组，遇到左括号添加到队列中，遇到右括号则从队列进行弹栈拿到顶端符号，与字典中对应的符号比较

  4. 正确示例：“{ [ < > ] }”

     • 入栈顺序(左括号)：

       • 3:<

       • 2:[

       • 1:{

     • 出栈顺序(左括号):

       • 1: <
       • 2:[
       • 3:{

     所以对应字典中的key必须是：> ] }

     代码实现：

     public boolean isValid(String s){
         // 括号之间的对应规则 例如：“{ [ < > ] }”  栈：先入后出特性 
         HashMap<Character, Character> mappings = new HashMap<Character, Character>();
         mappings.put(')', '(');
         mappings.put('}', '{');
         mappings.put(']', '[');
         Stack<Character> stack = new Stack<Character>();
         char[] chars = s.toCharArray();
         for (int i = 0; i < chars.length; i++) {
             if (mappings.containsKey(chars[i])) {
                 char topElement = stack.empty() ? '#' : stack.pop();
                 if (topElement != mappings.get(chars[i])) {
                     return false;
                 }
             } else {
                 //如果是左括号则加入栈
                 stack.push(chars[i]);
             }
         }
         return stack.isEmpty();
     

• 反转字符串：

  将字符串的每个字符先入栈后出栈即可

• 维护函数使用：

  最后一个被执行的函数，第一个压入栈

java中栈的实现

1. java中Stack只有一个无参构造函数。

2. 属于stack自己的方法包括（stack API）

   - push( num) //入栈
   - pop() //获取栈顶元素，元素出栈
   - empty() //判定栈是否为空
   - peek() //获取栈顶元素，元素不出栈
   - search(num) //判端元素num是否在栈中，如果在返回1，不在返回-1
   

3. 也可以使用数组或者链表实现，不管基于链表还是数组，入栈出栈时间复杂度都应该是O(1)

下面我们使用 数组 来实现一个栈，并且这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。

public class MyStack {
    private int[] storage;//存放栈中元素的数组
    private int capacity;//栈的容量
    private int count;//栈中元素数量
    private static final int GROW_FACTOR = 2;

    //不带初始容量的构造方法。默认容量为8
    public MyStack() {
        this.capacity = 8;
        this.storage=new int[8];
        this.count = 0;
    }

    //带初始容量的构造方法
    public MyStack(int initialCapacity) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException("Capacity too small.");

        this.capacity = initialCapacity;
        this.storage = new int[initialCapacity];
        this.count = 0;
    }

    //入栈
    public void push(int value) {
        if (count == capacity) {
            ensureCapacity();
        }
        storage[count++] = value;
    }

    //确保容量大小
    private void ensureCapacity() {
        int newCapacity = capacity * GROW_FACTOR;
        storage = Arrays.copyOf(storage, newCapacity);
        capacity = newCapacity;
    }

    //返回栈顶元素并出栈
    private int pop() {
        if (count == 0)
            throw new IllegalArgumentException("Stack is empty.");
        count--;
        return storage[count];
    }

    //返回栈顶元素不出栈
    private int peek() {
        if (count == 0){
            throw new IllegalArgumentException("Stack is empty.");
        }else {
            return storage[count-1];
        }
    }

    //判断栈是否为空
    private boolean isEmpty() {
        return count == 0;
    }

    //返回栈中元素的个数
    private int size() {
        return count;
    }
}

4. 队列

4.1 队列简介

• 队列：queue简称队列，类似水管，只能在一端进行插入，另一端进行删除
• 优先队列：出的时候优先级高的先出
  • 堆（二叉堆）：与树结构相反
  • 二叉搜索树

特点：

• 先进先出
• 队列入口、出口各占一侧

队列分类：

• 单队列 是常见的队列，每次添加元素时都添加到队尾，单队列又分为：

  • 1.顺序队列（数组实现）：存在“假溢出”的现象
  • 2.链式队列（链表实现）

• 循环队列

假溢出现象：

# 单队列：将前面两个元素 1、2出队，并入队两个元素 5、6，rear 和 front 指针都会移动，当添加元素 7 的时候，rear 指针移动到数组之外（越界）

+-----+-----+-----+-----+-----+-----+
|  头 |     |     |     | 尾  |     |    原队列
+----+----+----+----+----+----+-----+
|  1  |  2  |  3  |  4  |     |     | 
+----+----+----+----+----+----+-----+

# 1、2出队， 5、6入队,头尾指针也发生变化，当添加元素 7 的时候，尾指针移动到数组之外（越界），但其实还有空间，这就叫假溢出

+-----+-----+----+-----+-----+------+
|     |     |  头 |     |     |     |   尾        
+----+-------+--------+-------------+
|     |     |  3  |  4  |  5  |  6  |   ？
+----+-------+--------+--------------+



# 循环队列：将1、2元素出队后，添加5、6后再添加 7 元素，将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候， rear 向后移动。

+----+------+-----+-----+-----+-----+
|     |  尾 |  头  |     |     |     |    7入队
+----+-------+--------+--------------+
|  7  |     |  3  |  4  |  5  |  6  | 
+----+-------+--------+--------------+


+----+-----+-----+-----+-----+-----+
|    |     | 尾头 |     |     |     |      8入队
+----+-----+--------+---------------+
|  7  |  8 |  3  |  4  |  5  |  6  | 
+----+-------+--------+-------------

顺序队列中，front（头） == rear（尾） 时队列为空，循环队列则不一样，也可能为满。

1.可以设置一个标志变量 flag,当 front==rear 并且 flag=0 的时候队列为空，当front==rear 并且 flag=1 的时候队列为满。

2.队列为空的时候就是 front==rear ，队列满的时候，我们保证数组还有一个空闲的位置，rear 就指向这个空闲位置，那么现在判断队列是否为满的条件就是： (rear+1) % QueueSize= front。

4.2 队列应用场景

• 阻塞队列： 队列为空时，出队列操作阻塞。队列为满时，入队操作阻塞。常见的如 生产者-消费者 模型
• 线程池中的请求/任务队列： 当线程池没有空闲线程时，新的线程任务请求会被放在队列中，等待线程空闲的时候，循环遍历队列中的任务来执行。队列分为无界队列（基于链表）和有界队列（基于数组），无界队列的特点可以一直入队，直到系统资源耗尽，比如：FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列则不同，当队列满的时候在有任务/请求添加就会拒绝，在java中体现就是会抛出：java.util.concurrenent.RejectedExecutionException 异常
• 播放器列表
• 消息队列等

5. 哈希表

5.1 哈希表简介

哈希表：Hash Table 也叫散列表，是一种key-value的数据结构，它最大的特点是可以实现快速查找、插入和删除

哈希表结合了数组+链表的优点

• 在JDK1.8之前，哈希表底层采用 数组+链表 实现，即使用链表处理冲突，统一hash值的元素都存在一个链表里，但是当位于一个桶中的元素较多，即hash值相等的元素较多，通过key值依次查找的效率较低。
• 而JDK1.8中，哈希表存储采用了 数组+链表+红黑树 实现，当链表长度超过阈值（8）时，将链表转为红黑树，这样大大减少了查找时间。

5.2 HashSet 为什么不能存储重复元素？

/**
 * set集合存储元素不重复，前提：存储的元素必须重写hashCode方法和equest方法
 * set集合调用add方法的时候，add方法会调用元素的hashCode方法和equest方法判断元素是否重复
 * 
 * 1.哈希值相同放在同一链表下
 * 2.哈希值下相同在用qeuest比较元素是否相同，相同则不继续添加
 * 3.长度大于8之后由链表转为红黑树
 */
HashSet<String> set = new HashSet<String>();
Stirng s1 = new String("abc");
Stirng s2 = new String("abc");
set.add(s1);
set.add(s2);
set.add("重地");
set.add("通话");
set.add("abc");

6. 树(tree)

介绍： 树是一种典型的非线性结构，它是由n（n>0）个有限节点组成的一个有层次关系的集合

①、路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。

②、根节点：树顶端的节点称为根节点。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

③、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。

④、子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。

⑤、兄弟节点：具有相同父节点的节点互称为兄弟节点；比如上图的D和E。

⑥、叶子节点：没有子节点的节点称为叶节点，也叫叶子节点，比如上图的H、E、F、G都是叶子节点。

⑦、子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

⑧、节点的层次数：从根开始定义，根为第一层，根的子节点为第二层，以此类推。（节点的深度+1。）

⑨、节点的深度：该节点到根节点的长度，根的深度为0，根下面第一个节点深度从1开始；

⑩、节点的高度：对于任意节点n，从n到一片树叶的最长路径长；（说人话：就是节点到叶子节点最长的距离）

​ 树的高度：根节点的高度；

6.1 二叉树

树的每个节点最多只能有两个子节点（下面是几种常见的二叉树）

6.2 满二叉树

• 除最后一层的节点没有子节点外，其余每层的节点都有两个节点的二叉树

• 如果一个二叉树有k层，且总结点数为(2^k) -1 ，则他就是满二叉树

6.3 完全二叉树

除了最后一层，其余各层都是满的（最后一层也可以是满的），可以理解为扩展完左节点在扩展右侧节点，每扩展完一层，才能继续扩展下一层。

6.4 二叉搜索树

‘二叉搜索树’ 也叫 ’二叉查找树‘ 也叫 ’二叉排序树‘

🌵二叉查找树特点：

• 节点A，左节点值小于A，右节点值大于A；

• 若任意节点的左子树不空，左子树上所有节点的值均小于它的根节点的值；

• 若任意节点的右子树不空，右子树上所有节点的值均大于它的根节点的值；

• 任意节点的左、右子树也分别为二叉搜索树。

• 没有键值相等的节点。

• 对二叉查找树进行中序遍历，即可得到有序的数列

• 二叉查找树在极端情况下失去平衡，退化成线性的链表（如下图b所示）

🌵二叉搜索树 插入/删除/查找算法：

• 查找算法： 从根节点开始，比节点大进入右支，比节点小进入左支，直到查找到目标值。
• 插入算法： 空树就首先生成根节点；不是空树就按照查找的算法，找到父节点，然后作为叶子节点插入，如果值存在就插入失败。
• 删除算法：
  • 叶子节点直接删除
  • 被删节点只有一个子节点，可以将被删节点与自己点位置互换，然后删除子节点
  • 如果有两个子节点，这时采用中序遍历找到后继节点，然后与要删除节点位置互换后，可直接删除叶子节点（如下图所示）

6.5 二叉平衡树【AVL树】

• 平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN)

• 平衡二叉搜索树，又称AVL树，可以是一颗空树或者左右两颗子树的高度差的绝对值不能超过1，并且左右两个子树都是二叉平衡树。

6.5.1 二叉平衡树旋转

【左旋右旋】

在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是则需要做旋转去改变树的结构。

• 左旋： 将节点的右支往左拉，右子节点变父节点，晋升之后多余的左子节点给降级节点当右子节点
  

• 右旋： 将节点的左支往右拉，左子节点变父节点，晋升之后多余的右子节点给降级节点当左子节点
  

6.5.2 失衡的4种情况

以下是二叉平衡树失衡的4种情况以及如何处理的方法

• 左左： 节点A的左子树的左子树下有新的节点插入，导致与节点A右子数的高度差为2（解决方法：右旋）

• 右右： 节点A的右子树的右子树下有新的节点插入，导致与节点A左子树的高度差为2（解决方法：左旋）

• 左右： 节点A左子树的右子树下有新的节点插入，导致与节点A的右子树的高度差为2（解决方法：先左旋，在右旋）
  

• 右左： 节点A右子树的左子树上有新的节点插入，导致与节点A的左子树高度差为2（解决方法：先右旋，在左旋）
  

6.6 二叉树的存储和遍历

6.6.1 二叉树存储

• 链式存储
• 顺序存储

🌲链式存储

​ 和链表类似，二叉树的链式存储依靠指针将各个节点串联起来，不需要连续的存储空间。每个节点包括3个属性

• 数据 data（可以是不同类型）

• 左节点指针 left

• 右节点指针 right

  注：java不存在指针，这里的指针是对象引用

🌲顺序存储

​ 利用数组进行存储，每个节点值储存data，不存储左右节点指针，子节点的索引通过数组下标完成，根节点序号为1，假设根节点存储在下标为 i 的位置。那么左子节存储的下标就是 2i，右子节点存储的下标就是 2i+1

注意： 链式存储如果存储的不是完全二叉树，在数组中就会出现缝隙，导致内存利用率低。

6.6.2 二叉树遍历

1.先序遍历规则： 先输出根节点，在遍历左子树，最后遍历右子树（遍历子树的时候，同样遵循先序遍历规则）

代码如下：

public void preOrder(TreeNode root){
    if(root == null){
        return;
    }
    system.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

2.中序遍历规则： 先递归遍历左子树，在输出根，在递归遍历右子树（理解为一巴掌把树拍扁，父节点在左子节点和右字节点中间）

代码如下：

public void inOrder(TreeNode root){
    if(root == null){
        return;
    }
    inOrder(root.left);
    system.out.println(root.data);
    inOrder(root.right);
}

3.后续遍历规则： 先递归遍历左子树，在递归遍历右子树，最后输出根

)
代码如下：

public void postOrder(TreeNode root){
    if(root == null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    system.out.println(root.data);
}