Java手写ArrayList和拓展案例

Java手写ArrayList

思维导图

ArrayList是一种动态数组，它可以在内部自动管理数组的容量和元素的存储。下面是ArrayList的基本原理：

1. 内部数组：ArrayList使用一个内部数组来存储元素。这个数组的类型是Object类型的，可以存储任意类型的对象。

2. 容量管理：ArrayList会跟踪数组的容量和当前存储的元素数量。当数组容量不足以容纳新元素时，ArrayList会自动扩展数组的大小。扩展的策略通常是创建一个更大的数组，然后将原数组的元素复制到新数组中。

3. 元素存储：当向ArrayList中添加元素时，它会将元素存储在数组的末尾，并更新存储的元素数量。如果数组容量不足，会先进行扩容操作，然后再添加新元素。

4. 元素访问：可以通过索引来访问ArrayList中的元素。ArrayList会检查索引的有效性，确保不会越界访问。

5. 元素删除：当从ArrayList中删除元素时，它会将数组中的元素向前移动，填补被删除元素的位置。然后，会将数组的最后一个位置置为null，并更新存储的元素数量。

总之，ArrayList的核心原理是使用一个内部数组来存储元素，并通过动态扩容和移动元素的方式来管理元素的添加和删除。这种设计可以提供高效的随机访问和动态调整容量的能力，使得ArrayList成为常用的数据结构之一。

在这个思维导图中，我们将展示如何手写一个简单的ArrayList实现。它将包含数组容量、元素数量、添加元素、获取元素、删除元素和扩容等关键要素。

实现详细介绍和步骤

步骤一：初始化ArrayList

首先，我们需要创建一个ArrayList类，并定义私有变量capacity和size，分别表示数组容量和元素数量。

public class ArrayList<T> {
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
    private Object[] array; // 存储元素的数组
    private int capacity; // 数组容量    private int size; // 元素数量

    public ArrayList() {
        this.capacity = DEFAULT_CAPACITY;
        this.array = new Object[capacity];
        this.size = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

在这个步骤中，我们创建了一个ArrayList类，并初始化了默认的容量、数组和元素数量。

步骤二：添加元素接下来，我们需要实现添加元素的方法add()。当数组已满时，我们需要先扩容，然后再将元素添加数组中。

public void add(T element) {
    if (size == capacity) {
        resize();
    }
    array[size++] = element;
}
1
2
3
4
5
6

在这个步骤中，我们首先检查数组是否已满，如果是，则调用resize()方法进行扩容。然后，我们将元素添加到数组的末尾，并递增元素数量。

步骤三：获取元素我们还需要实现获取元素的方法get()，它将返回指定索引位置的元素。

    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of range");
    }
    return (T) array[index];
}
1
2
3
4
5

在这个步骤中，我们首先检查索引是否越界。如果是，则抛出IndexOutOfBoundsException异常。然后，我们返回指定索引位置的元素。

步骤四：删除元素

接下来，我们需要实现删除元素的方法remove()，它将删除指定索引位置的元素，并将后续元素向前移动。

public void remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of range");
    }
    for (int i = index; i < size - 1; i++) {
        array[i] = array[i + 1];
    }
    array[--size] = null;
}
1
2
3
4
5
6
7
8
9

在这个步骤中，我们首先检查索引是否越界。如果是，则抛出IndexOutOfBoundsException异常。然后，我们从指定索引位置开始，将后续元素向前移动一位，并将最后一个元素置为null，最后递减元素数量。

步骤五：扩容

当需要添加元素时，如果数组已满，我们需要进行扩容。在扩容过程中，我们将创建一个新的数组，并将原数组中的元素复制到新中。

private void resize() {
    int newCapacity = capacity * 2;
    Object[] newArray = new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newArray[i] = array[i];
    }
    array = newArray;
    capacity = newCapacity;
}
1
2
3
4
5
6
7
8
9

在这个步骤中，我们首先计算新的容量（通常是原容量的两倍），然后创建一个新的数组。接下来，我们将原数组中的元素复制到新数组中，并更新数组和容量的引用。

总结

通过以上步骤，我们成功地手写了一个简单的ArrayList实现。我们实现了初始化、添加、获取、删除和扩容等关键功能。虽然这个实现还有很多改进的空间，但它提供了一个基本的框架，帮助我们理解ArrayList的工作原理。

拓展

在这个实现的基础上，我们还可以进行许多拓展和改进，例如：

如果您想对ArrayList进行拓展，可以考虑添加以下功能：

1. 迭代器：实现一个Iterator接口，使得用户可以使用foreach循环遍历ArrayList中的元素。

import java.util.Iterator;

public class ArrayList<E> implements Iterable<E> {
    // ... 省略其他代码 ...

    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements Iterator<E> {
        private int currentIndex = 0;

        @Override
        public boolean hasNext() {
            return currentIndex < size;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return get(currentIndex++);
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

使用示例：

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

for (int num : list) {
    System.out.println(num);
}
1
2
3
4
5
6
7
8

2. 查找指定元素的索引：添加一个方法，用于查找指定元素在ArrayList中的索引位置。

public class ArrayList<E> {
    // ... 省略其他代码 ...

    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

使用示例：

ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");

int index = list.indexOf("banana");
System.out.println("Index of banana: " + index); // Output: Index of banana: 1
1
2
3
4
5
6
7

3. 批量添加元素：添加一个方法，可以一次性添加多个元素到ArrayList中。

public class ArrayList<E> {
    // ... 省略其他代码 ...

    public void addAll(Collection<? extends E> collection) {
        for (E element : collection) {
            add(element);
        }
    }
}
1
2
3
4
5
6
7
8
9

使用示例：

ArrayList<Integer> list = new ArrayList<>();
List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
list.addAll(numbers);

System.out.println(list); // Output: [1, 2, 3, 4, 5]
1
2
3
4
5

这些是对ArrayList进行拓展的一些示例。您可以根据自己的需求，添加其他功能或修改现有功能。

这些拓展将进一步提升ArrayList的功能和灵活性。

希望这篇博客能对您理解Java手写ArrayList的实现思路和步骤有所帮助。如果您有任何或需要进一步的帮助，请随时提问。