纯数据结构Java实现(1/11)(动态数组)
- 2019 年 10 月 3 日
- 筆記
我怕说这部分内容太简单后，突然蹦出来一个大佬把我虐到哭，还是悠着点，踏实写
大致内容有: 增删改查，泛型支持，扩容支持，复杂度分析。(铺垫: Java语言中的数组)
基础铺垫
其实没啥好介绍的，顺序存储，(非受限的)线性结构。查询O(1)，因为支持随机存取。
Java中的数组
Java 中的数组操作，大致如下:
int[] arr = new int[10] String[] strArr = new String[9] // 定义的时候就有初始值 --- 自动感知数组长度 int[] scores = new int[]{100, 99, 88} //获取数组的长度 arr.length //for each 循环 (数组是可迭代对象) for(int s in arr){ System.out.println(s) }但不同于 Python 这类动态脚本语言，Java中的数组只能存储相同类型的元素。
- Java比较奇葩，
长度一会儿是 length, 一会儿是 length()，一会儿是 size() - 可以大致按照数组-属性，字符串-方法，其他容器-size() 来记忆
自己实现
先别管动态扩容的部分，现在就看数组这个容器，如何实现增删改查
大体思路
其实就是内部封装一个 int[] 数组，为了方便，顺便需要一个长度属性。
package array; public class MyArray { //先声明一下相应的变量, 不暴露给外部 (内部维护保持两者一致) private int[] data; //capacity 就是 data 的 length private int size; // 构造函数，传入数组容量 public MyArray(int capacity) { data = new int[capacity]; size = 0; //初始情况下，实际有 0 个元素 } //提供一个默认的吧, 不需要用户手动提供 capacity, 无参 public MyArray() { this(10); } //获取数组元素个数 public int getSize() { return size; } //返回动态数组的容量 public int getCapacity() { return data.length; } //数组此刻是否为空 public boolean isEmpty() { return size == 0; } }- capacity 容量，数组实际装了多少，用 size 表示
- capacity 可以用内部数组的长度表示，及 data.length
上面就是整体的框架。(还没有涉及动态扩容)
增删改查
因为赶时间，所以增删改查一起来。
添加元素
此时 size 应该指向的是，要添加元素的下一个位置。即尾部添加时 size++ 。
简单想: 一开始没有元素，size 在 0 位置，即第一个元素的位置。
尾部添加:
public void append(int elem) { //TODO: 考虑一下是否超过容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } this.data[size++] = elem; } //如果实现了 insert(key, elem) 方法，可以直接写成 //末尾添加 public void append(int elem) { insert(size, elem); }指定位置添加:
//指定位置插入 public void insert(int index, int elem) { //TODO: 考虑一下是否超过容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } //检查 index 是合法的 if(index < 0 || index > size){ throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size "); } //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index) for(int i = size-1; i>=index; i--){ data[i+1] = data[i]; } data[index] = elem; //覆盖原来的 index 处的内容 size++; }注意一下，要维护 size 。
头部添加:
此时就可以复用 insert 方法了:
//头部添加 public void presert(int elem){ insert(0, elem); }遍历元素
其实就是遍历内部封装的数组，找到相应的元素。
获取整体: （覆写 toString 这个方法）
//获取数组整体，即打印时需要显示的信息 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("MyArray: size=%d, capacity=%dn", size, data.length)); res.append("["); //只遍历现有元素，而不是容量 for (int i = 0; i < size; i++) { res.append(data[i]); if(i != size-1){ res.append(", "); } } res.append("]"); return res.toString(); }测试看看:
import array.MyArray; public class Main { public static void main(String[] args) { MyArray arr = new MyArray(20); //容量20 //放入 10 个元素 for(int i=0; i< 10; i++){ arr.append(i); } System.out.println(arr); arr.insert(1, 100); System.out.println(arr); } } //输入结果如下: MyArray: size=10, capacity=20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]取出具体元素 (getter)
按照索引取。
//获取某个具体元素: 通过封装，加入自定义 index 检查(保证获取数据安全) public int get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } return data[index]; }修改元素 (setter)
按照索引修改。
//更新元素 public void set(int index, int elem) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } data[index] = elem; }是否包含
线性遍历一遍，看看是否存在
//是否包含 public boolean contains(int elem) { for (int i = 0; i < size; i++) { if (data[i] == elem) { return true; } } return false; }搜索元素
还是线性搜索一下，找到就返回下标
public int find(int elem){ for(int i=0; i<size; i++){ if(data[i] == elem){ return i; } } return -1; //没有找到返回 -1 }删除元素
删除就是覆盖，大致分为两类: 按照索引删除，按照元素删除。
从 index 开始到 size-1，不断往前赋值，最后维护一下整体的 size-—。
(size的元素用户是拿不到的，所以data[size]值不必担心)
//删除元素 (通常要返回相应的元素) public int remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存储起来 int ret = data[index]; //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因为用户取不到 data[size] return ret; }当然也可以补充一些快捷方法:
//快捷删除尾部元素 public int pop(){ return remove(size-1); } //快捷删除头部元素 public int popLeft(){ return remove(0); }按照元素删除: 先查找，然后删除
//删除指定元素 (不必返回，因为用户已经知道 elem) public void removeElem(int elem){ int index = find(elem); if(-1 == index) { throw new IllegalArgumentException("Remove failed, cannot find this elem"); } //成功了什么都不提示，出错才提示 remove(index); }- 默认都是查找，删除第一个找到的元素
简单测试一下，删除:
//[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除试试 arr.remove(1); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除末尾试试 arr.pop(); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8] //删除头部试试 arr.popLeft(); System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8] //删除 4 这个数字 arr.removeElem(4); System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8]泛型支持
语法限制
由于泛型的限制(不能放入基本类型，只能放入其包装类)，内部封装的数组初始化的时候需要强制类型转换一下。
也就是说，可以用于声明，但不能用于定义。
data = new E[capacity]; //报错，历史遗留问题，不支持该语法 //正确的写法 (借助强制类型转换) data = (E[])new Object[capacity];完整代码
特别注意一下:
- 对象值的比较，需要改成
equals - 删除的时候，因为存储的是对象的引用，所以应该把移动后的
data[size]位置设置为NULL- 但是这一条是非必须，因为
闲逛对象 != memory leak
- 但是这一条是非必须，因为
还是贴一下，支持泛型的完整代码吧:
package array; public class AdvanceArray<E> { //先声明一下相应的变量, 不暴露给外部 (内部维护保持两者一致) private E[] data; //capacity 就是 data 的 length private int size; // 构造函数，传入数组容量 public AdvanceArray(int capacity) { data = (E[])new Object[capacity]; size = 0; //初始情况下，实际有 0 个元素 } //提供一个默认的吧, 不需要用户手动提供 capacity, 无参 public AdvanceArray() { this(10); } //获取数组元素个数 public int getSize() { return size; } //返回动态数组的容量 public int getCapacity() { return data.length; } //数组此刻是否为空 public boolean isEmpty() { return size == 0; } //末尾添加 public void append(E elem) { insert(size, elem); } //头部添加 public void presert(E elem) { insert(0, elem); } //指定位置插入 public void insert(int index, E elem) { //TODO: 考虑一下是否超过容量 if (size == data.length) { throw new IllegalArgumentException("append failed"); } //检查 index 是合法的 if (index < 0 || index > size) { throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size "); } //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index) for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = elem; //覆盖原来的 index 处的内容 size++; } //获取数组整体，即打印时需要显示的信息 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("MyArray: size=%d, capacity=%dn", size, data.length)); res.append("["); //只遍历现有元素，而不是容量 for (int i = 0; i < size; i++) { res.append(data[i]); if (i != size - 1) { res.append(", "); } } res.append("]"); return res.toString(); } //获取某个具体元素: 通过封装，加入自定义 index 检查(保证获取数据安全) public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } return data[index]; } //更新元素 public void set(int index, E elem) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed, Index is illegal"); } data[index] = elem; } //是否包含 public boolean contains(E elem) { for (int i = 0; i < size; i++) { if (data[i].equals(elem)) { return true; } } return false; } //搜索元素 public int find(E elem) { for (int i = 0; i < size; i++) { if (data[i].equals(elem)) { return i; } } return -1; //没有找到返回 -1 } //删除元素 (通常要返回相应的元素) public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存储起来 E ret = data[index]; //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因为用户取不到 data[size] //当使用泛型，对对象元素支持时 data[size] = null; //方便 java 回收 loitering objects (非必须，闲逛对象 != memory leak) return ret; } //快捷删除尾部元素 public E pop() { return remove(size - 1); } //快捷删除头部元素 public E popLeft() { return remove(0); } //删除指定元素 (不必返回，因为用户已经知道 elem) public void removeElem(E elem) { int index = find(elem); if (-1 == index) { throw new IllegalArgumentException("Remove failed, cannot find this elem"); } //成功了什么都不提示，出错才提示 remove(index); } }测试代码如下:
//这个类主要用于 AdvanceArray 做泛型测试 public class Student { private String name; private int score; public Student(String studentName, int studentScore){ name = studentName; score = studentScore; } @Override public String toString() { return String.format("Student(name: %s, score: %d)", name, score); } } // main.java 中: public class Main { private static void test_2(){ //泛型不支持基本类型，所以这里写 Integer；使用时会自动box，unbox AdvanceArray<Integer> arr = new AdvanceArray<>(20); //容量20 //放入 10 个元素 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //插入试试 arr.insert(1, 100); System.out.println(arr); //[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除试试 arr.remove(1); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除末尾试试 arr.pop(); System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8] //删除头部试试 arr.popLeft(); System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8] //删除 4 这个数字 arr.removeElem(4); System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8] } private static void test_3(){ AdvanceArray<Student> arr = new AdvanceArray<>(); //默认容量是 10 //添加测试数据 arr.append(new Student("AAA", 100)); arr.append(new Student("BBB", 90)); arr.append(new Student("CCC", 60)); System.out.println(arr); } } // 测试结果 MyArray: size=3, capacity=10 [Student(name: AAA, score: 100), Student(name: BBB, score: 90), Student(name: CCC, score: 60)]动态支持
上面其实没有支持动态扩容，也就不能称为一个
动态数组
上面的做法是，一旦检测到索引异常，基本都抛异常结束流程了；正常索引就插入，但没有考虑插入之后超过容量了怎么办？（在容量满的时候就应该检测到了）
解决方案，最基本的就是:
- 1.开辟新空间
- 2.把元素复制过去
但这只是扩容支持，如果元素缩减到一定程度，那么也应该减少容量。
增加扩容
//主要就是修改 insert 函数 public void insert(int index, E elem) { //检查 index 是合法的 if (index < 0 || index > size) { throw new IllegalArgumentException("insert failed, need: index >=0 and index <= size "); } //满了，那么就扩容吧 -- 这里不再是抛异常对象了 if (size == data.length) { resize(2 * data.length); //java arraylist 选择的是 1.5 倍 } //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index) for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = elem; //覆盖原来的 index 处的内容 size++; } private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity]; //复制旧元素过去 for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; }简单测试一下:
//初始容量为 10，先初始化 10 个元素 AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默认为 10 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //再添加一个元素，试试 arr.append(100); System.out.println(arr); //输出结果: MyArray: size=10, capacity=10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100]删除缩减
删除元素的之后，如果空间小到一定程度，自动缩减空间
- 只要就是在删除后，做一下 size 和 capacity 的判断，然后 resize
(即删除后，size 为 capacity 的一半就可以缩容了)
//初始容量为 10，先初始化 10 个元素 AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默认为 10 for (int i = 0; i < 10; i++) { arr.append(i); } System.out.println(arr); //再添加一个元素，试试 -- 此时容量变为 20，实际占用 11 arr.presert(100); System.out.println(arr); //pop一个，容量立马缩减为 10 arr.pop(); System.out.println(arr); //运行结果为: MyArray: size=10, capacity=10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=11, capacity=20 [100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] MyArray: size=10, capacity=10 [100, 0, 1, 2, 3, 4, 5, 6, 7, 8]最后，扩容或者删除容量，对于 client 而言，它并不知道。(扩容策略也可以在细致些)
复杂度分析
O(1) -> O(logn)优良 —> O(n) 一般 —> O(nlogn) 一般般,其实和O(n)差不太多 —> O(n^2) 差 —>O(C^n) 超差
一般谈起来，会说和运行规模成: 常数关系，对数关系，线性关系，nlogn，平方关系，指数关系。简单理解就是，级大一级压死人。
详细分析
添加操作:
-
末尾插入 append: O(1)
-
头添加 presert: O(n)
-
任意位置插入 insert(index): 在 O(1) 和 O(n) 之间，假设 index 的取值概率一样，index 靠前的时候越慢，越靠后越快，整体需要靠具体需要移动多少个元素，n + (n-1) + … + 0，n 种情况，平均需要移动的元素 n/2，所以复杂度是 O(n/2)，即 O(n)
resize 的操作也是 O(n)。
(尾部操作也可能是 O(n)，但几率比较小，不可能每次都触发 resize)
综上所述，以最差来考虑，即 O(n)。 (一般考虑的是概率最高的情况)
删除操作: (其实分析方法类似，核心因素还是元素的移动)
- 末尾删除 pop(): O(1)
- 头删除 popLeft(): O(n) 因为元素要往前面移动
- 任意位置，平均 remove(index): O(n/2)，即 O(n)
resize 的操作也是 O(n)。
(头部操作也可能是 O(n)，但几率比较小，不可能每次都触发 resize)
综上所述，以最差来考虑，即 O(n)。
修改操作: 因为可以支持随机访问(按地址，索引)，所以复杂度 O(1)
查找操作:
- get(index): O(1)
- contains(e): O(n) 线性遍历
- find(e): O(n) 线性遍历
从上面也可以看出，时间复杂度和顺序存储情况一致。
均摊复杂度
也就是仔细考虑一下包含这个 扩容&缩容 耗时操作的 remove/insert 到底应该算作 O(1) 还是 O(n)。
比如 addLast() 本来是 O(1)，加入动态支持后，此时还是 O(1) 么。
显而易见，容易得证:
假设 capacity = n，那么进行 n+1 次 addLast，触发扩容，此时包括移动元素，总共操作 2n+1 次，也就是说平均每次 addLast 触发 (2n+1)/(n+1) 即 2 次操作，即常量次操作，所以 addLast() 算均摊，也是 O(1)。
震荡优化
刚添加一个元素，扩容；立马删除一个元素，又缩容
连环的 addLast 和 removeLast 导致最近的操作都是 O(n)。(常规而言是O(1)的)
此时就要延迟处理(lazy)缩容，即真实元素为 1/4 capacity时才容量减半。
代码如下:
//删除元素 (通常要返回相应的元素) public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed, Index is illegal"); } //先把要返回的值存储起来 E ret = data[index]; //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2 for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; //data[size] 不必清空，因为用户取不到 data[size] //当使用泛型，对对象元素支持时 data[size] = null; //方便 java 回收 loitering objects (非必须，闲逛对象 != memory leak) //缩减 (只在一个特定的时机缩减，不能用 < 或者 >，可能会存在多次缩减) //注意一下，延迟缩减，即 1/4 时，才缩减为一半 (还有一半是空的) if(size == data.length/4 && data.length/2 != 0) { resize(data.length/2); //那么就缩减为一半 } return ret; }上面有个技巧或者编程语言问题， data.length/2 != 0，因为 java 的除法默认是截断的，即可能出现 capacity 为 0 的情况。比如，当前capacity = 1 即 data.length 为 1，即便 size=0，也不能再缩减了(否则执行缩减， capacity 就为 0了)。
总结
顺序存储的结构，不管是不是线性的，基本都有这些操作特征，只不过上层接口隐藏了实现细节，比如 顺序栈 这类受限的结构，底层就是封装了动态数组(而非原始数组了)。
实现的时候注意移动操作从哪里开始，索引合法性判断以及记得维护 size。
深怕有人需要这些粗鄙的代码，我还是把它放在了 gayhub 上，供您参考。
如有不足之处，万望批评指正，虾虾侬。
