数据结构基础之动态数组

目录

前言

1、Java中的数组

2、实现动态数组

2.1、基本类结构设计

2.2、添加元素

2.3、查询&修改元素

2.4、包含&搜索&删除

2.5、数组扩容

---

前言

今天我们来学习一下关于数据结构的一些基础知识，数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以更高效的获取数据或者修改数据，那么首先我们要说的就是数组。

1、Java中的数组

数组就是把数据放成一排进行存放

通过一段代码来回忆一下数组的具体使用吧：

数组最大的优点就是：快速查询（比如ages[2]）。

思考：数组的大小在创建的时候就已经固定了，那么如果我们往数组里添加的元素个数超过了数组的最大容量时，该怎么办呢？

2、实现动态数组

基于上面的思考，我们就来基于Java为我们提供的数组，一步一步的实现一个动态数组，可以满足增删改查的需求，并且当元素个数超过数组容量时，可以自动扩容。

2.1、基本类结构设计

public class Array {private int[] data;private int size;/*** 构造函数，传入的是数组的容量** @param capacity 容量*/public Array(int capacity) {data = new int[capacity];size = 0;}// 无参构造，默认容量为10public Array() {this(10);}// 获取数组中的元素个数public int getSize() {return size;}// 获取数组的容量public int getCapacity() {return data.length;}//判断数组是否为空public boolean isEmpty() {return size == 0;}
}

2.2、添加元素

思想：向数组末尾添加元素

2.3、查询&修改元素

2.4、包含&搜索&删除

经过上面这些步骤，数组中的相关方法都已经添加好了，最后我们再把这个Array类修改为泛型类Array<Element>，让它可以添加各种数据类型的元素，这里我就不再一一修改了，后面会附上完整的代码。

接下来我们来简单测试一下我们的Array类是否可用：

执行结果如下：

2.5、数组扩容

对于扩容也很简单，就是当数组中的容量不够存储时，重新创建一个更大容量的数组，然后将原数组的数据一一更新到新数组中，当然，具体扩容成多少就由开发者自行决定了，下面来看代码：

然后我们来实际测试一下是否扩容成功：

从执行的结果中可以很明显的看出，我们的动态数组已经成功实现了扩容：

最后附上完整的Array.java类的源码吧：

public class Array<E> {private E[] data;private int size;/*** 构造函数，传入的是数组的容量** @param capacity 容量*/public Array(int capacity) {data = (E[]) new Object[capacity];size = 0;}// 无参构造，默认容量为10public Array() {this(10);}// 获取数组中的元素个数public int getSize() {return size;}// 获取数组的容量public int getCapacity() {return data.length;}//判断数组是否为空public boolean isEmpty() {return size == 0;}// 向所有元素后添加一个新元素public void addLast(E e) {add(size, e);}// 向所有元素前添加一个新元素public void addFirst(E e) {add(0, e);}// 向第index位置插入一个新元素public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("数组下标异常");}if (size == data.length) {resize(2 * data.length);}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;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;}// 获取index索引位置的元素public E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("数组下标异常");}return data[index];}//修改index索引位置的元素public void set(int index, E e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("数组下标异常");}data[index] = e;}// 查找数组中是否有元素epublic boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return true;}}return false;}// 查找数组中元素e所在的索引，如果没有则返回-1public int findIndex(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return i;}}return -1;}// 从数组中删除index位置的元素，并且返回删除的元素public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("数组下标异常");}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;if (size == data.length / 4 && data.length / 2 != 0) {resize(data.length / 2);}return ret;}// 从数组中删除第一个元素public E removeFirst() {return remove(0);}// 从数组中删除最后一个元素public E removeLast() {return remove(size - 1);}// 从数组中删除元素epublic void removeElement(E e) {int index = findIndex(e);if (index != -1) {remove(index);}}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append(String.format("Array:size=%d,capacity=%d\n", size, data.length)).append("[");for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(",");}}res.append("]");return res.toString();}
}

 OK，关于动态数组的相关内容就说这么多吧，下期再会！

祝：工作顺利！