写点什么

算法入门 - 动态数组的实现(Java 版本),分层架构图案例

用户头像
极客good
关注
发布于: 刚刚

}


通过循环把元素放入指定的位置中,类似于这样:



这是一个静态数组,因为我们在第一步初始化的时候就已经固定了它的长度,后面再也无法改变。所以,由于有这个限制,静态数组不适用于那些不确定储存多少数据的场景。


但是如果数组满了,能否再新建一个更长一些的数组,把原数组这些元素再转移到新数组中呢?这样一来,数组就可以继续使用了。按照这个思路,我们就可以创建基于静态数组的动态数组。


[](


)动态数组的实现原理


========================================================================


“动态”主要体现在以下几方面:


[](


)1.添加元素




不局限于只在数组末尾添加,而是能够随意选择索引位置(只要不超过数组长度)。例如在索引为 1 处添加元素 4:



从图中可以看出,需要将 index 处及右侧的元素依次向右移动一个单位(从末位元素开始),最后用新增元素覆盖 index 处元素。


[](


)2.删除元素




同添加元素,也可根据索引进行选择。例如删除索引为 0 处的元素 3:



删除元素移动元素的方向与添加元素正好相反,从 index 处开始,直接使用后一位元素覆盖前一位元素,最后将末位元素置为 null。


[](


)3.数组扩容




数组一旦装满元素,可触发数组扩容,即新建一个更长的数组,将原数组元素转移到新数组中,并将引用指向新数组,完成数组的变更;



[](


)4.数组缩减




如果数组元素相对总容量来说过少(例如数组元素个数小于数组容量的 1/4),便可触发数组缩减,即新建一个更短的数组,并转移元素至新数组。



[](


)代码实现


===================================================================


以下通过新建一个 Array 类,依次实现这几个重要功能:


public class Array<E> {


private E[] data; // 使用静态数组存放数组元素


private int size; // 记录数组元素数量


public Array(int capacity) {


this.data = (E[]) new Object[capacity];


this.size = 0;


}


public Array() {


this(10); // 默认 capacity 为 10


}


// 数组扩容/缩减


public void resize(int newCapacity) {


// 新数组长度必须大于 0


if (newCapacity < 0) throw new IllegalArgumentException("capacity must > 0!");


// 创建新数组


E[] newData = (E[]) new Object


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


[newCapacity];


// 将原数组元素放入新数组中


for (int i = 0; i < size; i++) {


newData[i] = data[i];


}


// 将引用指向新数组


data = newData;


}


/**


  • 在指定位置添加元素

  • 指定位置处的元素需要向右侧移动一个单位

  • @param index 索引

  • @param element 要添加的元素


*/


public void add(int index, E element) {


if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and <= size!");


// 数组满员触发扩容


if (size == data.length) {


resize(2 * data.length); // 扩容为原数组的 2 倍


}


// 从尾部开始,向右移动元素,直到 index


for (int i = size - 1; i >= index; i--) {


data[i + 1] = data[i];


}


// 添加元素


data[index] = element;


size++;


}


// 数组头部添加元素


public void addFirst(E element) {


add(0, element);


}


// 数组尾部添加元素


public void addLast(E element) {


add(size, element);


}


/**


  • 删除指定位置元素

  • 通过向左移动一位,覆盖指定位置处的元素,实现删除元素(data[size - 1] = null)

  • @param index 索引


*/


public E remove(int index) {


if (index < 0 || index > size) throw new IllegalArgumentException("Illegal index, index must > 0 and < size!");


// 数组长度为 0 时抛出异常


if (size == 0) throw new IllegalArgumentException("Empty array!");


E removedElement = data[index];


// 向左移动元素


for (int i = index; i < size - 1; i++) {


data[i] = data[i + 1];


}


// 将尾部空闲出的位置置为空,释放资源


data[size - 1] = null;


size--;


// size 过小触发数组缩减


if (size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2);


return removedElement;


}


// 删除头部元素


public E removeFirst() {


return remove(0);


}


// 删除尾部元素


public E removeLast() {


return remove(size - 1);


}


// 重写 Override 方法,自定义数组显示格式


@Override


public String toString() {


StringBuilder str = new StringBuilder();


// 显示数组的整体情况(长度、总容量)


str.append(String.format("Array: size = %d, capacity = %d\n[", size, data.length));


// 循环添加数组元素至 str


for (int i = 0; i < size; i++) {


str.append(data[i]);


if (i < size - 1) str.append(", ");


}


str.append("]");


return str.toString();


}


}


接下来我们测试一下这个数组的使用情况:


public static void main(String[] args) {


// 添加 10 个元素


Array<Integer> arr = new Array<>();


for (int i = 0; i < 10; i++)


arr.add(i, i);


// 查看数组当前状态


System.out.println(arr);


// 继续添加元素,观察是否扩容


arr.add(arr.size, 7);


System.out.println(arr);


// 再删除 6 个元素,观察是否缩减


for (int i = 0; i < 6; i++) {


System.out.println("元素" + arr.removeFirst() + "已被删除!");


}


System.out.println(arr);


}

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
算法入门 - 动态数组的实现(Java版本),分层架构图案例