动态数组

动态数组是一个能够在程序运行时根据需要动态扩展大小的数组，它通常用于存储和管理元素数量不确定的数据。与静态数组不同，静态数组的大小一旦定义就不可改变，而动态数组则可以根据需要增加或减少存储空间。Java中没有内建的"动态数组"类型，但可以通过ArrayList类实现动态数组的功能，或者自己手动实现一个简单的动态数组。

本文将介绍如何在Java中实现动态数组，分析其基本原理，并提供相关的代码示例。

1. 动态数组的基本原理

动态数组的核心思想是，当数组满时，会创建一个更大的数组，将原数组中的元素复制到新数组中。通过这种方式，动态数组的大小可以不断增长。

主要特点

• 动态调整大小：当数组的大小不够时，数组会自动扩大，通常是原大小的2倍。
• 顺序存储：与静态数组类似，动态数组使用连续的内存空间来存储数据，因此可以实现常数时间的随机访问。
• 增加/删除操作：虽然动态数组可以灵活扩展，但增加或删除元素时可能需要移动其他元素，这会增加一定的时间复杂度。

2. 动态数组的实现

Java 提供了 ArrayList 类来简化动态数组的操作。ArrayList 底层就是通过动态数组实现的，开发者可以直接使用这个类进行增删查改操作。

2.1 使用 ArrayList 实现动态数组

import java.util.ArrayList;

public class DynamicArrayExample {
    public static void main(String[] args) {
        // 创建一个空的动态数组
        ArrayList<Integer> dynamicArray = new ArrayList<>();

        // 向动态数组添加元素
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        dynamicArray.add(40);

        // 输出数组内容
        System.out.println("ArrayList: " + dynamicArray);

        // 获取数组中的元素
        int element = dynamicArray.get(2);
        System.out.println("Element at index 2: " + element);

        // 修改数组中的元素
        dynamicArray.set(1, 25);
        System.out.println("Updated ArrayList: " + dynamicArray);

        // 删除数组中的元素
        dynamicArray.remove(3); // 删除索引为3的元素
        System.out.println("ArrayList after removal: " + dynamicArray);

        // 获取动态数组的大小
        System.out.println("Size of ArrayList: " + dynamicArray.size());
    }
}

2.2 解释

• ArrayList 是一个动态数组实现，它的大小会随着元素的增加而自动增长。
• add(E e) 方法用于向数组中添加元素。
• get(int index) 用于获取指定索引的元素。
• set(int index, E element) 用于修改指定索引的元素。
• remove(int index) 用于删除指定索引的元素。
• size() 返回动态数组当前包含的元素数量。

通过 ArrayList 类，我们可以轻松实现动态数组的功能，避免手动扩展数组。

3. 自定义实现一个动态数组

如果你想更深入理解动态数组的实现原理，或者想自己实现一个简单的动态数组，我们可以手动写一个动态数组类。这里提供一个简单的实现示例：

3.1 自定义动态数组类

package com.shenlink.list;

import java.util.Objects;

public class ArrayList<E> {
    private int size;

    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capacity) {
        capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    public void add(E element) {
        add(size, element);
    }

    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    public E set(int index, E element) {
        rangeCheck(index);
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    public E remove(int index) {
        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        trim();
        return old;
    }

    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (Objects.equals(element, elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    public void trim() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1;
        if (size > newCapacity || oldCapacity < DEFAULT_CAPACITY) return;
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

4. 性能分析

4.1 添加元素的时间复杂度

• 当数组有足够空间时，add() 操作的时间复杂度是 O(1)。
• 当数组已满，需要扩展数组时，expandCapacity() 方法需要复制所有的元素，这会使得此操作的时间复杂度是 O(n)，其中 n 是数组中当前元素的数量。

4.2 获取和修改元素的时间复杂度

• 获取和修改元素的操作都是 O(1)，因为它们只涉及直接索引访问。

4.3 删除元素的时间复杂度

• 删除元素通常需要移动数组中的其他元素，因此删除操作的时间复杂度是 O(n)，其中 n 是删除元素之后数组的大小。

5. 总结

动态数组是一种非常实用的数据结构，它能够自动调整大小，从而有效地处理大小不固定的集合。Java 中的 ArrayList 类已经封装了这一实现，我们可以直接使用它来进行动态数组的操作。如果需要更多控制，也可以手动实现一个简单的动态数组，理解其底层的实现机制。

动态数组具有常数时间的访问和修改元素的能力，但在扩展和删除操作时可能会有性能瓶颈。因此，选择合适的数据结构需要根据具体的应用场景来决定。