实现一个类似ArrayList的数据结构,可以帮助我们更深入地理解动态数组的原理和实现细节。在Java中,ArrayList是常用的动态数组实现,它可以根据需要动态地增长或缩减存储元素的空间,提供了便捷的操作方法。
自实现ArrayList的核心原理
自实现一个ArrayList主要涉及以下几个核心原理和步骤:
1. **动态数组的基本结构**:使用数组作为基本的存储结构,并实现动态扩展功能。当数组容量不足时,通过创建一个更大的数组并将原有元素拷贝过去来实现扩展。
2. **元素的添加和删除**:实现添加元素、获取元素、删除元素等基本操作。添加元素时,需要考虑数组容量是否足够;删除元素时,可能需要进行数组的整理和缩减容量的操作。
3. **迭代器的实现**:提供迭代器以支持对ArrayList中元素的遍历和操作。
4. **异常处理**:处理可能的越界访问等异常情况。
自实现ArrayList的代码示例
下面是一个简单的自实现ArrayList的代码示例,展示了基本的添加、获取、删除和迭代功能。
```java import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; public class MyArrayList<E> implements Iterable<E> { private static final int DEFAULT_CAPACITY = 10; private Object[] elements; private int size; public MyArrayList() { elements = new Object[DEFAULT_CAPACITY]; size = 0; } public MyArrayList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } elements = new Object[initialCapacity]; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void add(E e) { if (size == elements.length) { ensureCapacity(size + 1); } elements[size++] = e; } @SuppressWarnings("unchecked") public E get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } return (E) elements[index]; } public E remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } @SuppressWarnings("unchecked") E oldValue = (E) elements[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elements, index + 1, elements, index, numMoved); } elements[--size] = null; // Let gc do its work return oldValue; } private void ensureCapacity(int minCapacity) { int oldCapacity = elements.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // grow by 50% if (newCapacity < minCapacity) { newCapacity = minCapacity; } elements = Arrays.copyOf(elements, newCapacity); } @Override public Iterator<E> iterator() { return new Iterator<E>() { private int cursor = 0; @Override public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") @Override public E next() { int i = cursor; if (i >= size) { throw new NoSuchElementException(); } cursor = i + 1; return (E) elements[i]; } }; } public static void main(String[] args) { MyArrayList<String> list = new MyArrayList<>(); list.add("Apple"); list.add("Banana"); list.add("Orange"); System.out.println("Elements in the list:"); for (String fruit : list) { System.out.println(fruit); } System.out.println("Removing element at index 1: " + list.remove(1)); System.out.println("Size of list after removal: " + list.size()); System.out.println("Elements in the list after removal:"); for (String fruit : list) { System.out.println(fruit); } } } ```
解释和关键点说明
- **数组存储**:`elements`数组用于存储元素,初始化时默认容量为`DEFAULT_CAPACITY`(这里设定为10)。
- **添加元素**:`add(E e)`方法将元素添加到数组末尾,如果数组容量不足则通过`ensureCapacity`方法扩展数组。
- **获取元素**:`get(int index)`方法根据索引获取元素,注意边界检查。
- **删除元素**:`remove(int index)`方法删除指定索引位置的元素,将后续元素向前移动。
- **迭代器**:实现了`Iterable<E>`接口,使得可以使用增强的for循环和迭代器遍历列表中的元素。
- **动态扩展**:`ensureCapacity(int minCapacity)`方法负责数组容量的动态扩展,保证足够的存储空间。
这个示例演示了如何基于数组实现一个简单的动态数组,具备基本的添加、获取、删除和迭代功能。自实现ArrayList的过程不仅可以加深对数据结构的理解,还能够理解Java集合框架中ArrayList的设计原理和优化策略。