Java如何实现自定义ArrayList类

目录

1. 引言
2. ArrayList的基本概念
3. 自定义ArrayList类的设计
4. 实现自定义ArrayList类
   • 4.1 定义类结构
   • 4.2 实现构造函数
   • 4.3 实现add方法
   • 4.4 实现get方法
   • 4.5 实现remove方法
   • 4.6 实现size方法
   • 4.7 实现扩容机制
   • 4.8 实现toString方法
5. 测试自定义ArrayList类
6. 总结

引言

在Java编程中，ArrayList是一个非常常用的数据结构，它提供了动态数组的功能，可以根据需要自动调整大小。虽然Java标准库中已经提供了ArrayList的实现，但通过自己实现一个自定义的ArrayList类，可以帮助我们更好地理解其内部工作原理，并提升我们的编程能力。

本文将详细介绍如何从零开始实现一个自定义的ArrayList类，涵盖从基本设计到具体实现的各个方面。

ArrayList的基本概念

ArrayList是Java集合框架中的一部分，它基于动态数组实现。与普通数组不同，ArrayList可以根据需要自动扩展其容量，从而避免了手动管理数组大小的麻烦。ArrayList的主要特点包括：

• 动态扩容：当元素数量超过当前容量时，ArrayList会自动增加其容量。
• 随机访问：由于基于数组实现，ArrayList支持通过索引快速访问元素。
• 顺序存储：元素在ArrayList中是按照插入顺序存储的。

自定义ArrayList类的设计

在实现自定义ArrayList类之前，我们需要明确其基本功能和结构。一个简单的ArrayList类应该至少包含以下功能：

• 添加元素：支持在列表末尾添加元素。
• 获取元素：支持通过索引获取元素。
• 删除元素：支持通过索引删除元素。
• 获取列表大小：返回列表中元素的数量。
• 动态扩容：当列表容量不足时，自动扩展容量。

为了实现这些功能，我们需要定义一个类，并在其中维护一个数组来存储元素。此外，我们还需要记录当前列表的大小和容量。

实现自定义ArrayList类

4.1 定义类结构

首先，我们定义一个名为CustomArrayList的类，并在其中声明必要的成员变量：

public class CustomArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
    private Object[] elements; // 存储元素的数组
    private int size; // 当前列表大小

    // 构造函数
    public CustomArrayList() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }
}

在这个类中，我们使用了一个Object类型的数组elements来存储元素。由于Java的泛型在运行时会被擦除，因此我们使用Object数组来存储任意类型的元素。size变量用于记录当前列表中元素的数量。

4.2 实现构造函数

我们已经在类中定义了一个无参构造函数，它将数组的初始容量设置为DEFAULT_CAPACITY（默认为10）。此外，我们还可以提供一个带有初始容量参数的构造函数，以便用户可以根据需要指定初始容量：

public CustomArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        elements = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        elements = new Object[DEFAULT_CAPACITY];
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
    size = 0;
}

4.3 实现add方法

add方法用于在列表末尾添加元素。如果当前数组已满，我们需要先扩展数组的容量，然后再添加元素。以下是add方法的实现：

public void add(E element) {
    if (size == elements.length) {
        ensureCapacity(size + 1); // 确保容量足够
    }
    elements[size++] = element;
}

在这个方法中，我们首先检查当前数组是否已满。如果已满，则调用ensureCapacity方法扩展数组容量。然后，我们将新元素添加到数组的末尾，并增加size的值。

4.4 实现get方法

get方法用于通过索引获取元素。我们需要确保索引在有效范围内，然后返回对应位置的元素：

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    return (E) elements[index];
}

在这个方法中，我们首先检查索引是否有效。如果索引超出范围，则抛出IndexOutOfBoundsException异常。否则，我们返回对应位置的元素，并将其强制转换为泛型类型E。

4.5 实现remove方法

remove方法用于通过索引删除元素。删除元素后，我们需要将后续元素向前移动，以填补删除后的空缺：

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    E removedElement = (E) elements[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(elements, index + 1, elements, index, numMoved);
    }
    elements[--size] = null; // 清除最后一个元素的引用
    return removedElement;
}

在这个方法中，我们首先检查索引是否有效。然后，我们获取要删除的元素，并将后续元素向前移动。最后，我们将最后一个元素的引用设置为null，并减少size的值。

4.6 实现size方法

size方法用于返回当前列表中元素的数量：

public int size() {
    return size;
}

这个方法非常简单，直接返回size变量的值即可。

4.7 实现扩容机制

当列表容量不足时，我们需要扩展数组的容量。通常，我们会将数组的容量扩展为当前容量的1.5倍。以下是ensureCapacity方法的实现：

private void ensureCapacity(int minCapacity) {
    int oldCapacity = elements.length;
    if (minCapacity > oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        elements = Arrays.copyOf(elements, newCapacity);
    }
}

在这个方法中，我们首先计算新的容量。如果新容量仍然小于所需的最小容量，则将新容量设置为最小容量。然后，我们使用Arrays.copyOf方法将旧数组复制到新数组中。

4.8 实现toString方法

为了方便调试和输出，我们可以重写toString方法，使其返回列表中所有元素的字符串表示：

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (int i = 0; i < size; i++) {
        sb.append(elements[i]);
        if (i < size - 1) {
            sb.append(", ");
        }
    }
    sb.append(']');
    return sb.toString();
}

在这个方法中，我们使用StringBuilder来构建字符串表示。我们遍历数组中的元素，并将它们添加到StringBuilder中，最后返回构建好的字符串。

测试自定义ArrayList类

为了验证我们的自定义ArrayList类的正确性，我们可以编写一些测试代码：

public class CustomArrayListTest {
    public static void main(String[] args) {
        CustomArrayList<String> list = new CustomArrayList<>();

        // 添加元素
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 输出列表
        System.out.println("List: " + list);

        // 获取元素
        System.out.println("Element at index 1: " + list.get(1));

        // 删除元素
        list.remove(1);
        System.out.println("List after removing element at index 1: " + list);

        // 获取列表大小
        System.out.println("Size of list: " + list.size());
    }
}

运行这个测试代码，我们可以看到以下输出：

List: [Apple, Banana, Cherry]
Element at index 1: Banana
List after removing element at index 1: [Apple, Cherry]
Size of list: 2

这个输出表明我们的自定义ArrayList类能够正确地添加、获取、删除元素，并且能够正确地返回列表的大小。

总结

通过本文的介绍，我们详细讲解了如何从零开始实现一个自定义的ArrayList类。我们从基本概念出发，逐步实现了添加、获取、删除元素等功能，并实现了动态扩容机制。最后，我们通过测试代码验证了自定义ArrayList类的正确性。

通过自己实现ArrayList类，我们不仅加深了对Java集合框架的理解，还提升了编程能力。希望本文能够帮助你更好地掌握Java中的动态数组实现，并为你的编程学习提供有价值的参考。