数组结构与算法之动态数组

前言

前文我们提到过数组的一些缺点，包括无法扩容，封装性较差等，我们可以通过自定义一个动态数组来解决一下这些问题。
在java中早已有成熟的ArrayList可以供我们日常使用，或者线程安全的Vector等；C++中也有Vector。这是语言提高给我们已经封装好的动态数组。
但是，我们仍然应当了解其基本原理，动态数组其实不是一种很复杂的数据结构，它更像是数组的优化版本。
以下，是动态数组的java实现：

泛型支持

动态数组，作为被封装的工具类，应当是支持泛型的。

Java泛型（generics）是JDK 5中引入的一个新特性，泛型提供了编译时类型安全监测机制，该机制允许程序员在编译时监测非法的类型。使用泛型机制编写的程序代码要比那些杂乱地使用Object变量，然后再进行强制类型转换的代码具有更好的安全性和可读性。

我们这个动态数组，就取英译名DynamicArray：

/*** @program: thinking-in-all* @description:* @author: Lucifinil* @create: 2019-12-26**/
public class DynamicArray<T> {
}

属性

这里的动态数组是一个教为简单的实现，首先，因为它本质上是对数组的封装与扩展，其第一个属性为泛型数组：data，其次，动态数组支持动态扩容，其容量值为第二个属性：capacity；最后，我们应当有一个当前大小，来确定是否扩容：size，即：

    //被封装的数组private T[] data;//当前动态数组的元素数量private int size;//当前动态数组的容量private int capacity;

初始化

对于动态数组的初始化而言，支持直接传入capacity构造器，传入一个数组的构造器，或者无参构造，因为在动态数组初始化时，size始终应当为0，且data应当被初始化：
在java中，泛型数组无法通过这样的写法来初始化：

传入capacity的构造器

 data = new T[capacity];

正确的写法为通过泛型数组强转Object数组：

    public DynamicArray(int capacity) {this.capacity = capacity;data = (T[])new Object[capacity];size=0;}

传入数组的构造器

    public DynamicArray(T[] arr) {this.data =  (T[]) (new Object[arr.length]);for (int i = 0; i < arr.length; i++) {data[i] = arr[i];}size = arr.length;capacity=size+1;}

无参构造器
参考ArrayList，设置初始容量为10：

public DynamicArray() {this(10)

辅助函数

获取动态数组当前元素数量：

    public int size(){return size;}

获取动态数组当前是否非空：

    public boolean isEmpty(){return size==0;}

获取动态数组当前容量大小：

    public int capacity(){return capacity;}

元素的添加与扩容

上图，黑色代表原本存在的元素，灰色表示未使用的元素（int数组默认值为0），绿色表示新增值，红色表示迁移后的值。

扩容函数：

    private void grow(int capacity) {this.capacity = capacity;T[] newData = (T[])new Object[capacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;}

当data中插入一个元素后，如果其位置之后存在元素，也就是图中的3，4它会相应向后迁移；
插入元素前会进行检查，一旦data的容量被全部使用，data的大小会扩充为原来的1.5倍：

    public void add(int index, T e) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Add failed.Index is invalid.");}//如果当前元素数量已经等于容量值，扩容为原数组大小的1.5倍if (size == capacity) {grow(capacity + (capacity >> 1));}//对数据进行迁移for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}//赋值data[index] = e;//添加元素后 size应当加1size++;}

元素的删除与缩容

前文提到了当动态数组的实际使用已经到达容量值的时候，动态数组会进行扩容操作，那么，当动态数组的使用远远到达不了容量值的时候，动态数组应该进行缩容吗？
比如前文的数组，进行删除5的操作后：

上述图片中的自动缩容是与自动扩容相对的，也就是说一旦size等于capacity就会扩容，而一旦size等于capacity的2/3便会缩容，这会产生一个临界问题，那就是，如果我们经常在旧的扩容前的capacity大小的索引左右增删数据，那么动态数组便会不断地扩容缩容，如下图：

其实，除了这种自动缩容外，还有主动缩容的策略，如ArrayList中的trimToSize()：

    public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}

它是用户主动调用，来将其底层数组的大小缩容为当前size大小。

我们，这里选择自动扩容的优化版本，只有当size为capacity的一半时，才进行缩容，这样便不会产生临界震荡问题，其实，各种策略都可以，在不同的场景下各有优劣。

删除元素，且在删除元素后检查来决定是否缩容：

    public T remove(int index){//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Remove failed.Index is invalid.");}T oldValue = data[index];for (int i = index+1; i < size ; i++) {data[i - 1] = data[i];}size--;data[size] = null;//size为容量值的一半，且容量值的一半不为0，进行缩容if (size == this.capacity>>1 && this.capacity>>1!=0) {grow(this.capacity>>1);}return oldValue;}

元素的改查

其实，元素的修改与查询是直接对底层数组的修改与查询，由于工具类中data是私有的，故而应当暴露相应接口：
修改：

    public void set(int index, T e) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Set failed.Index is invalid.");}data[index] = e;}

查询：

    public T get(int index) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Get failed.Index is invalid.");}return data[index];}

完整代码

/*** @program: thinking-in-all* @description:* @author: Lucifinil* @create: 2019-12-26**/
public class DynamicArray<T> {//数组private T[] data;//当前动态数组的元素数量private int size;//当前动态数组的容量private int capacity;public DynamicArray(int capacity) {this.capacity = capacity;data = (T[]) new Object[capacity];size = 0;}public DynamicArray(T[] arr) {this.data = (T[]) (new Object[arr.length]);for (int i = 0; i < arr.length; i++) {data[i] = arr[i];}size = arr.length;capacity = size + 1;}public DynamicArray() {this(10);}public int size() {return size;}public boolean isEmpty() {return size == 0;}public int capacity() {return capacity;}//判断动态数组中是否包含epublic boolean contains(T e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return true;}}return false;}public void add(int index, T e) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Add failed.Index is invalid.");}//如果当前元素数量已经等于容量值，扩容为原数组大小的1.5倍if (size == capacity) {grow(capacity + (capacity >> 1));}//对数据进行迁移for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}//赋值data[index] = e;//添加元素后 size应当加1size++;}//给动态数组尾部添加元素public void addLast(T e) {add(size, e);}private void grow(int capacity) {this.capacity = capacity;T[] newData = (T[]) new Object[capacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;}public T remove(int index) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Remove failed.Index is invalid.");}T oldValue = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;data[size] = null;//size为容量值的一半，且容量值的一半不为0，进行缩容if (size == this.capacity >> 1 && this.capacity >> 1 != 0) {grow(this.capacity >> 1);}return oldValue;}public T removeLast() {return remove(size - 1);}public void set(int index, T e) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Set failed.Index is invalid.");}data[index] = e;}//给动态数组尾部修改元素public void setLast(T e) {set(size - 1, e);}public T get(int index) {//如果索引值非法，抛出索引越界异常if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Get failed.Index is invalid.");}return data[index];}//获取尾部元素public T getLast() {return get(size - 1);}@Overridepublic String toString() {StringBuilder str = new StringBuilder();str.append("[");for (int i = 0; i < size; i++) {str.append(data[i]);if (i != size - 1) {str.append(",");}}str.append("]");return str.toString();}
}

总结

这个工具类很多东西是没有考虑周全的，比如java中集合类都应implement的Iterable接口里的方法等等，一般来说，动态数组只需要包含上述基本方法就行了，理解到动态数组的思想才是最为重要的。
我是路西菲尔，如有错误，敬请指正，期待与你一同成长！
转载请注明出处，来自路西菲尔的博客https://blog.csdn.net/csdn_1364491554/article/details/103699256！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！