数据结构(Java版)第五期：ArrayList与顺序表(下)

目录

一、数组实现顺序表

在探讨顺序表的实现时，我们通常会想到数组这一基础数据结构。本文将通过一个简单的例子，展示如何使用数组来构建一个顺序表，并实现其基本操作。

public class MyArrayList {
    private int[] arr;
    private int size; // 记录有效元素的数量

    // 构造函数，初始化数组容量
    public MyArrayList(int capacity) {
        arr = new int[capacity];
    }
}

在上述代码中，我们定义了一个名为MyArrayList的类，它使用一个整型数组arr来存储元素，并用一个size变量来追踪当前有效元素的数量。

接下来，我们将实现一系列方法，以支持顺序表的基本操作，包括增加、删除、查找和修改元素。

// 返回顺序表中元素的数量
public int size() {
    return size;
}

// 在顺序表末尾添加一个新元素
public void add(int val) {
    if (size == arr.length) {
        resize();
    }
    arr[size++] = val;
}

// 在指定位置插入一个新元素
public void add(int index, int val) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    if (size == arr.length) {
        resize();
    }
    for (int i = size; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = val;
    size++;
}

// 根据下标获取元素
public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    return arr[index];
}

// 根据下标设置元素
public void set(int index, int val) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    arr[index] = val;
}

// 删除指定值的第一个元素
public void delete(int val) {
    int index = indexOf(val);
    if (index != -1) {
        remove(index);
    }
}

// 根据下标删除元素
public void remove(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    for (int i = index; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    size--;
}

// 检查元素是否存在于顺序表中
public boolean contains(int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) {
            return true;
        }
    }
    return false;
}

// 查找元素的索引
public int indexOf(int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) {
            return i;
        }
    }
    return -1;
}

// 清空顺序表
public void clear() {
    size = 0;
}

// 将顺序表转换为字符串形式，便于打印
@Override
public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append("[");
    for (int i = 0; i < size; i++) {
        stringBuilder.append(arr[i]);
        if (i < size - 1) {
            stringBuilder.append(", ");
        }
    }
    stringBuilder.append("]");
    return stringBuilder.toString();
}

// 私有方法，用于扩容
private void resize() {
    int[] newArr = new int[(int) (arr.length * 1.5)];
    for (int i = 0; i < size; i++) {
        newArr[i] = arr[i];
    }
    arr = newArr;
}

现在，我们已经实现了一个基本的顺序表类MyArrayList，它包含了添加、删除、查找和修改元素的方法。接下来，我们将通过一个简单的测试来验证我们的实现。

public static void test() {
    MyArrayList list = new MyArrayList(10);
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    System.out.println("Size: " + list.size());
    System.out.println("List: " + list);
}

public static void main(String[] args) {
    test();
}

通过上述测试代码，我们可以验证MyArrayList类的功能是否符合预期。这个简单的实现展示了如何使用数组来构建一个顺序表，并提供了基本的操作接口。