线性表：顺序表的实现以及遍历扩容

Java学习手册+面试指南：https://javaxiaobear.cn

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

1、顺序表的实现

1、API设计

类名	SequenceCase
构造方法	SequenceCase(int capacity)：创建容量为capacity的SequenceList对象
成员方法	public void clear()：空置线性表 public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false public int length():获取线性表中元素的个数 public T get(int i):读取并返回线性表中的第i个元素的值 public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。 public void insert(T t):向线性表中添加一个元素t public T remove(int i):删除并返回线性表中第i个数据元素。 public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
成员变量	private T[] arr：存储元素的数组 private int N:当前线性表的长度

2、代码实现

public class SequenceCase<T> {

    /**
     * 存储线性表
     */
    public T[] arr;

    /**
     * 线性表元素个数
     */
    public int sequenceLength;

    public SequenceCase(int capacity) {
        arr = (T[]) new Object[capacity];
        sequenceLength = 0;
    }

    /**
     * 插入元素
     * @param name
     */
    public void insert(T name){
        if(sequenceLength == arr.length){
            throw new RuntimeException("线性表已满");
        }
        arr[sequenceLength++] = name;
    }

    /**
     * 指定索引插入元素
     * @param i
     * @param name
     */
    public void insert(int i, T name){
        if (i == arr.length){
            throw new RuntimeException("当前表已满");
        }
        if (i < 0 || i > sequenceLength){
            throw new RuntimeException("插入的位置不合法");
        }
        for (int j = sequenceLength; j > i; j--) {
            arr[j] = arr[j-1];
        }
        arr[i] = name;
        sequenceLength++;
    }

    /**
     * 根据索引删除元素
     * @param i
     */
    public T remove(int i){
        if (i < 0 || i > sequenceLength-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        T t = arr[i];
        for (int j = i; j < sequenceLength; j++) {
            arr[j] = arr[j+1];
        }
        sequenceLength--;
        return t;
    }

    /**
     * 清空整个线性表
     */
    public void clear(){
        sequenceLength = 0;
    }

    /**
     * 线性表是否为空
     * @return
     */
    public boolean isEmpty(){
        return 0 == sequenceLength;
    }

    /**
     * 获取线性表的长度
     * @return
     */
    public int getSequenceLength(){
        return sequenceLength;
    }

    /**
     * 根据索引查询线性表
     * @param i
     * @return
     */
    public T getNameByIndex(int i){
        if(0 > i || i > sequenceLength){
            throw new RuntimeException("未存在该元素");
        }
        return arr[i];
    }

    /**
     * 获取线性表首次出现的序列号
     * @param t
     * @return
     */
    public int indexOf(T t){
        for (int i = 0; i < sequenceLength; i++) {
            if (t.equals(arr[i])){
                return i;
            }
        }
        return -1;
    }
}

public class SequenceCaseTest {
    public static void main(String[] args) {
        SequenceCase<String> aCase = new SequenceCase<>(10);
        aCase.insert("yhx");
        aCase.insert("xiaobear");
        aCase.insert("lwh");
        aCase.insert("xiaohuahua");
        aCase.insert(2,"love");
        String nameByIndex = aCase.getNameByIndex(2);
        System.out.println("索引2的名字为：" + nameByIndex);
        String remove = aCase.remove(2);
        System.out.println("删除索引2的元素名称为：" + remove);
        //清空操作
        aCase.clear();
        System.out.println("线性表长度为：" + aCase.getSequenceLength());
    }
}

2、顺序表的遍历

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

• 让SequenceList实现Iterable接口，重写iterator方法；
• 在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；

public class SequenceCase<T> implements Iterable<T>{
        private class SequenceIterator implements Iterator{

        private int temp;

        //遍历从0开始
        public SequenceIterator() {
            this.temp = 0;
        }

        @Override
        public boolean hasNext() {
            return temp < sequenceLength;
        }

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

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

3、顺序表的扩容

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

1、添加元素

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

2、删除元素

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

/**
     * 重置线性表大小
     * @param newSize
     */
public void resize(int newSize){
    T[] temp = arr;
    arr = (T[]) new Object[newSize];
    for (int i = 0; i < temp.length; i++) {
        arr[i] = temp[i];
    }
}

添加元素时：

/**
     * 指定索引插入元素
     * @param i
     * @param name
     */
public void insert(int i, T name){
    if (i == arr.length){
        resize(arr.length*2);
    }
    if (i < 0 || i > sequenceLength){
        throw new RuntimeException("插入的位置不合法");
    }
    for (int j = sequenceLength; j > i; j--) {
        arr[j] = arr[j-1];
    }
    arr[i] = name;
    sequenceLength++;
}

删除元素时：

/**
     * 根据索引删除元素
     * @param i
     */
public T remove(int i){
    if (i < 0 || i > sequenceLength-1){
        throw new RuntimeException("当前要删除的元素不存在");
    }
    T t = arr[i];
    for (int j = i; j < sequenceLength; j++) {
        arr[j] = arr[j+1];
    }
    sequenceLength--;
    //当线性表元素不足数组的1/4时，重置数组元素大小
    if(0 < sequenceLength && sequenceLength < arr.length/4){
        resize(arr.length/2);
    }
    return t;
}

4、顺序表的时间复杂度

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

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

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

• 由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显