java之顺序表的创建

顺序表（Sequential List）是一种线性数据结构，其底层通常采用数组来存储数据元素。顺序表的优点在于其存取速度快，可以通过下标直接访问元素，插入和删除操作的时间复杂度也比较明显。然而，顺序表在扩展时会涉及到数组的复制，内存管理也是一个需要注意的问题。

顺序表的基本特性

1. 固定大小：顺序表一旦创建，其容量是固定的。如果需要增加容量，通常需要创建一个新的更大的数组，并将旧数组的数据复制过来。
2. 快速存取：由于顺序表的元素存储在连续的内存位置上，因此可以通过下标快速访问元素。
3. 插入和删除的代价：在顺序表中插入或删除元素时，可能需要移动大量元素，导致效率降低。

顺序表的基本操作

顺序表的基本操作主要包括：创建顺序表、插入元素、删除元素、查找元素和显示顺序表。

以下是一个简单的顺序表实现示例，代码包括了基本的创建、插入、删除和遍历操作：

public class SequentialList {
    private int[] array; // 存储数据的数组
    private int size; // 当前顺序表的元素个数
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    // 构造函数，初始化顺序表
    public SequentialList() {
        array = new int[DEFAULT_CAPACITY];
        size = 0;
    }

    // 插入元素
    public void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 扩容
        if (size == array.length) {
            resize();
        }
        // 移动元素，为插入腾出空间
        for (int i = size; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = value; // 插入新的元素
        size++;
    }

    // 删除元素
    public int delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        int deletedValue = array[index];
        // 移动元素，以填补被删除元素的位置
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return deletedValue; // 返回被删除的元素
    }

    // 扩展数组
    private void resize() {
        int newSize = array.length * 2; // 新大小为当前大小的两倍
        int[] newArray = new int[newSize];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
    }

    // 显示顺序表中的所有元素
    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    // 测试顺序表的功能
    public static void main(String[] args) {
        SequentialList list = new SequentialList();
        list.insert(0, 10);
        list.insert(1, 20);
        list.insert(1, 15); // 在索引1位置插入15
        list.display(); // 输出: 10 15 20

        list.delete(1); // 删除索引1的元素
        list.display(); // 输出: 10 20
    }
}

代码解析

• 构造函数：初始化长度为10的数组和当前元素个数。
• 插入方法：首先检查索引是否越界，如果数组已满，调用resize方法进行扩容，然后依次移动元素，腾出空间插入新元素。
• 删除方法：删除特定位置的元素，删除后将后面的元素前移。
• 扩容方法：实现简单的数组倍增机制，使用System.arraycopy快速复制数组。
• 显示方法：遍历顺序表并打印所有元素。

总结

顺序表是一种简单高效的线性数据结构，特别适合用于查找和随机访问的场景。不过，由于插入和删除操作的时间复杂度较高，对于频繁变动的数据，可能需要考虑其他数据结构（如链表）。顺序表的实现过程虽然简单，却涉及到数据结构的许多基本概念，对学习数据结构有很大的帮助。