线性表

线性表是最简单、最基本也是最常用的一种线性结构，它是具有相同特性的数据元素组成的一个有限序列。常采用顺序存储和链式存储，主要的基本操作是插入、删除以及查找。

特点：

线性表有且只有一个开始结点，这个元素被称为头结点
线性表有且只有一个末尾结点，这个元素被称为尾结点
除第一个元素外，序列中的其他元素均只有一个直接前驱
除最后一个元素外，序列中的其他元素均只有一个直接后继

分类：

线性表在存储结构上有顺序存储和链式存储两种方式。按照存储方式不同，可把线性表分为顺序表和链表。

1.顺序表

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

顺序表的优缺点：

优点：可以随机存取表中的元素。
缺点：插入和删除操作需要移动元素。

在插入前要移动元素以挪出空的存储单元，来放要插入的元素；删除也需要移动元素，来填充被删除的元素空出来的存储单元。

2.顺序表的实现

插入元素

增删改查是数据结构的核心操作，每种数据结构都要实现这几种最基本的操作。在顺序表中，如果要插入元素，则需要将插入位置后的所有元素依次向后移动，如下图所示：

注意：当顺序表已满时，表中元素无法向后移动，需要做出特别的处理（不插入，或者开辟更大的空间来存储这些元素）

删除元素

从顺序表中删除一个元素，当删除该元素后，需要将后面的元素依次向前移动来补充空位，删除过程如下：

整个创建顺序表、元素的插入删除查找以及顺序表的清空等基本功能，接下来测试一下这个顺序表的情况：

public class SequenceList<T> {

    //存储元素的数组
    private T[] array;
    //记录线性表中的元素个数，即线性表的长度
    private int N;
    //创建容量为capacity的SequenceList对象
    public SequenceList(int capacity) {
        //初始化数据
        this.array = (T[]) new Object[capacity];
        //初始化长度
        this.N = 0;
    }
    //清空线性表
    public void clear(){
        this.N = 0;
    }
    //判断线性表是否为空
    public boolean isEmpty(){
        return N == 0;
    }
    //获取线性表中的元素个数
    public int length(){
        return N;
    }
    //读取并返回线性表中的第 i 个元素
    public T get(int i){
        return array[i];
    }
    //插入元素（在顺序表的末尾插）
    public void insert(T t){
        array[N++] = t;
    }
    //在线性表的第 i 个元素之前插入一个值为 t 的元素
    public void insert(int i,T t){
        //将i索引及以后的元素依次向后移一位
        for (int j = N - 1;j > i;j--){
            array[j] = array[j - 1];
        }
        //将t元素放到i索引处
        array[i] = t;
    }
    //删除并返回线性表中的第 i 个元素
    public T remove(int i){
        //记录索引i处的值
        T current = array[i];
        //将索引 i 后面的元素依次向前移一位
        for (int j = i; j < N - 1; j++) {
            array[j] = array[j + 1];
        }
        N--;    //元素个数减一
        return current;
    }
    //返回线性表中首次出现的指定元素的位序号，不存在则返回-1
    public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if (array[i].equals(t)){
                return i;
            }
        }
        return -1;
    }

}

public class SequenceListTest {
    public static void main(String[] args) {
        SequenceList<String> sl = new SequenceList<String>(10);
        //  插入数据
        sl.insert("科比");
        sl.insert("乔丹");
        sl.insert("哈登");
        sl.insert(1,"库里");
        //获取元素
        String s = sl.get(1);
        System.out.println("索引处的元素为："+s);
        //删除元素
        String s1 = sl.remove(0);
        System.out.println("删除的元素为："+s1);
        //清空线性表
        sl.clear();
        System.out.println("线性表的长度为："+ sl.length());
    }
}