Java 数据结构深入理解ArrayList与顺序表

Java 数据结构深入理解ArrayList与顺序表攻略

1. 什么是ArrayList？

ArrayList是Java集合框架中的一个类，是一个基于动态数组实现的可变大小的容器。

与传统的静态数组相比，ArrayList可以动态地增加和减少元素的个数，而无需预先指定数组的大小，并且ArrayList是支持泛型的，能够存储任意类型的对象。

ArrayList的接口定义如下所示：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    // 构造函数
    public ArrayList()

    ... // 其他方法

}

2. ArrayList的实现原理

ArrayList的底层是一个Object类型的数组，它动态地扩容和收缩。

当ArrayList已经占满了当前数组的空间，再往其中添加元素时，会先创建一个新的底层数组，长度是旧数组的1.5倍，并将旧的数组中的元素复制到新的数组中，然后再将新的元素添加进去。如果插入或删除元素时，ArrayList的大小低于1/4，则会将底层数组的长度缩减到当前长度的1/2。

由于ArrayList底层是数组，因此它查询元素的速度非常快，但是插入和删除元素的操作速度相对较慢。如果涉及到大量的元素插入和删除操作，使用链表类的集合可能更加适合。

3. 顺序表的实现

顺序表是一种常见的线性数据结构，它由一组连续的存储空间构成，用来存储同类型的元素。顺序表中的每个元素都可以通过下标来访问，所以查询元素的时间复杂度为O(1)。但是插入和删除元素的操作速度相对较慢，需要移动其他元素的位置。

以下是一个简单的顺序表的实现：

public class MyArrayList<T> {

    private T[] array;
    private int size;

    public MyArrayList(int capacity) {
        this.array = (T[])new Object[capacity];
        this.size = 0;
    }

    ...
}

其中，array是用来存储元素的数组，size是当前元素的个数。可以通过在构造函数中传入参数capacity来指定数组的大小。

实现顺序表的基本操作，如插入元素、删除元素、查询元素等，可以参考以下代码：

public class MyArrayList<T> {

    ...

    // 在指定位置插入元素
    public void add(int index, T element) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        // 判断容量，如果已经满了，需要进行扩容
        if (size == array.length) {
            int newCapacity = array.length * 2;
            T[] newArray = (T[])new Object[newCapacity];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }

        // 将index之后的元素往后移一位
        for (int i = size; i > index; i--) {
            array[i] = array[i-1];
        }

        // 将元素插入到index处
        array[index] = element;
        size++;
    }

    // 删除指定位置的元素
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        // 将index之后的元素往前移一位
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i+1];
        }

        size--;
    }

    // 查询指定位置的元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        return array[index];
    }

    // 返回当前元素的数量
    public int size() {
        return size;
    }
}

4. 示例说明

示例1：使用ArrayList存储字符串

import java.util.ArrayList;

public class TestArrayList {

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

        list.add("apple");
        list.add("banana");
        list.add("orange");

        System.out.println(list); // 输出：[apple, banana, orange]
    }

}

在这个示例中，我们使用ArrayList存储了三种水果的名称，然后通过System.out.println输出了整个列表。

示例2：使用自定义的顺序表存储整数

public class TestMyArrayList {

    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>(3);

        list.add(0, 1);
        list.add(1, 2);
        list.add(2, 3);
        list.add(1, 4);

        System.out.println(list.get(0)); // 输出：1
        System.out.println(list.get(1)); // 输出：4
        System.out.println(list.get(2)); // 输出：2
        System.out.println(list.get(3)); // 输出：3

        list.remove(1);

        System.out.println(list.get(0)); // 输出：1
        System.out.println(list.get(1)); // 输出：2
        System.out.println(list.get(2)); // 输出：3
    }

}

在这个示例中，我们使用自定义的MyArrayList存储了四个整数，然后通过System.out.println输出了指定位置的元素。接着，我们删除了第二个位置的元素，并再次输出了所有元素。