数据结构思维导图模板_ProcessOn思维导图、流程图

1、数组Array

定义：在 连续的 内存空间中，存储一组 相同类型 的元素

方法： 1. 访问 O(1) 2. 搜索 O(N) 3. 插入 O(N) 需要将后面的所有元素都后移一位；如果后面没有额外空间了，则需要在内存中查找一整块更大的空间，然后将所有元素移过去。 4. 删除 O(N) :  同插入原理

特点： 适合读，不适合写： 读多写少！！

常用操作： 1. 创建数组 有两种方式：前两种方法需要提前知道需要存放的元素个数！不能动态添加元素！通常用arraylist创建 ① int[] a = {1,2,3}; ② int[] b = new int[]{4,5,6}; ③ List<Integer> arr = new ArrayList<>();  // ArrayList 是List接口的实现类 2. 添加元素 arr.add(element);   // O(1)直接放在尾部 arr.add(index, element); // O(N) 放在指定索引位置 3. 访问元素 arr.get(index); // O(1) 4. 数组长度 arr.size();  5. 修改元素 arr.set(index, newValue);   // O(1) 6. 删除元素 arr.remove(index); arr.remove(element);   // O(N) 默认删除第一次出现的该元素。 7. 遍历 普通for循环；  增强for循环 8. 查找元素 arr.contains(element);  // 返回boolean 9. 排序(内置函数) Arrays.sort(a);   //O(NlogN普通方法创建的数组，排序会更改原数组顺序！ Collections.sort(arr);  //O(NlogN) 通过arraylist创建的数组，排序也会更改原数组顺序！ 倒序：  Arrays.sort(T[], Collections.reverseOrder());   //必须是包装类的数组！ 不能是基本数据类型的数组！           Collections.sort(arr, Collections.reverseOrder());   // 通过arraylist创建的数组，使用该方法倒序排列数组！ 10. arr.toString();  11. arr.subList();  //截取部分arraylist 12. arr.isEmpty();

2、链表

链表包括 单端链表 和 双端链表 单端链表: 一个节点 包括两个属性: 当前节点的值(val) 和 指向下一个节点的指针(next) 双端链表：一个节点 包括三个属性: 当前节点的值(val)， 指向前一个节点的指针(prev) 和 指向后一个节点的指针(next)

方法： 访问（access）： O(N) // 遍历链表 搜索（search）： O(N)  插入（insert）：O(1)  删除（delete）：O(1)

特点：读少写多！

常用操作： 1. 创建链表 LinkedList<Integer> list = new LinkedList<>(); 2. 添加元素   list.add(element);  //默认尾端插入  O(1) list.add(index, element);  //指定位置插入 O(N) list.addFirst();   //头部添加 3. 访问元素   O(N) list.get(element);      4. 查找元素 list.indexOf(element);   //未找到返回 5. 更新元素 O(N) list.set(index, element);  6. 删除元素 O(N) list.remove(index);    list.remove(element); list.clear();   7. 链表长度 O(1) list.size();

3、队列Queue

队列：底层是链表实现的; 因为链表的插入和删除比较快只有O(1)

特点：先入先出

单端队列： 只有一个口可以进，一个口可以出 双端队列： 两个口都可以进， 两个口也都可以出

操作： 访问： O(N) 搜索： O(N) 插入： O(1)    // 默认末尾插入 删除： O(1)    // 只能删除头

常用方法： 常用操作： 1. 创建队列 Queue<Integer> queue = new LinkedList<>(); 2. 添加元素  O(1) queue.add(); 3. 获取即将出队的元素   O(1) int temp = queue.peek(); 4. 删除即将出队的元素   O(1) int temp2 = queue.poll(); 5. 判断队列是否为空  O(1) boolean res = queue.isEmpty(); 6. 队列长度  O(1) queue.size();    7. 遍历队列（边删除 边遍历队列的操作）  O(N) while(!queue.isEmpty()){        int temp = queue.poll(); }

4、栈Stack

先进后出，后进先出 例：浏览器的后退功能

访问栈顶元素： O(1) 搜索： O(N) 插入：O(1) 删除栈顶元素：O(1)

常用方法： 1. 创建栈 Stack<Integer> stack = new Stack<>(); 2. 添加元素  O(1) stack.add(element); stack.push(element); 3. 查看栈顶元素（即将出栈的元素）  O(1) stack.peek(); 4. 删除栈顶元素（即将出战的元素） O(1) int temp = stack.pop();   5. 栈的长度  O(1) stack.size();   6. 栈是否为空  O(1) stak.isEmpty();    7. 遍历栈（便删除栈顶元素，边遍历） O(N) while(!stack.isEmpty()){       int num = stack.pop();       sout(num); }

5、哈希表（散列表）

key : value 键值对 学号： 姓名 1 ： tyq 2 ： xxx 3 ： yyy

key  --> 哈希函数 --> 地址值  哈希碰撞： 不同的key通过哈希函数得到了相同的地址值    --> 用链表解决

访问：  不可以 搜索：O(1)      哈希碰撞情况下： O(k)  k: 碰撞元素的个数 插入:   O(1)   删除:   O(1)  通过key删除

哈希表的常用操作： 1. 创建哈希表     ① String[] hashTable = new String[4];    //把数组的索引当作key，数组的值当作value     ② HashMap<Integer, String> map = new HashMap<>(); 2. 添加元素   O(1)     hashTable[1] = "abc";     map.put(1,"yyy"); 3. 删除元素   O(1)     hashTable[1] = "";     map.remove(index); 4. 修改元素    O(1)     hashTable[1] = "zzzz";     map.put(1, "zzzz");      //覆盖之前1位置的值 5. 获取key对应的value  O(1)     String temp = hashTable[1];     map.get(key); 6. 检查key是否存在  O(1)     map.containsKey(key); 7. 哈希表长度  O(1)     map.size(); 8. 哈希表是否还有元素  O(1)     map.isEmpty();

6、集合Set

无序； 不重复！   主要作用:  1. 检查某一个元素是否存在 2. 检查是否存在重复元素（通过长度判断）

HashSet 元素  -->  哈希函数  -->  哈希值 对应一张哈希表 如果对应位置上没有元素，则直接存到哈希值的对应位置上 如果已经有元素了，则比较两个元素是否相等，如果相等，则更新； 如果不相等，则哈希冲突；

访问： 不存在搜索： 无哈希冲突： O(1)            有哈希冲突：O(k) 插入： 无哈希冲 突：O(1)            有哈希冲突：O(k) 删除： 无哈希冲突：O(1)            有哈希冲突：O(k)

1. 创建集合 HashSet<Integer> set = new HashSet<>(); 2. 添加元素 O(1) set.add(element); 3. 查询元素  O(1) set.contains(element); 4. 删除元素 O(1) set.remove(element); 5. 长度  O(1) set.size();

7、树

节点根节点叶子节点：没有孩子节点的节点

高度： 从最底下算起，从0开始深度： 从上往下计算，根节点是0 层：从上往下算，根节点是第一层

普通二叉树：每个节点最多只能有两个孩子（0个，1个，2个都可以）满二叉树：除了叶子节点，每个节点都有左右两个孩子，所有叶子节点必须在同一个层上！！完全二叉树：从树的根节点开始，从上到下，从左到右，依次填满节点形成的二叉树。注意: 满二叉树 一定是 完全二叉树； 完全二叉树 不一定是 满二叉树！！

二叉树的遍历： 1. 前序遍历： 根节点 -> 左子树 -> 右子树   （根左右） 2. 中序遍历： 左子树 -> 根节点 -> 右子树    （左根右） 3. 右序遍历： 左子树 -> 右子树 -> 根节点     （左右根）

8、堆

堆是完全二叉树，并且每个节点 >= 或 <= 孩子节点

每个节点 >= 孩子节点   ==》   最大堆 每个节点 <= 孩子节点   ==》   最小堆

特点： 最大堆： 最大值 是 堆顶元素 最小堆： 最小值 是 堆顶元素

访问： 不存在搜索：（访问堆顶元素） O(1)             (访问其他元素） O(N) 添加： O(log N) 删除：O(log N)  （当删除堆顶元素时，会先将右下角的元素放到堆顶(为了维系完全二叉树的结构)，然后再层层比较，把小的元素放到堆顶）

1. 创建堆（最大堆、最小堆）  PriorityQueue<Integer> minheap = new PriorityQueue<>(); PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder()); 2. 添加元素 minheap.add(element); 3. 获取堆顶元素 minheap.peek(); maxheap.peek(); 4. 删除对顶元素 int temp = minheap.poll(); int temp = maxheap.poll(); 5. 堆的长度 minheap.size(); 6. 堆的遍历（边删除边遍历） while(!minheap.isEmpty()){       sout(minheap.poll); }