线性表

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

前驱元素：

	若A元素在B元素的前面，则称A为B的前驱元素

后继元素：

	若B元素在A元素的后面，则称B为A元素的后继元素

特征

数据元素之间有一对一的逻辑关系

第一个数据元素没有前驱，称为头结点
最后一个元素没有后继，这个元素称为尾节点
除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和后继

分类

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

顺序表

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

API实现

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

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

    //将一个线性表置为空表
    public void clear(){
        this.N=0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N==0;
    }

    //获取线性表的长度
    public int length(){
        return N;
    }

    //获取指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //向线型表中添加元素t
    public void insert(T t){
       
        eles[N++]=t;
    }

    //在i元素处插入元素t
    public void insert(int i,T t){
      

        //先把i索引处的元素及其后面的元素依次向后移动一位
        for(int index=N;index>i;index--){
            eles[index]=eles[index-1];
        }
        //再把t元素放到i索引处即可
        eles[i]=t;

        //元素个数+1
        N++;
    }

    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        //记录索引i处的值
        T current = eles[i];
        //索引i后面元素依次向前移动一位即可
        for(int index=i;index<N-1;index++){
            eles[index]=eles[index+1];
        }
        //元素个数-1
        N--;

     
        return current;
    }


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



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

    private class SIterator implements Iterator{
        private int cusor;
        public SIterator(){
            this.cusor=0;
        }
        @Override
        public boolean hasNext() {
            return cusor<N;
        }

        @Override
        public Object next() {
            return eles[cusor++];
        }
    }
}

测试

public class SequenceListTest {
    public static void main(String[] args) {
        //创建顺序表对象
        SequenceList<String> s1 = new SequenceList<String>(10);
        s1.insert("姚明");
        s1.insert("科比");
        s1.insert("麦迪");
        s1.insert(1,"詹姆斯");

        String  getResult = s1.get(1);
        System.out.println(getResult);

        String removeResult = s1.remove(1);
        System.out.println(removeResult);

        s1.clear();
        System.out.println(s1.length());
    }
}

顺序表的容量可变

public class SequenceListTest2 {
    public static void main(String[] args) {
        SequenceList<String> s1 = new SequenceList<>(3);
        s1.insert("张三");
        s1.insert("李四");
        s1.insert("王五");
        s1.insert("赵六");

    }
}

在创建数组时，我们初始化为3，当插入的元素大于三就会越界。

我们期望得到的是可变容量的数组，即在加入的元素超出初始值时，直接将容量扩充到二倍，当数据元素数量少于1/4时，则将容量缩减为当前的1/2

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

添加元素时：

public void insert(int i,T t){
    if (N==eles.length){
        resize(2*eles.length);
    }

    //先把i索引处的元素及其后面的元素依次向后移动一位
    for(int index=N;index>i;index--){
        eles[index]=eles[index-1];
    }
    //再把t元素放到i索引处即可
    eles[i]=t;

    //元素个数+1
    N++;
}

删除元素时

//删除指定位置i处的元素，并返回该元素
public T remove(int i){
    //记录索引i处的值
    T current = eles[i];
    //索引i后面元素依次向前移动一位即可
    for(int index=i;index<N-1;index++){
        eles[index]=eles[index+1];
    }
    //元素个数-1
    N--;

    if (N<eles.length/4){
        resize(eles.length/2);
    }
    
    return current;

}