数据结构

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

方法：
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();

链表包括 单端链表 和 双端链表
单端链表: 一个节点 包括两个属性: 当前节点的值(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();

队列：底层是链表实现的; 因为链表的插入和删除比较快只有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();
}

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

访问栈顶元素： 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);
}

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();

无序； 不重复！  

主要作用: 
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();

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

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

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

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

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

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

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

访问： 不存在 搜索：（访问堆顶元素） 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);
}