Java教程
数据结构与算法-基础（一）动态数组
摘要
日常开发中，会经常创建数组，并使用数组的添加、删除等方法。现在就是要以数据结构的方式，来探究一下这些方法是怎么实现的。
本文结构先总结 Array 常用的 API，接下来由简单到复杂，由基础到组合思路实现，最后优化细节。你可以按照文章的顺序来梳理思路，去实现一下。
在文章的最后有完整的代码实现，你可以实现完了作为参考对照，或者不想看太多文字，直接跳到代码，自己去看代码理解也是可以的。
动态数组通俗些说就是可以无限的添加元素，不用考虑数组装不下的问题。其本质就是时刻监控数组中的剩余空间，及时的扩容和缩容，让数组动态的保持适当的容量大小。
数组的数据结构和对外的 API 函数，是在常见的基础上建立的，其中穿插着一些恰到好处的代码处理。不同的代码语言有不同的实现，但是数据结构是经历了几十年的检视，设计逻辑是可以套用到大部分代码语言上的。
Array 的常用 API
先来总结一下，日常使用 Array 的 API 大都逃不过下面代码块中罗列出的 11 个方法。
代码中的 E 就是泛型类型
/** * 清除所有元素 */ public void clear() /** * 元素的数量 * @return */ public int size() /** * 是否为空 * @return */ public boolean isEmpty() /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element) /** * 添加元素到尾部 * @param element */ public void add(E element) /** * 获取index位置的元素 * @param index * @return */ public E get(int index) /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素ֵ */ public E set(int index, E element) /** * 在index位置插入一个元素 * @param index * @param element */ public void add(int index, E element) /** * 删除index位置的元素 * @param index * @return */ public E remove(int index) /** * 删除元素 * @param element */ public void remove(E element) /** * 查看元素的索引 * @param element * @return */ public int indexOf(E element)
数据结构
Array 的数据结构中主要包括构造函数、存放元素的成员变量、记录元素数量的成员变量等。
public class ArrayList<E> {
/**
* 默认数组大小
*/
private static final int DEFAULT_CAPATICY = 10;
/**
* 默认标示
*/
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 所有元素
*/
private E[] elements;
/**
* 元素数量
*/
private int size = 0;
/**
* 初始化数组
*/
public ArrayList(int capaticy) {
elements = (E[]) new Object[capaticy];
}
/**
* 初始化数组（无参）
*/
public ArrayList() {
this(DEFAULT_CAPATICY);
}
}
如果看到定义的属性中，竟然还定义了一个elements数组属性，就发出“？”。
这里就简单说一下元素在内存中的如何存放，看构造函数中用 new 创建数组，本质就是在堆空间申请了一个连续的空间准备存放数组，elements 中每个 index 是指向内存空间的指针（和 C++ 中的内存空间不同）。
为什么要申请堆空间来存放数据？
在内存管理中，有栈空间和堆空间可以存放一些临时创建的数据，区别就是栈空间的创建和释放是系统管理的，但是堆空间就可以开发人员自己管理。咱们创建的数组，肯定不希望自己无法控制，所以堆空间是最好的选择。
那么为什么 new 就是申请堆空间？这是代码特性，没有什么道理的规定
实现方法
实现方法的思路是从简单到复杂
看 Array 中定义的属性，有元素数量size，size是记录数组中已经存在的元素数量，那么就可以先快速实现元素的数量和是否为空两个方法
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
因为元素是存放在 elements 这个数组中的，所以删除元素的方法就可以通过遍历方式快速实现
/**
* 清除所有元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
获取 index 位置上的元素方法，可以使用数组索引的方法实现
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index) {
return elements[index];
}
设置 index 位置的元素方法，也可以直接在elements数组上直接操作。
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
public E set(int index, E element) {
E oldElement = elements[index];
elements[index] = element;
return oldElement;
}
添加元素
简单的方法实现完了，接下来就实现复杂的方法。那么在复杂的方法中首先实现基础的方法。
那么现在首要实现的方法是add(int index, E element)(在 index 位置插入一个元素)。为什么要首要实现呢？这个问题咱先放放，先实现
当在 index 位置插入元素时，index 位置的元素开始都要往后移动一个位置，然后把这个元素放到 index 位置。不要忘记把记录已经存放元素数量的size加 1 操作。
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index] = element;
size++;
}
接下来在这个方法基础上实现add(E element)(添加元素到尾部)，就是在 size 位置上插入一个元素。这就是首要实现在 index 位置插入一个元素的原因。
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
查看元素
循着添加元素的实现逻辑，首要实现indexOf(E element)（查看元素的索引）方法。该方法需要分 element 不为 null 和为 null 两种情况处理。若 element 为 null，那么就没法进行比较
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
return i;
}
}
}
else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND; // 常量：-1，数组中没有该元素
}
在这基础上，可以实现contains(E element)（是否包含某个元素）。方法中直接判断 element 元素的 index 是否等于 -1 来判断返回。
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
删除元素
继续首要实现基础方法思路，先实现remove(int index)（删除 index 位置的元素）方法。
数组从 index 位置到尾部遍历，后面的元素不断覆盖前面的元素。然后把最后一个元素设置为 null。size 的大小也要减 1.
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index) {
rangeCheck(index);
E oldElement = elements[index];
for (int i = index; i < size; i++) {
elements[i] = elements[i+1];
}
size --;
elements[size] = null;
return oldElement;
}
接下来实现remove(E element)（删除元素）方法。它就可以先获取 element 元素的 index，然后再删除 index 位置的元素。通过这两个方法实现。
/**
* 删除元素
* @param element
*/
public void remove(E element) {
remove(indexOf(element));
}
数组越界
截止到现在，动态数组的11个方法已经实现完了。畅快淋漓之后，要开始补补漏洞。
使用数组的方法，不怕元素不存在，就要坐标越界，所以就需要在传入 index 参数的方法中先要判断一下是否越界，如果越界，就不能再进行下面的代码实现。
/**
* 判断坐标是否越界
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBound(index);
}
}
private void outOfBound(int index) {
throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}
但是添加元素到尾部的时候，是把元素放到 size 的位置，那么就需要排除 index == size 的判断。
private void rangeCheckOfAdd(int index) {
if (index < 0 || index > size) {
outOfBound(index);
}
}
扩容
补了数组越界的洞之后，但是 elements 开始设置容量是 10 个元素，如果添加元素时，超过 elements 的容量时，就需要进行扩容操作。
执行扩容方法时，先要判断容量是否够用，不够用时，就创建一个1.5倍之前 elements 容量的新数组，然后遍历老数组元素放置到新的数组中。
/**
* 扩容
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity <= oldCapacity) {
return;
}
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩大 1.5 倍
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
相对的，需要进行缩容吗？如何实现缩容？这两个问题可以根据实际情况来进行，思路和扩容是相似的。
整体实现
动态数组已经完美实现了。接下来就完整的贴一下代码，整体的看一下代码实现，再品味品味动态数组的实现逻辑。
@SuppressWarnings({"unused","unchecked"})
public class ArrayList<E> {
/**
* 默认数组大小
*/
private static final int DEFAULT_CAPATICY = 10;
/**
* 默认标示
*/
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 所有元素
*/
private E[] elements;
/**
* 元素数量
*/
private int size = 0;
/**
* 初始化数组
*/
public ArrayList(int capaticy) {
// 忘记
capaticy = (capaticy < DEFAULT_CAPATICY ? DEFAULT_CAPATICY: capaticy);
elements = (E[]) new Object[capaticy];
}
/**
* 初始化数组（无参）
*/
public ArrayList() {
this(DEFAULT_CAPATICY);
}
/**
* 清除所有元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
public E set(int index, E element) {
rangeCheck(index);
E oldElement = elements[index];
elements[index] = element;
return oldElement;
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
rangeCheckOfAdd(index);
ensureCapacity(size+1);
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index] = element;
size++;
}
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index) {
rangeCheck(index);
E oldElement = elements[index];
for (int i = index; i < size; i++) {
elements[i] = elements[i+1];
}
size --;
elements[size] = null;
return oldElement;
}
/**
* 删除元素
* @param element
*/
public void remove(E element) {
remove(indexOf(element));
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
return i;
}
}
}
else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 扩容
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (capacity <= oldCapacity) {
return;
}
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩大 1.5 倍
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private void outOfBound(int index) {
throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}
/**
* 判断坐标是否越界
* @param index
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBound(index);
}
}
private void rangeCheckOfAdd(int index) {
if (index < 0 || index > size) {
outOfBound(index);
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("size:").append(size).append(" ").append("[");
for (int i = 0; i < size; i++) {
if (i != 0) {
stringBuilder.append(",");
}
stringBuilder.append(elements[i]);
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
-
Java项目开发入门：新手必读指南11-23
-
Java语音识别项目入门教程11-23
-
Java语音识别项目入门教程11-23
-
Java云原生入门11-23
-
Java云原生入门：从零开始构建云原生Java应用11-23
-
Java云原生入门：简单教程助你轻松上手11-23
