顺序表的基本概念及实现

顺序表（Sequential List）是一种线性表的顺序存储实现方式，常见于数组。它利用一段连续的内存空间来存储数据元素，支持快速的随机访问。由于内存地址是连续的，因此可以通过元素的索引（下标）直接访问元素，访问时间复杂度为 O(1)。

线性结构

线性结构是数据结构中最基本、最常用的一类结构，其特点是数据元素之间存在一对一的线性关系，数据元素按顺序排列。线性结构包括：

顺序表（数组）
链表
栈
队列

一、顺序表的基本概念

1. 顺序表的特点

连续存储：数据元素在内存中按照顺序连续存放。
随机访问：可以通过下标直接访问任意位置的元素，访问速度快。
固定容量：容量固定，初始化后大小不能改变（对于数组而言）。
存储类型一致：存储的元素类型必须相同。

2. 顺序表的优缺点

优点：

访问速度快：支持随机访问，查找元素效率高。
空间利用率高：不需要额外的存储空间来存放节点指针。

缺点：

插入和删除效率低：在中间位置插入或删除元素时，需要移动大量元素。
容量固定：数组的容量固定，不能动态扩容（除非手动实现扩容机制）。

二、顺序表的初始化和判空判满功能实现

1. 初始化顺序表

在 Java 中，可以使用数组或集合类来实现顺序表。下面以数组为基础，实现一个简单的顺序表。

public class SequenceList {
    private int[] data;    // 存储元素的数组
    private int size;      // 当前元素数量
    private int capacity;  // 顺序表容量

    // 初始化顺序表
    public SequenceList(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        size = 0;
    }
}

2. 判空功能实现

判断顺序表是否为空，即判断 size 是否为 0。

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

3. 判满功能实现

判断顺序表是否已满，即判断 size 是否等于 capacity。

// 判断顺序表是否已满
public boolean isFull() {
    return size == capacity;
}

三、顺序表实现之指定位置数据的增加与遍历操作

1. 在指定位置增加元素

在顺序表的指定位置插入元素，需要考虑以下情况：

位置合法性检查：插入位置应在 [0, size] 之间。
顺序表是否已满：如果已满，需要先扩容（后续会介绍）。
元素后移：从插入位置开始，后面的元素需要依次后移一位。

// 在指定位置插入元素
public void insert(int index, int element) {
    if (isFull()) {
        throw new RuntimeException("顺序表已满，无法插入新元素");
    }
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("插入位置不合法");
    }
    // 元素后移
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = element;
    size++;
}

2. 遍历顺序表

遍历顺序表中的元素，依次输出或处理每个元素。

// 遍历顺序表
public void traverse() {
    for (int i = 0; i < size; i++) {
        System.out.print(data[i] + " ");
    }
    System.out.println();
}

四、顺序表实现删除指定位置的元素与修改操作

1. 删除指定位置的元素

删除指定位置的元素，需要将后面的元素依次前移。

// 删除指定位置的元素
public void delete(int index) {
    if (isEmpty()) {
        throw new RuntimeException("顺序表为空，无法删除元素");
    }
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("删除位置不合法");
    }
    // 元素前移
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    size--;
}

2. 修改指定位置的元素

修改指定位置的元素，即将新值赋给指定位置。

// 修改指定位置的元素
public void update(int index, int element) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("修改位置不合法");
    }
    data[index] = element;
}

五、顺序表实现扩容操作

由于数组的容量固定，当顺序表满时，需要进行扩容。扩容的思路是创建一个更大的数组，将原数组的元素复制过去。

// 扩容操作
private void resize(int newCapacity) {
    int[] newData = new int[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData;
    capacity = newCapacity;
}

// 修改插入方法，支持自动扩容
public void insert(int index, int element) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("插入位置不合法");
    }
    if (isFull()) {
        resize(capacity * 2); // 扩容为原来的两倍
    }
    // 元素后移
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = element;
    size++;
}

六、顺序表使用泛型适应多种类型数据

为了使顺序表适应多种类型的数据，可以使用 Java 的泛型。

public class SequenceList<T> {
    private T[] data;      // 存储元素的数组
    private int size;      // 当前元素数量
    private int capacity;  // 顺序表容量

    // 初始化顺序表
    @SuppressWarnings("unchecked")
    public SequenceList(int capacity) {
        this.capacity = capacity;
        data = (T[]) new Object[capacity];
        size = 0;
    }

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

    // 判满
    public boolean isFull() {
        return size == capacity;
    }

    // 插入元素
    public void insert(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入位置不合法");
        }
        if (isFull()) {
            resize(capacity * 2);
        }
        for (int i = size -1; i >= index; i--) {
            data[i +1] = data[i];
        }
        data[index] = element;
        size++;
    }

    // 删除元素
    public void delete(int index) {
        if (isEmpty()) {
            throw new RuntimeException("顺序表为空，无法删除元素");
        }
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("删除位置不合法");
        }
        for (int i = index; i < size -1; i++) {
            data[i] = data[i +1];
        }
        size--;
        // 缩容（可选）
        if (size > 0 && size == capacity / 4) {
            resize(capacity / 2);
        }
    }

    // 修改元素
    public void update(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("修改位置不合法");
        }
        data[index] = element;
    }

    // 获取元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("获取位置不合法");
        }
        return data[index];
    }

    // 遍历顺序表
    public void traverse() {
        for (int i = 0; i < size; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    // 扩容/缩容
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
        capacity = newCapacity;
    }
}

七、测试顺序表

编写一个测试类，验证顺序表的各项功能。

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<Integer> list = new SequenceList<>(5);

        // 插入元素
        list.insert(0, 10);
        list.insert(1, 20);
        list.insert(2, 30);
        list.insert(1, 15);
        list.insert(3, 25);
        list.insert(5, 35); // 触发扩容
        System.out.print("插入元素后：");
        list.traverse();

        // 删除元素
        list.delete(2);
        System.out.print("删除索引为 2 的元素后：");
        list.traverse();

        // 修改元素
        list.update(3, 100);
        System.out.print("修改索引为 3 的元素后：");
        list.traverse();

        // 获取元素
        int element = list.get(2);
        System.out.println("索引为 2 的元素为：" + element);

        // 判空
        System.out.println("顺序表是否为空：" + list.isEmpty());

        // 判满
        System.out.println("顺序表是否已满：" + list.isFull());
    }
}

运行结果：

插入元素后：10 15 20 25 30 35 
删除索引为 2 的元素后：10 15 25 30 35 
修改索引为 3 的元素后：10 15 25 100 35 
索引为 2 的元素为：25
顺序表是否为空：false
顺序表是否已满：false

顺序表的基本概念：顺序表利用连续的内存空间存储数据，支持快速的随机访问。
初始化和判空判满：在初始化时指定容量，判空判满通过 size 和 capacity 比较实现。
增加与遍历操作：在指定位置插入元素时，需要将后续元素后移；遍历时依次访问每个元素。
删除与修改操作：删除指定位置元素需要将后续元素前移；修改操作直接更新指定位置的值。
扩容操作：当顺序表满时，通过创建更大的数组并复制元素来实现扩容。
使用泛型适应多种类型数据：通过泛型，使顺序表可以存储任意类型的数据，提高了通用性。

算法之旅(三) 顺序表