线性表之顺序表

前言

1）、线性表是最基本，最简单，也是最常用的一种数据结构，一个线性表是 n 个具有相同特性的数据元素的有限序列。

2）、线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

今天我们主要介绍顺序表。

一、顺序表的实现

顺序表是在计算机中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

如下数组：

1.1、顺序表 API 设计

类名	SequenceList<T>
构造方法	Sequence(int capacity) ：创建容量为 capacity 的 SequenceList 对象
成员方法	1、public void clean() ：清空线性表 2、public boolean isEmpty() ：线性表是否为空 3、public int length() ：获取线性表元素的个数 4、public T get(int i) ：获取线性表中第 i 个位置元素的值 5、public void insert(int i,T t) ：在第 i 个元素之前插入一个值为 t 的数据元素 6、public void insert(T t) ：向线性表中添加一个元素 t 7、public T remove(int i) ：删除并返回线性表中第 i 个位置的数据元素 8、public int indexOf(T t) ：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回 -1
成员变量	1、private T[] eles ：存储元素的数组 2、private int N ：当前线性表的长度

1.2、顺序表具体实现

接下来我们根据 API 设计来编写具体的实现类：

public class SequenceList<T>{

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中元素的个数
    private int N;

    //构造方法
    public SequenceList(int capacity) {
        eles = (T[]) new Object[capacity];
    }

    //清空
    public void clear(){
        N = 0;
    }

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

    //长度
    public int length(){
        return N;
    }

    //获取元素
    public T get(int i){
        return eles[i];
    }

    //插入元素，带下标
    public void insert(int i, T t) {
        //1、将 i 及之后位置的元素往后移一位
        for (int index = N; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //2、在 i 位置处插入 t
        eles[i] = t;
        //3、元素个数加 1
        N++;
    }

    //插入元素
    public void insert(T t){
        eles[N++] = t;
    }

    //移除并返回当前元素
    public T remove(int i){
        final T removeElement = eles[i];
        for(int index = i; index < N - 1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        return removeElement;
    }

    //获取当前元素的索引
    public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }
}

1.3、顺序表测试

public class Test {

    public static void main(String[] args) {
        SequenceList<String> strList = new SequenceList<>(10);
        //1、插入元素
        strList.insert("姚明");
        strList.insert("科比");
        strList.insert("麦迪");
        strList.insert(1,"詹姆斯");
        //2、获取元素
        String result = strList.get(1);
        System.out.println(result);//詹姆斯
        //3、删除元素
        String removeElement = strList.remove(0);
        System.out.println(removeElement);//姚明
        //4、测试清空
        strList.clear();
        System.out.println(strList.length());//0
    }
}

二、顺序表的遍历

作为存储容器，一般需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。

在 Java 中，遍历集合的方式一般都是用 foreach 循环，如果想让我们的 SequenceList 也能支持 foreach ，则需要做如下操作：

1、让 SequenceList 实现 Iterable 接口，重写 iterator 接口

2、在 SequenceList 内部提供一个内部类 SIterator，实现 Iterator 接口，重写 hasNext() 方法和 next() 方法

具体实现如下：

public class SequenceList<T> implements Iterable<T>{

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中元素的个数
    private int N;

    //构造方法
    public SequenceList(int capacity) {
        eles = (T[]) new Object[capacity];
    }

    //清空
    public void clear(){
        N = 0;
    }

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

    //长度
    public int length(){
        return N;
    }

    //获取元素
    public T get(int i){
        return eles[i];
    }

    //插入元素，带下标
    public void insert(int i, T t) {
        //1、将 i 及之后位置的元素往后移一位
        for (int index = N; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //2、在 i 位置处插入 t
        eles[i] = t;
        //3、元素个数加 1
        N++;
    }

    //插入元素
    public void insert(T t){
        eles[N++] = t;
    }

    //移除并返回当前元素
    public T remove(int i){
        final T removeElement = eles[i];
        for(int index = i; index < N - 1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        return removeElement;
    }

    //获取当前元素的索引
    public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

    //================================== 新增部分代码 start =================================
    @NonNull
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    class SIterator implements Iterator<T>{

        private int cursor;

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

        @Override
        public T next() {
            return eles[cursor++];
        }
    }
    //================================== 新增部分代码 start =================================
}

//测试
public class Test {

    public static void main(String[] args) {
        SequenceList<String> strList = new SequenceList<>(10);
        //1、插入元素
        strList.insert("姚明");
        strList.insert("科比");
        strList.insert("麦迪");
        strList.insert(1,"詹姆斯");
        for (String s : strList) {
            System.out.println(s);
        }
    }
}

//打印结果
姚明
詹姆斯
科比
麦迪

三、顺序表的容量可变

前面的实现中，当我们使用 SequenceList 时，先 new SequenceList(5) 创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了 5 个元素，还要继续插入数据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的伸缩性。

1、添加元素时：

添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个时原数组两倍容量的新数组存储元素，如下图：

2、移除元素时：

移除元素时，应该检查当前数组的大小是否太大，比如正在用 100 个容量的数组存储 10 个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的 1/2 的新数组存储元素，如下图：

具体实现如下：

public class SequenceList<T> implements Iterable<T>{

    //存储元素的数组
    private T[] eles;
    //记录当前顺序表中元素的个数
    private int N;

    //构造方法
    public SequenceList(int capacity) {
        eles = (T[]) new Object[capacity];
    }

    //清空
    public void clear(){
        N = 0;
    }

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

    //长度
    public int length(){
        return N;
    }

    //获取元素
    public T get(int i){
        return eles[i];
    }

    //插入元素，带下标
    public void insert(int i, T t) {
        //检查是否需要扩容
        if(N == eles.length){
            resize(eles.length * 2);
        }
        //1、将 i 及之后位置的元素往后移一位
        for (int index = N; index > i; index--) {
            eles[index] = eles[index - 1];
        }
        //2、在 i 位置处插入 t
        eles[i] = t;
        //3、元素个数加 1
        N++;
    }

    //插入元素
    public void insert(T t){
        //检查是否需要扩容
        if(N == eles.length){
            resize(eles.length * 2);
        }
        eles[N++] = t;
    }

    //移除并返回当前元素
    public T remove(int i){
        //检查是否需要缩容
        if(N < eles.length / 4){
            resize(eles.length / 2);
        }
        final T removeElement = eles[i];
        for(int index = i; index < N - 1; index++){
            eles[index] = eles[index + 1];
        }
        N--;
        return removeElement;
    }

    //获取当前元素的索引
    public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(eles[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

    @NonNull
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    class SIterator implements Iterator<T>{

        private int cursor;

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

        @Override
        public T next() {
            return eles[cursor++];
        }
    }

    //扩容或者缩容
    public void resize(int newSize){
        //1、定义一个临时数组，指向原数组
        T[] temp = eles;
        //2、创建新数组
        eles = (T[]) new Object[newSize];
        //3、把原数组的数据拷贝到新数组
        for (int i = 0; i < N; i++) {
            eles[i] = temp[i];
        }
    }
}

四、顺序表的时间复杂度

4.1、get(i) 方法时间复杂度

get(i) 不难看出，不论数据元素量 N 有多大，只需要一次 eles[i] 就可以获取到对应的元素，所以时间复杂度为 O(1)

4.2、insert(int i,T t) 方法时间复杂度

insert(int i,T t) 每一次插入，都需要把 i 及 i 后面位置的元素往后移一位，随着元素数量 N 的增大，移动的元素也越多，时间复杂度为 O(n)

4.3、remove(int i) 方法时间复杂度

remove(int i) 每一次删除，都需要把 i 及 i 后面位置的元素往前移一位，随着元素数量 N 的增大，移动的元素也越多，时间复杂度为 O(n)

五、Java 中 ArrayList 实现

Java 中 ArrayList 集合的底层就是一种顺序表，类似我们上面 SequenceList，使用数组实现，同样提供了增删改查，遍历及扩容等功能。

六、总计

本篇文章我们介绍了：

1、顺序表的 API 设计并进行了具体实现，以及进行测试用例测试

2、通过实现 Iterable 接口让我们的顺序表能够使用增强 for 循环来遍历

3、对顺序表进行扩容处理

4、分析了顺序表中核心方法的时间复杂度：

1、get(i)：O(1)

2、set(int i,T t)：O(n)

3、remove(int i)：O(n)

5、介绍了 Java 中的 ArrayList，实际上它的实现和 Sequence 类似

好了，本篇文章到这里就结束了，感谢你的阅读🤝