扩展JDK源码：Java手撕ArrayList【超详细注释】

引言

算法和数据结构可以说是程序的核心，不仅是程序高效运行的基础，而且对于解决复杂问题至关重要。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() {
        // 初始容量设为10
        array = (T[]) new Object[10]; 
        // 初始时，数组中没有元素
        size = 0;                     
    }
}

添加元素

/**
 * 向MyArrayList中添加一个新元素
 * 如果内部数组已满，则会触发自动扩容
 *
 * @param element 要添加的元素
 */
public void add(T element) {
    // 检查是否需要扩容。
    if (size == array.length) {
        resize();
    }
    // 在数组的下一个可用位置添加元素，并递增size
    array[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];
    }

    // 释放最后一个元素并减小size
    array[--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() {
    // 遍历数组，将每个元素设置为null
    for (int i = 0; i < size; i++) {
        array[i] = null;
    }
    // 重置元素数量为0
    size = 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;  
        }
    }
    // 如果没有找到元素，返回-1
    return -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);
    // 将末尾多余的元素置为null
    for (int i = newSize; i < size; i++) {
        array[i] = null;
    }
    // 更新size
    size = 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实现的底层原理

• 程序员三毛