📖 前言
在学习数据结构与算法之前, 我们要知道什么是数据结构？为什么要学数据结构与算法？
• 数据结构就是研究数据如何在计算机中进行组织和存储, 使我们可以高效的获取数据和修改数据.
• 要写出好的程序一定要学好数据结构与算法, 我们脑海里要时刻有如下这个公式：
数据结构 + 算法 = 程序
• 在学习数据结构过程中，我们要形成一种意识：并不是简单的实现，而是强调比较和优化。
数据结构可以分为三类：
• 线性结构：数组、队列、栈、链表、哈希表...
• 树型结构：二叉树、二分搜索树、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 操作时，如果过于着急会出现均摊度的震荡问题，此时我们可以在缩容的时候缓一点。
