目录
前言
1、Java中的数组
2、实现动态数组
2.1、基本类结构设计
2.2、添加元素
2.3、查询&修改元素
2.4、包含&搜索&删除
2.5、数组扩容
今天我们来学习一下关于数据结构的一些基础知识，数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以更高效的获取数据或者修改数据，那么首先我们要说的就是数组。
数组就是把数据放成一排进行存放
通过一段代码来回忆一下数组的具体使用吧：
数组最大的优点就是：快速查询（比如ages[2]）。
思考：数组的大小在创建的时候就已经固定了，那么如果我们往数组里添加的元素个数超过了数组的最大容量时，该怎么办呢？
基于上面的思考，我们就来基于Java为我们提供的数组，一步一步的实现一个动态数组，可以满足增删改查的需求，并且当元素个数超过数组容量时，可以自动扩容。
public class Array {
private int[] data;
private int size;
/**
* 构造函数，传入的是数组的容量
*
* @param capacity 容量
*/
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
// 无参构造，默认容量为10
public Array() {
this(10);
}
// 获取数组中的元素个数
public int getSize() {
return size;
}
// 获取数组的容量
public int getCapacity() {
return data.length;
}
//判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
}思想：向数组末尾添加元素
经过上面这些步骤，数组中的相关方法都已经添加好了，最后我们再把这个Array类修改为泛型类Array<Element>，让它可以添加各种数据类型的元素，这里我就不再一一修改了，后面会附上完整的代码。
接下来我们来简单测试一下我们的Array类是否可用：
执行结果如下：
对于扩容也很简单，就是当数组中的容量不够存储时，重新创建一个更大容量的数组，然后将原数组的数据一一更新到新数组中，当然，具体扩容成多少就由开发者自行决定了，下面来看代码：
然后我们来实际测试一下是否扩容成功：
从执行的结果中可以很明显的看出，我们的动态数组已经成功实现了扩容：
最后附上完整的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;
}
// 无参构造，默认容量为10
public 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;
}
// 查找数组中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果没有则返回-1
public 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);
}
// 从数组中删除元素e
public void removeElement(E e) {
int index = findIndex(e);
if (index != -1) {
remove(index);
}
}
@Override
public 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，关于动态数组的相关内容就说这么多吧，下期再会！
祝：工作顺利！