（一）动态数组

本是古典何须时尚 2022-05-14 11:22 172阅读 0赞

*  前言
 *  已实现方法
 *  思想
 *  复杂度的分析（均摊复杂度、复杂度震荡）
 *  java 代码

--------------------

# 前言 #

`java` 内置的数组是`静态`的，我们可以基于它提供的`静态数组`，开发属于我们自己的`动态数组`，并且，保证其操作的复杂度，和 `java` 提供的`静态数组`，没有多大的差别，基本一致 ；

--------------------

# 已实现方法 #

![这里写图片描述][70]

--------------------

# 思想 #

底层使用 `java` 的内置数组；

对外暴露两个构造器：**一个接收一个参数，代表初始创建多大的数组 ；另一个无参构造器，底层默认创建大小为10的数组 ；**

动态的实现，在于 `reSize()` 方法，会对数组大小进行动态伸缩；

比如我们最初的数组容量为 `n` ，当我们添加元素的个数大于数组容量的时候，我们就调用 `reSzie()` 方法，对数组进行扩容，这里，我们选择扩容到 `2n` ；

当数组的实际元素个数等于 `n/4` 的时候，我们就对数组进行缩小，这里，我选择讲起缩小到 `n/2` ；不要直接缩小到 `n/4` ，会造成 **`复杂度震荡`**，具体原因，代码的注释中有讲，并其缩小的时候，注意传进去的参数，不能为 `0` ，因为不能创建大小为 `0` 的数组 ；

--------------------

# 复杂度的分析（均摊复杂度、复杂度震荡） #

关于复杂度的分析，在代码眉头的注释里 ；

--------------------

# java 代码 #

package xin.ijava.array;
 
 
 /** * @author An * @description 自定义开发动态数组，基于java数组的二次封装 * @date 2018年9月5日15:46:00 * * * 动态数组 （实现很简单） * * 时间复杂度的分析 * * ------------------------------- 增 ---------------------------- * * addLast() O(1) ; * addFirst() O(n) ; * add() 0(n/2) = O(n) ; * reSize() 0(n) ; * * ------------------- addLast() 复杂度 -------------------- * 其中 addLast() ，会有几率触发 reSize()，但是我们还是认定它的复杂度是 O(1) 的，这里需要计算均摊复杂度 ； * 因为不是每次 addLast() 都会触发 reSize() ，假如 capacity 是 n ,那么 n+1 次 addLast() ，才会触发 reSize() ； * 均摊一下计算，就是 n+1 次 addLast() 操作，会进行 n+1+n 次基本操作，折算一下，一次 addLast() ，差不多 2 次 * 基本操作，因此我们认定 addLast() 的复杂度就是 0（1） 的 ； * * ------------------ 复杂度震荡 -------------------------- * addLast() 和 removeLast() ，这两个方法，都有几率触发 reSize（） ；假如现在数组容量已经满了，再次 * addLast() 就会触发 reSize() ，此时复杂度变为 O(n) ，然后，假如我们继续 addLast() 的话，那么之前的复杂度 * 就会被均摊下去。但是，假如我们现在进行的是 removeLast() ，按照之前的逻辑，数组中的实际元素个数变为数组容量的 * 一半时，就进行 reSize()，那么又会进行复杂度为 O(n) 的操作，假如一直 addLast() 和 removeLast() 交替下去，那么 * 本来均摊复杂度应该为 O(1) 的操作，将会变为 O(n) ，均摊也不会降低复杂度了；这种情况，就叫复杂度震荡 ； * * 解决方法就是，在缩容的时候，不要太着急，当数组的实际元素个数等于容量的一半的时候，不要进行 reSize() 操作， * 而是等实际元素个数等于容量的 1/4 的时候，再 reSize() ，并且 reSize() 也不是直接缩到当前容量的 1/4 ,不然进行 * addLast() 又会进行 reSize()，我们让其 reSize() 缩到当前容量的 1/2 ；这样，就可以避免复杂度震荡了 ； * * * 结论：最坏情况下的复杂度是 O(n) 的 ； * * * * ----------------------- 删 ---------------------- * * removeLast() O(1) ； 跟 addLast() 一样 ，最后均摊下来都是 O(1) * removeFirst() 0(n) ; * remove() 0(n/2 + 1) = O(n) ; * removeElement() 0(n + n ) = 0(n) ; * removeAllElement() 0( n * n ) ; * * 结论：最坏情况下的复杂度是 O(n) 的 ； * * * * * ---------------------------- 改 ------------------------------- * * set() 0(1) ; * * 结论：改，是数组的拿手好戏了，优势杠杠的 ； * * * * ---------------------------- 查 ------------------------------- * * find() O(n) ; * contains() 0(n) ; * get() 0(1) ; * * * * 总结：我们的动态数组，复杂度还是很 ok 的，并且实现起来，也很方便 ； */
 @SuppressWarnings("unused")
 public class Array<E> { 
 /** * 内部维护的数组，动态数组基于其开发 */
 private E[] arr;
 /** * 数组中的存储的实际元素个数 */
 private int size;
 
 /** * 创建用户给定的空间大小的数组 */
 public Array(int capacity) {
 // 创建数组，不支持泛型数组，需要绕点弯子，创建泛型数组
 arr = (E[]) new Object[capacity];
 // 初始记录size的数量为 0
 size = 0;
 }
 
 /** * 默认开辟容量为 10 的数组 ； */
 public Array() {
 this(10);
 }
 
 /** * 判断数组 是否为空 * * @return true 为空 */
 public boolean isEmpty() {
 return size == 0;
 }
 
 
 /** * 向相应的下标位置上添加元素 * * @param index 目标下标 * @param e 目标元素 */
 public void add(int index, E e) {
 
 // 数组是否满了
 if (size == arr.length) {
 reSize(2 * size);
 }
 // 下标 是否越界
 if (index < 0 || index >= arr.length) {
 throw new IllegalArgumentException("index is out of array ;");
 }
 
 // 添加元素
 for (int i = size; i > index; i--) {
 arr[i] = arr[i - 1];
 }
 arr[index] = e;
 size++;
 }
 
 /** * 向数组中追加元素 * * @param e 目标元素 */
 public void addLast(E e) {
 add(size, e);
 }
 
 /** * 向数组的第一个位置 添加元素 * * @param e 目标元素 */
 public void addFirst(E e) {
 add(0, e);
 }
 
 /** * 数组 是否 包含某一个元素 * * @param e 目标元素 * @return 包含返回 true */
 public boolean contains(E e) {
 for (int i = 0; i < size; i++) {
 if (arr[i].equals(e)) {
 return true;
 }
 }
 return false;
 }
 
 /** * 数组 是否 包含某一个元素 * * @param e 目标元素 * @return 查到则返回对应的下标，不存在，则返回 -1 ； */
 public int find(E e) {
 for (int i = 0; i < size; i++) {
 if (arr[i].equals(e)) {
 return i;
 }
 }
 return -1;
 }
 
 /** * 返回对应下标上的元素 * * @param index 目标下标 * @return 目标元素 */
 public E get(int index) {
 // 下标 是否越界
 if (index < 0 || index >= arr.length) {
 throw new IllegalArgumentException("Get fail ; index is out of array ;");
 }
 
 if (index >= size) {
 throw new IllegalArgumentException("Get fail ; index is bigger than size ;");
 }
 
 return arr[index];
 }
 
 /** * 返回最后一个元素 * @return 目标元素 */
 public E getLast() {
 return get(size - 1);
 }
 
 /** * 返回第一个元素 * @return 目标元素 */
 public E getFirst() {
 return get(0);
 }
 
 
 /** * 返回数组实际元素个数 * * @return */
 public int getSize() {
 return size;
 }
 
 /** * 返回数组容量 * * @return */
 public int getCapacity() {
 return arr.length;
 }
 
 /** * 移除对应下标的元素 * * @param index * @return */
 public E remove(int index) {
 E temp = arr[index];
 // 下标 是否越界
 if (index < 0 || index >= size) {
 throw new IllegalArgumentException("Add fail ; index is out of array ;");
 }
 if (isEmpty()) {
 throw new IllegalArgumentException("Remove fail ; array is empty");
 }
 
 for (int i = index; i < size - 1; i++) {
 arr[i] = arr[i + 1];
 }
 size--;
 
 arr[size] = null ;
 
 if (size == arr.length / 4 && arr.length / 2 != 0 ) {
 reSize(arr.length / 2);
 }
 
 return temp;
 }
 
 /** * 对数组长度进行动态的变化； * * @param size */
 private void reSize(int size) {
 E[] es = (E[]) new Object[size];
 for (int i = 0; i < this.size; i++) {
 es[i] = arr[i];
 }
 arr = es;
 }
 
 /** * 移除 匹配到的第一个目标元素 * * @param e 目标元素 * @return 移除返回true */
 public boolean removeElement(E e) {
 int index = find(e);
 if (index != -1) {
 remove(index);
 return true;
 }
 return false;
 }
 
 /** * 移除掉 数组中所有的目标的元素 * * @param e 目标元素 */
 public void removeAllElement(E e) {
 while (removeElement(e)) {
 }
 }
 
 /** * 移除第一个 * * @return */
 public E removeFirst() {
 return remove(0);
 }
 
 /** * 移除最后一个 * * @return */
 public E removeLast() {
 return remove(size - 1);
 }
 
 /** * 更改目标位置的元素 * * @param index * @param e */
 public void set(int index, E e) {
 add(index, e);
 }
 
 /** * 改变打印方式 * * @return */
 @Override
 public String toString() {
 StringBuilder builder = new StringBuilder();
 builder.append(String.format("array 's size is %d , capacity is %d ; \n", size, arr.length));
 builder.append("[ ");
 for (int i = 0; i < size; i++) {
 builder.append(arr[i]);
 if (i != size - 1) {
 builder.append("，");
 }
 }
 builder.append(" ]");
 return builder.toString();
 }
 }

[70]: /images/20220514/1a4302e3a0f0416491a7b5ed6d94a64a.png