数据结构与算法–顺序表(Java)

目录

1. 顺序表简介
2. 顺序表的结构设计
3. 顺序表的基本操作
4. Java 顺序表实现代码
5. 复杂度分析
6. 应用场景
7. 拓展与优化建议

1️⃣ 顺序表简介

• 定义：顺序表是一种线性表结构，元素在内存中连续存储，支持通过索引快速访问。
• 特点：支持随机访问，插入和删除可能涉及大量元素移动。
• 对比：与链表相比，顺序表访问快，插入删除相对慢。

2️⃣ 顺序表的结构设计

• 底层数组：用数组存储元素，固定初始容量，容量不足时扩容。
• size变量：记录当前顺序表中元素个数。
• 扩容机制：当底层数组满时，扩展容量（如扩大1.5倍或2倍）。

3️⃣ 顺序表的基本操作

4️⃣ Java 顺序表实现代码示例

public class SeqList<T> {
    private Object[] data;  // 存储元素的数组
    private int size;       // 当前元素数量
    private static final int DEFAULT_CAPACITY = 10;

    public SeqList() {
        data = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public SeqList(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于0");
        }
        data = new Object[capacity];
        size = 0;
    }

    // 获取当前元素个数
    public int size() {
        return size;
    }

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

    // 获取指定位置的元素
    @SuppressWarnings("unchecked")
    public T get(int index) {
        checkIndex(index);
        return (T) data[index];
    }

    // 设置指定位置的元素
    public void set(int index, T element) {
        checkIndex(index);
        data[index] = element;
    }

    // 在末尾添加元素
    public void add(T element) {
        ensureCapacity(size + 1);
        data[size++] = element;
    }

    // 在指定位置插入元素
    public void add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入位置不合法");
        }
        ensureCapacity(size + 1);
        // 后移元素
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = element;
        size++;
    }

    // 删除指定位置的元素，返回删除的元素
    @SuppressWarnings("unchecked")
    public T remove(int index) {
        checkIndex(index);
        T old = (T) data[index];
        // 前移元素
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(data, index + 1, data, index, numMoved);
        }
        data[--size] = null; // GC回收
        return old;
    }

    // 查找元素首次出现的位置，没找到返回 -1
    public int indexOf(T element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (data[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(data[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    // 确保容量足够，不够则扩容
    private void ensureCapacity(int minCapacity) {
        int oldCapacity = data.length;
        if (minCapacity > oldCapacity) {
            // 扩容为原来的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            Object[] newData = new Object[newCapacity];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }

    // 检查索引是否合法
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
    }

    // 遍历打印所有元素
    public void printAll() {
        System.out.print("[");
        for (int i = 0; i < size; i++) {
            System.out.print(data[i]);
            if (i < size - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

5️⃣ 复杂度分析

6️⃣ 应用场景

• 小规模数据存储，需随机访问的场景
• 实现栈、队列、字符串缓冲区等数据结构基础
• 需要频繁按索引访问元素时优先选择

7️⃣ 拓展与优化建议

• 可结合泛型设计，提高类型安全
• 设计动态缩容策略，避免内存浪费
• 对于插入删除频繁场景，考虑链表替代
• 增加迭代器支持，方便遍历