【顺序表的模拟实现Java】

顺序表（Sequence List）是一种基于数组实现的线性表。它是将线性表中各个元素在内存中存储为连续的一段存储空间，以便在访问元素时能够以 O(1) 的时间复杂度进行快速访问。本文将介绍顺序表的基本实现，包括增、删、查、改等基本操作，并给出相应的 Java 代码示例。

顺序表的基本结构

在 Java 中，我们可以通过一个数组来实现顺序表。通常情况下，我们需要维护以下几个属性： - 存储元素的数组 - 顺序表的当前大小（已存储的元素个数） - 顺序表的最大容量

下面是顺序表的基本实现：

public class SequenceList<T> {
    private T[] element; // 存储元素的数组
    private int size; // 当前元素个数
    private int capacity; // 最大容量

    @SuppressWarnings("unchecked")
    public SequenceList(int capacity) {
        this.capacity = capacity;
        this.element = (T[]) new Object[capacity]; // 初始化数组
        this.size = 0; // 当前大小为 0
    }

    // 增加元素
    public void add(T item) {
        if (size >= capacity) {
            throw new IllegalStateException("顺序表已满，无法添加新的元素。");
        }
        element[size++] = item; // 将元素添加到末尾并增加大小
    }

    // 指定位置插入元素
    public void insert(int index, T item) {
        if (size >= capacity) {
            throw new IllegalStateException("顺序表已满，无法插入新的元素。");
        }
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("索引越界： " + index);
        }
        // 从后往前移动元素
        for (int i = size; i > index; i--) {
            element[i] = element[i - 1];
        }
        element[index] = item; // 插入新元素
        size++; // 更新大小
    }

    // 获取元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界： " + index);
        }
        return element[index]; // 返回索引位置的元素
    }

    // 删除元素
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界： " + index);
        }
        // 从前往后移动元素
        for (int i = index; i < size - 1; i++) {
            element[i] = element[i + 1];
        }
        element[--size] = null; // 将最后一个元素置为 null
    }

    // 更新元素
    public void set(int index, T item) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界： " + index);
        }
        element[index] = item; // 更新指定位置的元素
    }

    // 获取顺序表的当前大小
    public int size() {
        return size;
    }

    // 判断顺序表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
}

示例代码解释

1. 构造函数：接受一个参数 capacity，用于初始化顺序表的容量和元素数组。
2. 增加元素：add 方法用于在顺序表末尾添加元素。
3. 插入元素：insert 方法用于在指定的位置插入元素，需处理数组中元素的位移。
4. 获取元素：get 方法根据索引获取顺序表中的元素。
5. 删除元素：remove 方法根据索引删除指定的元素，并对后续元素进行位移处理。
6. 更新元素：set 方法用于更新指定位置的元素。
7. 辅助方法：size 和 isEmpty 方法用于查询顺序表的大小与是否为空。

总结

通过以上代码实现，我们对顺序表的基本操作有了一个清晰的理解。在实际开发中，顺序表适用于大多数需要频繁随机访问的场景，但对于频繁插入和删除操作的场景，可能更适合选择链表等数据结构。希望本文能帮助读者理解顺序表的实现思路与基本用法。