【Java ArrayList】底层方法的自我实现
我们来手写一个简易版的 ArrayList，通过自己实现核心方法，来真正理解 ArrayList 的底层原理。
目标是实现以下核心功能（尽量贴近 JDK 的 ArrayList 设计）：
- 动态扩容
- 添加元素（add）
- 指定位置添加（add(index, element)）
- 获取元素（get）
- 删除元素（remove）
- 修改元素（set）
- 查询大小（size）
- 判断是否包含（contains）
- 查找元素索引（indexOf）
简易版 ArrayList 完整实现
import java.util.Arrays;
/**
* 简易版 ArrayList 实现（仅供学习理解底层原理）
*/
public class MyArrayList<E> {
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组实例（用于无参构造时延迟分配）
private static final Object[] EMPTY_ELEMENTDATA = {};
// 实际存储元素的数组
private Object[] elementData;
// 当前元素个数
private int size;
/**
* 无参构造：默认容量 10，但真正分配在第一次添加元素时
*/
public MyArrayList() {
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* 指定初始容量构造
*/
public MyArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
/**
* 添加元素到末尾
*/
public boolean add(E e) {
// 检查容量，必要时扩容
ensureCapacityInternal(size + 1);
// 放入数组尾部
elementData[size++] = e;
return true;
}
/**
* 在指定位置插入元素
*/
public void add(int index, E element) {
// 检查索引合法性
rangeCheckForAdd(index);
// 确保容量够用（插入后 size+1）
ensureCapacityInternal(size + 1);
// 把 index 及后面的元素向后移动一位
System.arraycopy(elementData, index,
elementData, index + 1,
size - index);
// 放入新元素
elementData[index] = element;
size++;
}
/**
* 获取指定位置元素
*/
@SuppressWarnings("unchecked")
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
/**
* 修改指定位置元素，返回旧值
*/
@SuppressWarnings("unchecked")
public E set(int index, E element) {
rangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
/**
* 删除指定位置元素，返回被删除的元素
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
rangeCheck(index);
E oldValue = (E) elementData[index];
// 计算需要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0) {
// 向前移动覆盖被删除的位置
System.arraycopy(elementData, index + 1,
elementData, index,
numMoved);
}
// 最后一位置空，帮助 GC
elementData[--size] = null;
return oldValue;
}
/**
* 删除第一个匹配的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++) {
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}
} else {
for (int index = 0; index < size; index++) {
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
}
return false;
}
// 快速删除（内部使用，不做边界检查）
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null;
}
/**
* 是否包含某个元素
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 返回元素第一次出现的位置，没找到返回 -1
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 当前元素个数
*/
public int size() {
return size;
}
/**
* 是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 清空列表
*/
public void clear() {
// 帮助 GC
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
// ------------------- 内部工具方法 -------------------
/**
* 确保容量足够
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
// 第一次添加时，给默认容量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// 如果需要，扩容
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
/**
* 核心扩容逻辑
* 1.5 倍扩容（JDK 原版策略）
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果 1.5 倍还不够，直接用 minCapacity
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
// 防止溢出（理论上很少发生）
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
// 复制到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void rangeCheck(int index) {
if (index >= size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
// 方便调试
@Override
public String toString() {
if (size == 0) return "[]";
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(elementData[i]);
if (i < size - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
// 测试
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add(1, "X");
System.out.println(list); // [A, X, B, C]
System.out.println(list.get(2)); // B
System.out.println(list.remove(1)); // X
System.out.println(list); // [A, B, C]
System.out.println(list.contains("B")); // true
System.out.println(list.indexOf("C")); // 2
}
}核心要点总结（面试常问）
- 为什么用 Object[] 数组？
泛型擦除后，底层还是 Object[]，通过类型转换使用。 - 扩容策略为什么是 1.5 倍？
- 1.5 倍是时间与空间的折中（2 倍太浪费，1.2 倍扩容太频繁）
- 使用
oldCapacity + (oldCapacity >> 1)实现 1.5 倍（位运算更快）
- 为什么第一次添加时才分配默认容量 10？
延迟分配（lazy initialization），节省内存（new ArrayList() 但不 add 时不占空间） - System.arraycopy 为什么快？
native 方法，底层用 C 实现，批量内存复制效率很高 - 删除元素时为什么要把末尾置 null？
帮助 GC 回收不再引用的对象，避免内存泄漏 - 线程安全吗？
当前版本不安全（多线程 add/remove 会出现数据丢失、越界等）
进阶思考题（建议自己实现或回答）
- 如何实现线程安全的 ArrayList？（CopyOnWriteArrayList 思路）
- 如何实现 fail-fast 机制？（modCount）
- 如何实现 trimToSize() 功能？
- 如何实现 subList()？
- 如何实现 toArray() 的泛型版本？
如果你想继续深入某个方法（比如扩容、删除、subList、迭代器等），或者想加上 fail-fast 机制、泛型优化、迭代器 等功能，告诉我，我可以继续帮你完善！
