Java数据结构顺序表用法详解

什么是顺序表？

在计算机科学中，顺序表（英语：Sequence）指的是一种线性数据结构，通常是用数组实现的。顺序表是一种顺序存放的线性表，其中的每个节点按照顺序依次排列。

顺序表的基本操作

顺序表主要包括以下几个基本操作：

• 创建顺序表
• 在顺序表中插入元素
• 从顺序表中删除元素
• 获取顺序表中的元素
• 判断顺序表是否为空
• 获取顺序表的长度

Java中顺序表的实现

在Java中，我们可以使用数组来实现顺序表。以下是一些常用的Java代码实现：

创建顺序表

public class ArrayList<T> {
    private T[] data;
    private int size;

    public ArrayList(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    public ArrayList() {
        this(10);
    }
}

插入元素

public void add(int index, T e) {
    if (size == data.length) {
        resize(2 * data.length);
    }
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed. Index is illegal.");
    }
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = e;
    size ++;
}

删除元素

public T remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Remove failed. Index is illegal.");
    }
    T ret = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    size --;
    data[size] = null;
    if (size == data.length / 4 && data.length / 2 != 0) {
        resize(data.length / 2);
    }
    return ret;
}

获取顺序表中的元素

public T get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Get failed. Index is illegal.");
    }
    return data[index];
}

判断顺序表是否为空

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

获取顺序表的长度

public int getSize() {
    return size;
}

示例说明

下面给出两个示例说明，使用上面的代码实现顺序表的基本操作：

示例1：创建一个长度为10的顺序表，从第二个位置开始插入整数1-10

ArrayList<Integer> list = new ArrayList<>(10);
for (int i = 1; i <= 10; i++) {
    list.add(i-1, i);
}
for (int i = 0; i < list.getSize(); i++) {
    System.out.print(list.get(i) + " ");
}

输出结果：1 2 3 4 5 6 7 8 9 10

示例2：创建一个长度为5的顺序表，从第二个位置开始插入字符串“Java”，“Python”，“C++”，从第三个位置删除元素

ArrayList<String> list = new ArrayList<>(5);
list.add(0, "Hello");
list.add(1, "Java");
list.add(2, "Python");
list.add(3, "C++");
System.out.println("Before remove: ");
for (int i = 0; i < list.getSize(); i++) {
    System.out.print(list.get(i) + " ");
}
System.out.println();
list.remove(2);
System.out.println("After remove: ");
for (int i = 0; i < list.getSize(); i++) {
    System.out.print(list.get(i) + " ");
}

输出结果：

Before remove: Hello Java Python C++

After remove: Hello Java C++