📖 前言
在学习数据结构与算法之前, 我们要知道什么是数据结构？为什么要学数据结构与算法？
• 数据结构就是研究数据如何在计算机中进行组织和存储, 使我们可以高效的获取数据和修改数据.
• 要写出好的程序一定要学好数据结构与算法, 我们脑海里要时刻有如下这个公式：
数据结构 + 算法 = 程序
• 在学习数据结构过程中，我们要形成一种意识：并不是简单的实现，而是强调比较和优化。
数据结构可以分为三类：
• 线性结构：数组、队列、栈、链表、哈希表...
• 树型结构：二叉树、二分搜索树、AVL树、红黑树、堆、Trie、线段树、并查集...
• 图结构： 邻接矩阵、邻接表
🎀 数组
概念：
✎ 一组相同数据类型的数或相同类型数的集合.
数组在内存中如何分配：
✎ 分配的是连续的空间, 因此在创建数组时要指定数组的大小, 数组一旦创建就不能修改.
如何声明和定义数组：
✎ int [] arr = new int[10] ;
数组操作：
✎ 增删改查 (crud) 【C:Create(创建) Retrieve(查询) Update(更新) Delete(删除)】
如何使用数组：
✎ 通过数组的下标(索引) 下标是从0开始的，至数组中元素的个数(数组的长度)-1 arr.length
常见问题：
✎ 空数组---[ ] 空对象---null
NullPointException 空指针异常（要知道谁为空）
ArraysIndexOutOfBoundsException 下标越界
数组优缺点：
✎ 优：快速查询！ 缺：删除/添加元素慢！
常见数组有：
✎ 字符串、哈希表、对象数组.
🎀 自建数组 MyArray
创建属于自己的数组 ----- 注意：是基于java中的数组进行二次封装.
✰ 定义属性 (数据容器、实际存放元素个数、容积)
public class MyArray<T> { //定义数据容器 private T[] data; //实际存放元素的个数 private int size; //容积 capacity private int capacity;
✰ 创建构造方法 (无参构造方法和有参构造方法)
public MyArray() { this(100); } public MyArray(int capacity) { //先判断容积是否合法,不合法默认容积为一个值 if (capacity <= 0) { capacity = 100; } this.capacity = capacity; this.size = 0; this.data = (T[]) new Object[this.capacity]; }
实现MyArray类的功能 (常用方法)
//获取数组容积 public int getCapacity() { return this.capacity; } //判断是否为空 public boolean isEmpty() { return this.size == 0; } //获取实际存放元素的大小 public int getSize() { return this.size; }
✰ 数组操作（增删改查）
📌 添加元素
//添加元素 public void add(int index, T ele) { if (index < 0 || index > this.size) { throw new IllegalArgumentException("index is invalid!"); } //判断是否扩容 if (index == this.capacity) { resize(this.capacity * 2); } //判断哪些元素后移 for (int i = this.size; i >= index; i--) { this.data[i + 1] = this.data[i]; } this.data[index] = ele; this.size += 1; } //在头部添加 public void addHead(T ele) { add(0, ele); } //在尾部添加 public void addTail(T ele) { add(this.size, ele); }
📌 删除元素
//删除操作 public T remove(int index) { if (index < 0 || index > this.size) {//先判断索引是否合法 throw new IllegalArgumentException("index is invalid!"); } //保存删除元素 T delVal = this.data[index]; for (int i = index + 1; i < this.size; i++) { this.data[i - 1] = data[i]; } this.size--; if (this.size <= (this.capacity / 4) && capacity / 2 > 1) { resize(this.capacity / 2); } return delVal; } public T removeHead() {//删除头部元素 return remove(0); }
修改元素
//修改操作 public void updateByIndex(int index, T ele) { if (index < 0 || index > this.size) {//先判断索引是否合法 throw new IllegalArgumentException("index is invalid!"); } this.data[index] = ele; }
查询元素
//查询某个元素是否存在 public boolean contains(T ele) { for (int i = 0; i < this.size; i++) { if (this.data[i].equals(ele)) { return true; } } return false; } //查询元素在数组中是否存在,如果存在，返回索引，否则返回-1 public int findIndex(T ele) { for (int i = 0; i < this.size; i++) { if (this.data[i].equals(ele)) { return i; } } return -1; }
完整代码
package com.learn.study1; public class MyArray<T> { //定义数据容器 private T[] data; //实际存放元素的个数 private int size; //容积 capacity private int capacity; public MyArray() { this(100); } public MyArray(int capacity) { if (capacity <= 0) { capacity = 100; } this.capacity = capacity; this.size = 0; this.data = (T[]) new Object[this.capacity]; } //获取数组容积 public int getCapacity() { return this.capacity; } //判断是否为空 public boolean isEmpty() { return this.size == 0; } //获取实际存放元素的大小 public int getSize() { return this.size; } //添加元素 public void add(int index, T ele) { if (index < 0 || index > this.size) { throw new IllegalArgumentException("index is invalid!"); } //判断是否扩容 if (index == this.capacity) { resize(this.capacity * 2); } //判断哪些元素后移 for (int i = this.size; i >= index; i--) { this.data[i + 1] = this.data[i]; } this.data[index] = ele; this.size += 1; } //在头部添加 public void addHead(T ele) { add(0, ele); } //在尾部添加 public void addTail(T ele) { add(this.size, ele); } //修改操作 public void updateByIndex(int index, T ele) { if (index < 0 || index > this.size) {//先判断索引是否合法 throw new IllegalArgumentException("index is invalid!"); } this.data[index] = ele; } //查询某个元素是否存在 public boolean contains(T ele) { for (int i = 0; i < this.size; i++) { if (this.data[i].equals(ele)) { return true; } } return false; } //查询元素在数组中是否存在,如果存在，返回索引，否则返回-1 public int findIndex(T ele) { for (int i = 0; i < this.size; i++) { if (this.data[i].equals(ele)) { return i; } } return -1; } //删除操作 public T remove(int index) { if (index < 0 || index > this.size) {//先判断索引是否合法 throw new IllegalArgumentException("index is invalid!"); } //保存删除元素 T delVal = this.data[index]; for (int i = index + 1; i < this.size; i++) { this.data[i - 1] = data[i]; } this.size--; if (this.size <= (this.capacity / 4) && capacity / 2 > 1) { resize(this.capacity / 2); } return delVal; } public T removeHead() {//删除头部元素 return remove(0); } //重写toString @Override public String toString() { //[1,2,3,4] StringBuilder sb = new StringBuilder("["); for (int i = 0; i < this.size; i++) { sb.append(this.data[i].toString()); if (i != this.size - 1) { sb.append(","); } } sb.append("]"); return super.toString(); } private void resize(int newCapacity) { System.out.println("resize操作,新的容积:" + newCapacity); T[] newData = (T[]) new Object[newCapacity]; //空间复杂度 O(n) // 将原数组中的数组复制到新数组中 // 时间复杂度O(n) for (int i = 0; i < this.size; i++) { newData[i] = this.data[i]; } // 更新容器 this.data = newData; // 更新容积 this.capacity = newCapacity; } public static void main(String[] args) { } }
🎀 复杂度分析和均摊复杂度
• 在算法领域，使用复杂度分析的内容来评价写的代码性能如何。
📌时间复杂度
- 通常情况下我们只需要简单的时间复杂度分析就OK！
- 大O描述的是算法的运行时间和输入数据之间的关系 (数据量要足够的大,趋于无穷)
- 通常情况有：O(1)，O(n)，O(Ign)，O(nIogn)，O(n^2)
• 在计算时需要忽略常数，如：
T = 2*n+2 -------- O(n)
T = 20000*n+50000 -------- O(n)
T = 5 * n * n + 5 -------- O(n^2)
这时很多小伙伴就问了：比如n取10, T2明显时间大于T3啊，注意：此时我们要考虑n趋于无穷的情况 （而n趋于无穷时常数就可以忽略）
综合来看：
- 增：O(n)
- 删：O(n)
- 改：已知索引O(1)；未知索引O(n)
- 查：已知索引O(1)；未知索引O(n)
📌均摊时间复杂度
resize O(n)
假设capacity = n , n+1次addLast ，触发resize(扩容)，一共进行了2n+1次操作，平均每次addLast操作进行两次操作，这样均摊计算：时间复杂度为O(1)
注意：
当我们同时进行 addLast 和 removelast 操作时，如果过于着急会出现均摊度的震荡问题，此时我们可以在缩容的时候缓一点。
