Java数据结构线性表中的顺序表实现过程

什么是线性表

线性表是最基本、最简单和最常用的一种数据结构，一个线性表是n个具有相同特性的数据元素的有限序列。
若A元素在B元素前面，则称A为B的前驱元素；若B元素在A元素的后面，则称B为A的后继元素。
线性表的特征：数据元素之间存在一对一的关系
第一个数据元素没有前驱元素，叫头结点。
最后一个数据元素没有后继元素，叫尾结点。
除了头尾结点，其它数据元素有且仅有一个前驱元素和后继元素。

线性表的分类

按照数据的存储方式可以分为顺序表和链表。

顺序表实战

顺序表根据索引查询快（元素在内存中连续），添加和删除元素的效率低（要做元素的迁移或者移位）。

顺序表基于数组实现，基本实现：

import java.util.Iterator;

public class SequenceList<T> implements Iterable<T> {
    //1、存储元素的数组
    private T[] arr;
    //2、记录当前顺序表中的元素个数
    private int N;

    //3、构造函数
    public SequenceList(int capacity) {
        //初始化数组
        this.arr = (T[]) new Object[capacity];
        //初始化长度
        this.N = 0;
    }

    //4、将顺序表置为空表
    public void clear() {
        this.N = 0;
    }

    //5、判断当前顺序表是否为空
    public boolean isEmpty() {
        return this.N == 0;
    }

    //6、获取顺序表的元素个数
    public int length() {
        return N;
    }

    //7、获取指定位置的元素
    public T get(int i) {
        //严格来说需要判断索引是否越界
        return arr[i];
    }

    //8、向顺序表中添加元素t
    public void add(T t) {
        //判断扩容
        if (N == arr.length) {
            resize(2 * arr.length);
        }
        arr[N++] = t;
    }

    //9、在i索引处插入元素t
    public void insert(int i, T t) {
        //判断扩容
        if (N == arr.length) {
            resize(2 * arr.length);
        }
        //先把i索引处的元素及其后面的元素依次向后移动一位
        for (int index = N; index > i; index--) {
            arr[index] = arr[index - 1];
        }
        //再把t元素放到i索引处
        arr[i] = t;
        //数组元素个数 +1
        this.N++;
    }

    //10、删除 i索引 处的元素，并返回该元素
    public T remove(int i) {
        //记录索引 i 处的值
        T current = arr[i];
        //索引i后面的元素依次向前移动一位即可
        for (int index = i; index < N - 1; index++) {
            arr[index] = arr[index + 1];
            //判断
            if (index == N - 2) {
                arr[index + 1] = null;
            }
        }
        //元素个数 -1
        this.N--;
        //判断缩容
        if (N < arr.length / 4) {
            resize(arr.length / 2);
        }
        return current;
    }

    //11、查找t元素第一次出现的位置
    public int indexOf(T t) {
        for (int i = 0; i < N; i++) {
            if (arr[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    //12、遍历（类实现Iterable接口，重写iterator方法；创建内部类，重写hasNext和next方法）
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator {
        private int cursor;

        public SIterator() {
            this.cursor = 0;
        }

        @Override
        public boolean hasNext() {
            return cursor < N;
        }

        @Override
        public Object next() {
            return arr[cursor++];
        }
    }

    //13、容量可变（增加元素容量不够时扩容为原数组的2倍，删除元素容量浪费时缩容为原数组的1/2）
    public void resize(int newSize) {
        //定义临时数组，指向原数组
        T[] temp = arr;
        //创建新数组，拷贝原数组
        arr = (T[]) new Object[newSize];
        for (int i = 0; i < N; i++) {
            arr[i] = temp[i];
        }
    }
}

---