引言

算法和数据结构可以说是程序的核心，不仅是程序高效运行的基础，而且对于解决复杂问题至关重要。ArrayList因其灵活性和高效性在Java编程中占有重要地位。它是一个基于数组实现的动态大小的列表，能够根据需要自动扩展和收缩

在这篇文章中，我们将尝试从头开始实现一个类似于Java标准库（JDK）中ArrayList的数据结构。这个自定义的MyArrayList类将支持泛型，并提供动态数组的核心功能。通过这个过程，我们能更好地理解ArrayList的内部工作原理

目录

• 概述
• JDK ArrayList的实现原理
• JDK ArrayList关键特性
• JDK ArrayList类图概览
• 基本实现
• 创新方法，拓展JDK源码
• 写在最后

JDK ArrayList 的实现原理

在深入到我们自己的ArrayList实现之前，让我们先快速了解一下Java标准库中ArrayList的工作原理。

Java中的ArrayList是基于数组实现的动态列表。它通过一个内部数组来存储元素，当这个数组的容量不足以容纳更多元素时，ArrayList会创建一个新的更大的数组，并将旧数组中的元素复制到新数组中。这个过程被称为“动态扩容”

JDK ArrayList关键特性：

• 动态数组：ArrayList使用数组作为其内部数据结构，但与普通数组不同的是，可以动态地扩容
• 随机访问：由于基于数组，ArrayList支持快速的随机访问，即可以在O(1)时间访问任何位置的元素
• 自动扩容机制：当添加元素到ArrayList时，如果内部数组已满，ArrayList会自动创建一个更大的数组，并将所有元素复制到新数组中

JDK ArrayList 类图概览：

下面的类图简单展示了ArrayList的结构：

下文我们将手撕这些方法，并扩展一些jdk没有的方法

基本实现

定义类和构造函数

/*** 自定义的ArrayList实现，支持泛型* * @param <T> ArrayList中存储的元素类型*/
public class MyArrayList<T> {// 用于存储元素的数组private T[] array;  // 实际存储的元素数量private int size;  /*** 构造一个初始容量为10的空MyArrayList*/public MyArrayList() {// 初始容量设为10array = (T[]) new Object[10]; // 初始时，数组中没有元素size = 0;                     }
}

添加元素

/*** 向MyArrayList中添加一个新元素* 如果内部数组已满，则会触发自动扩容** @param element 要添加的元素*/
public void add(T element) {// 检查是否需要扩容。if (size == array.length) {resize();}// 在数组的下一个可用位置添加元素，并递增sizearray[size++] = element;
}/*** 扩容* 当数组无法容纳更多元素时，调用此方法将数组容量增加一倍*/
private void resize() {// 创建一个容量是当前数组两倍的新数组T[] newArray = (T[]) new Object[array.length * 2];// 将旧数组的内容复制到新数组System.arraycopy(array, 0, newArray, 0, array.length);// 更新内部数组引用到新数组array = newArray;
}

添加集合

/**
* 添加一个集合中的所有元素到MyArrayList
*
* @param c 要添加的元素集合
* @return 如果MyArrayList由于调用而改变，则返回true
*/
public boolean addAll(Collection<? extends T> c) {boolean modified = false;for (T element : c) {add(element);modified = true;}return modified;
}

获取元素

/*** 获取MyArrayList中指定索引处的元素** @param index 要获取元素的索引* @return 在指定索引处的元素* @throws IndexOutOfBoundsException 如果索引超出数组的当前大小范围*/
public T get(int index) {// 检查索引是否在有效范围内if (index >= size || index < 0) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}// 返回指定索引处的元素return array[index];
}

删除元素

/*** 从MyArrayList中移除指定索引处的元素** @param index 要移除元素的索引* @return 被移除的元素* @throws IndexOutOfBoundsException 如果索引超出数组的当前大小范围*/
public T remove(int index) {// 使用get方法获取元素同时检查索引有效性T element = get(index);// 将指定索引之后的元素向前移动一个位置for (int i = index; i < size - 1; i++) {array[i] = array[i + 1];}// 释放最后一个元素并减小sizearray[--size] = null;// 返回被移除的元素return element;
}

contains 方法

/*** 检查ArrayList是否包含特定元素* @param element 要检查的元素* @return 如果找到了元素，返回true，否则返回false*/
public boolean contains(T element) {for (int i = 0; i < size; i++) {if ((element == null && array[i] == null) ||(element != null && element.equals(array[i]))) {return true;}}return false;
}

size 方法

/*** 返回MyArrayList中的元素数量** @return 当前存储的元素数量*/
public int size() {return size;
}

clear方法

/*** 清空MyArrayList，移除所有元素*/
public void clear() {// 遍历数组，将每个元素设置为nullfor (int i = 0; i < size; i++) {array[i] = null;}// 重置元素数量为0size = 0;
}

isEmpty 方法

/*** 检查MyArrayList是否为空** @return 如果列表没有元素则返回true，否则返回false*/
public boolean isEmpty() {return size == 0;
}

isNotEmpty 方法

/*** 检查MyArrayList是否不为空** @return 如果列表有元素则返回true，否则返回false*/
public boolean isNotEmpty() {return size > 0;
}

indexOf 方法

/*** 查找元素在MyArrayList中的索引** @param element 要查找的元素* @return 如果找到元素，则返回其索引；否则返回-1*/
public int indexOf(T element) {// 遍历数组，寻找匹配的元素for (int i = 0; i < size; i++) {if (element.equals(array[i])) {// 返回找到的元素的索引return i;  }}// 如果没有找到元素，返回-1return -1; 
}

lastIndexOf 方法

/*** 查找元素在MyArrayList中最后一次出现的索引** @param element 要查找的元素* @return 如果找到元素，则返回其最后一次出现的索引；否则返回-1*/
public int lastIndexOf(T element) {// 从数组的末尾开始向前遍历for (int i = size - 1; i >= 0; i--) {// 元素找到时返回当前索引if (element.equals(array[i])) {return i;}}// 未找到元素return -1;
}

removeRange 方法

public void removeRange(int fromIndex, int toIndex) {// 检查索引范围的有效性if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) {throw new IndexOutOfBoundsException();}// 计算需要移动的元素数量int numMoved = size - toIndex;// 将toIndex之后的元素向前移动，覆盖掉要移除的部分System.arraycopy(array, toIndex, array, fromIndex, numMoved);// 计算新的大小int newSize = size - (toIndex - fromIndex);// 将末尾多余的元素置为nullfor (int i = newSize; i < size; i++) {array[i] = null;}// 更新sizesize = newSize;
}

subList 方法

/*** 获取MyArrayList中指定范围内元素的子列表** @param fromIndex 子列表的起始索引（包含）* @param toIndex 子列表的终止索引（不包含）* @return 指定范围内的元素构成的子列表* @throws IndexOutOfBoundsException 如果索引范围不合法*/
public MyArrayList<T> subList(int fromIndex, int toIndex) {// 检查索引范围的有效性if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) {throw new IndexOutOfBoundsException();}// 创建新的MyArrayList作为子列表MyArrayList<T> sub = new MyArrayList<>();// 将指定范围内的元素添加到子列表中for (int i = fromIndex; i < toIndex; i++) {sub.add(array[i]);}// 返回子列表return sub;
}

replace 方法

/*** 替换MyArrayList中指定索引处的元素，并返回原来的元素** @param index 要替换元素的索引* @param element 新元素* @return 原来在指定索引处的元素* @throws IndexOutOfBoundsException 如果索引超出数组的当前大小范围*/
public T replace(int index, T element) {// 使用get方法获取当前索引处的元素，同时检查索引有效性T oldElement = get(index);// 将新元素设置到指定索引处array[index] = element;// 返回被替换的旧元素return oldElement;
}

sort默认自然排序

/**
* 根据元素的自然顺序对MyArrayList进行排序
*/
public void sort() {// 将MyArrayList转换为数组Object[] a = this.toArray();// 使用Arrays.sort方法进行排序，没有提供Comparator，将使用元素的自然顺序Arrays.sort(a);// 更新MyArrayList的内部数组System.arraycopy(a, 0, array, 0, size);
}

sort指定比较器排序

/**
* 根据指定比较器对MyArrayList进行排序
*
* @param comp 用于元素比较的Comparator
*/
public void sort(Comparator<? super T> comp) {// 将MyArrayList转换为数组Object[] a = this.toArray();// 使用Arrays.sort方法进行排序Arrays.sort(a, (Comparator) comp);// 更新MyArrayList的内部数组System.arraycopy(a, 0, array, 0, size);
}

创新方法，拓展JDK源码

批量添加元素

public void batchAdd(T... elements) {for (T element : elements) {add(element);}
}

翻转列表

public void reverse() {for (int i = 0; i < size / 2; i++) {T temp = array[i];array[i] = array[size - 1 - i];array[size - 1 - i] = temp;}
}

随机打乱列表

随机打乱列表中的元素顺序

public void shuffle() {Random rnd = new Random();for (int i = size; i > 1; i--) {swap(i - 1, rnd.nextInt(i));}
}private void swap(int i, int j) {T temp = array[i];array[i] = array[j];array[j] = temp;
}

查找最大/最小元素

假设元素实现了Comparable接口，可以找到最大或最小的元素

public T findMax() {if (isEmpty()) {return null;}T max = array[0];for (int i = 1; i < size; i++) {if (max.compareTo(array[i]) < 0) {max = array[i];}}return max;
}public T findMin() {if (isEmpty()) {return null;}T min = array[0];for (int i = 1; i < size; i++) {if (min.compareTo(array[i]) > 0) {min = array[i];}}return min;
}

去除重复元素

public void removeDuplicates() {HashSet<T> set = new HashSet<>();int writePointer = 0;for (int readPointer = 0; readPointer < size; readPointer++) {if (set.add(array[readPointer])) {array[writePointer++] = array[readPointer];}}for (int i = writePointer; i < size; i++) {array[i] = null;}size = writePointer;
}

交集

/*** 计算当前MyArrayList与另一个MyArrayList的交集** @param otherList 要比较的另一个MyArrayList* @return 两个列表共有元素组成的新MyArrayList*/
public MyArrayList<T> intersection(MyArrayList<T> otherList) {MyArrayList<T> result = new MyArrayList<>();// 遍历当前列表的每个元素for (T item : this.array) {// 如果另一个列表也包含这个元素，则添加到结果列表中if (otherList.contains(item)) {result.add(item);}}return result;
}

并集

/*** 计算当前MyArrayList与另一个MyArrayList的并集** @param otherList 要比较的另一个MyArrayList* @return 两个列表所有元素（不包括重复）组成的新MyArrayList*/
public MyArrayList<T> union(MyArrayList<T> otherList) {MyArrayList<T> result = new MyArrayList<>();// 将当前列表的元素添加到结果列表中for (T item : this.array) {result.add(item);}// 将另一个列表中不重复的元素添加到结果列表中for (T item : otherList.array) {if (!result.contains(item)) {result.add(item);}}return result;
}

差集

/*** 计算当前MyArrayList与另一个MyArrayList的差集** @param otherList 要比较的另一个MyArrayList* @return 存在于当前列表但不在另一个列表中的元素组成的新MyArrayList*/
public MyArrayList<T> difference(MyArrayList<T> otherList) {MyArrayList<T> result = new MyArrayList<>();// 遍历当前列表的每个元素for (T item : this.array) {// 如果另一个列表不包含这个元素，则添加到结果列表中if (!otherList.contains(item)) {result.add(item);}}return result;
}

MyArrayList类图

可以看到我们基本上实现了jdk所有的方法，并且拓展了很多JDK并不支持的方法

写在最后

通过这篇文章，探索了如何从零开始构建一个高效的ArrayList。希望在这个过程中你不仅学到了如何实现这个强大的数据结构，而且也对Java ArrayList操作有了更深刻的理解

编程其实不仅仅是关于写代码，更是关于理解背后的原理，这样我们才能写出更高效、更可靠的代码。希望这篇文章能够激发你们对深入学习Java以及算法数据结构的决心

如果喜欢这篇文章，记得点赞和关注。你的支持是我不断创作和分享的动力！同时，如果你有任何问题或想法，欢迎在评论区留言，让我们一起讨论和成长。

感兴趣的读者也可以看看往期我写的文章：

java实现十大经典排序算法【GIF动画+完整代码+详细注释
Java设计模式实战：从If-Else到策略+工厂方法的演变
Java并发编程深度解析：掌握CompletableFuture的高效异步模式
Lambda表达式深度解析：提升代码效率与可读性
https://blog.csdn.net/weixin_38522648/article/details/135186933
一文搞懂JAVA单例设计模式的所有实现
Redis缓存八大模式，项目应用选型？这篇文章就够了
Redis缓存的八大模式，项目应用如何选型？这篇文章就够了
git的工作原理，实战案例，这篇文章就够了
深入剖析事务ACID实现的底层原理

• 程序员三毛