一、线性表的顺序存储结构

1.线性表（List）的定义

由零个或多个数据元素组成的有限序列，数据元素类型可以是基本类型，也可以是抽象类型class，把它想象成一个结点就行。

2. 线性表的顺序存储

顺序存储是由在内存当中一块连续的空间组成的，这块内存空间，在创建线性表时就需要确定大小，这一点刚好对应了java当中的数组，java创建一个数组，会返回一个引用，数组元素存于堆内存当中，是一块连续的空间，引用是存于栈当中，使用时push进栈。

顺序存储.png

3. 顺序存储的优势

存取速率快，时间复杂度为O(1)，因为数据元素存于地址连续的内存空间当中，每一个小结点，分配的大小是固定的，比如int分配8字节，那么很快可以根据存取的脚标计算出结点的位置。并且顺序存储不需要开辟空间去存储下一个结点的引用，节省了内存开销。

4.顺序存储的劣势

增删结点会有较多不便，想象一下，最好的情况是在线性表的最后一个结点进行增删，那么时间复杂度是O(1)，因为其他数据元素不需要进行位移。最糟糕的情况，在线性表的第一个结点进行增删，那么时间复杂度是O(n)，n被称作问题规模，简单理解为数据量，平均一下，时间复杂度也有(n+1)/2。

二、线性表的链式存储结构

1. 线性表的链式存储

这种方式底层不在是采用数组的方式，因为在链式存储方式下，相邻的两个数据元素存储的位置不在连续的内存空间，那如何体现线性表的有序呢？每个数据元素除了存储元素值以外，还需要额外开辟空间来存储指向下个数据元素的引用，这样就可以将不同结点链接起来。

链式存储.png

2.链式存储的优势

之前用顺序存储的模式，在进行增删的时候，只要不是最后一个结点，就会产生大量数据元素的位移，用链式存储可以很好的解决这个问题，因为链式存储只要修改一下引用的指向就可以了，不需要位移任何元素，时间复杂度为O(1)，但是这里有一点，就是遍历查找需要增删数据元素的复杂度，也为O(n)，但是对于批量增删来说，链式存储还是有很明显的优势的。并且链式存储不需要一开始就固定线性表的大小，即用即申请，非常方便。

3.链式存储的劣势

链式存储需要为每一个结点单独开辟一个内存空间来存储引用。并且由于每个数据元素存储的内存位置不是连续的，存取时遍历带来的时间复杂度为O(n)。

三、顺序存储的实现-java

import java.util.ArrayList;

public class MyArrayList {

    /**
     * 线性表反应的是若干数据元素之间的线性关系，与树不同，元素之间的关系都是一对一的
     * 线性表存在两种存储方式：顺序存储，链式存储
     */
    /**
     * 线性表一般具有以下功能：
     * 1.InitList(int Maxlenth) 初始化操作，建立一个空的线性表
     * 2.ListEmpty() 判断线性表是否为空，为空则返回true，非空返回false
     * 3.ClearList() 将线性表清空
     * 4.GetElem(int index) 返回位置index的元素
     * 5.LocateElem(T elem) 返回与给定elem值相等的元素，返回第一个相同值的脚标
     * 6.ListInsert(T elem) 在线性表末尾插入数据，不需要手动指定位置
     * 7.ListInsertWithIndex(int index,T elem) 在线性表脚标为index处插入新元素
     * 8.ListDelete(int index) 删除线性表脚标为index的元素，并返回其值
     * 9.ListLenth() 返回当前线性表的长度
     * 10.toString() 打印当前线性表的所有元素值，用逗号分隔
     */

    /**
     * 使用顺序存储的方式来实现一个线性表，即java数组。
     */
    int MaxLenth; //定义该线性表最大存储空间
    int Currlength = 0; //定义该线性表当前大小
    int[] myArrayList = null;

    //实现InitList功能
    public MyArrayList(int Maxlenth){
        // 以整型数组为例
        myArrayList = new int[Maxlenth];
        this.MaxLenth = Maxlenth;
    }

    //实现ListEmpty功能
    public Boolean ListEmpty(){
        return Currlength == 0?true:false;
    }

    //实现ClearList功能
    public int[] ClearList(){
        /**
         * java当中没有手动操作内存的API，不想C语言当中的指针，但是当一块内存没有引用
         * 指向时，就会开始等待GC（JVM的垃圾回收机制）
         */
        return new int[MaxLenth];
    }

    //实现GetElem的功能
    public int GetElem(int index){
        if (index < 0 || index >= Currlength){return -1;}
        else {return myArrayList[index];}
    }

    //实现LocateElem(T elem)功能
    public int LocateElem(int elem){
        for (int head = 0;head < Currlength;head++){
            if (myArrayList[head] == elem){return head;}
            else {continue;}
        }
        return -1;//返回-1表示未找到有与其对应的元素值
    }

    //实现ListInsert(int index,T elem)功能
    public Boolean ListInsert(int elem){
        if (Currlength == MaxLenth){return false;}
        myArrayList[Currlength++] = elem;
        return true;
    }

    //ListInsertWithIndex(int index,T elem)功能
    public Boolean ListInsertWithIndex(int index,int elem){
        /**
         * 插入操作会相对复杂一些，由于数组这种顺序结构，插入会导致
         * 被插元素后面的所有元素需要后移一位
         */
        if (Currlength == MaxLenth){return false;}

        if (Currlength == 0){myArrayList[0] = elem; Currlength++;return true;}

        for (int rear = Currlength;rear >= index;rear--){
                myArrayList[rear] = myArrayList[rear-1];
        }
        myArrayList[index] = elem;
        Currlength++;
        return true;
    }

    //实现ListDelete(int index)功能
    public int ListDelete(int index){
        /**
         * 与插入操作相反，删除操作需要将被删元素后面所有元素都向前移一位
         */
        if (Currlength == 0 ){return -1;}
        int returnTempElem = -1;
        for (int start = index;index < Currlength;index++){
            returnTempElem = myArrayList[index];
            myArrayList[index] = myArrayList[index+1];
        }
        Currlength--;
        return returnTempElem;
    }

    //实现ListLenth()的功能
    public int ListLenth(){
        return Currlength;
    }

    //实现toString方法
    public String toString(){
        StringBuffer returnTempString = new StringBuffer();
        for (int start = 0;start<Currlength;start++){
            if (start != Currlength-1){
                returnTempString.append(myArrayList[start] + ",");
            }else {
                returnTempString.append(myArrayList[start]);
            }
        }
        return returnTempString.toString();
    }

    public static void main(String[] args) {
    }
}

四、链式存储的实现-java

public class MyLinkedList {
    /**
     * 线性表反应的是若干数据元素之间的线性关系，与树不同，元素之间的关系都是一对一的
     * 线性表存在两种存储方式：顺序存储，链式存储
     */
    /**
     * 线性表一般具有以下功能：
     * 1.InitList() 初始化操作，建立一个空的线性表
     * 2.LinkedListEmpty() 判断线性表是否为空，为空则返回true，非空返回false
     * 3.ClearLinkedList() 将线性表清空
     * 4.GetLinkedElem(int index) 返回位置index的元素
     * 5.LocateLinkedElem(T elem) 返回与给定elem值相等的元素，返回第一个相同值的脚标
     * 6.LinkedListInsert(T elem) 在线性表末尾插入数据，不需要手动指定位置
     * 7.LinkedListInsertWithIndex(int index,T elem) 在线性表脚标为index处插入新元素
     * 8.LinkedListDelete(int index) 删除线性表脚标为index的元素，并返回其值
     * 9.LinkedListLenth() 返回当前线性表的长度
     * 10.toString() 打印当前线性表的所有元素值，用逗号分隔
     */

    /**
     * 使用链式存储的方式来实现一个线性表
     */
    private int CurrLenth = 0; //线性表的大小
    private LinkedNode headNode = null; // 头结点
    private LinkedNode rear = null; //尾指针，方便线性表尾部的操作

    class LinkedNode{
        String nodeData; //存储节点数据
        LinkedNode next; //存储指向下一个节点的位置
    }

    public MyLinkedList(){
        /**
         * 初始化一个链式存储的线性表，生成头结点，尾指针
         */
        this.headNode = new LinkedNode();
        headNode.nodeData = null; //头结点的数据域不需要存储数据
        headNode.next = null; //初始化一个链式存储的线性表，由于没有第一个结点，所以头结点的next为空
        this.rear = headNode; //将尾部指针指向头结点
    }

    //实现LinkedListEmpty的功能
    public Boolean LinkedListEmpty(){
        //头结点默认不算长度
        return CurrLenth == 0?true:false;
    }

    //实现ClearLinkedList的功能
    public Boolean ClearLinkedList(){
        /**
         * 由于java不能手动释放内存占用，只能依靠GC机制，所以这边需要循环
         * 将每个指向结点的引用置为空，这样当一块内存没有引用指向时，JVM
         * 会自动回收。
         */
        if (CurrLenth == 0){return true;} //空链表，直接返回true
        LinkedNode index = headNode.next; //该游标作用是保存释放结点前,存放该结点的指针域数据
        LinkedNode currIndex = headNode.next; //该游标作用是指向待释放结点对象
//        headNode.next = null; //释放头结点对一个结点的链接
        if (CurrLenth == 1){
            //表示只有一个结点时
            index = null;
            currIndex = null;
            headNode.next = null;
            // 释放完以后的初始化操作
            CurrLenth = 0;
            rear = headNode;
            return true;
        }
        for (;index.next != null;){
            index = currIndex.next;
            currIndex.next = null;
            currIndex = index;
        }
        // 释放临时游标指针
        index = null;
        currIndex = null;
        // 释放头结点链接
        headNode.next = null;
        // 释放完以后的初始化操作
        CurrLenth = 0;
        rear = headNode;
        return true;
    }

    //实现GetLinkedElem的功能
    public String GetLinkedElem(int index){
        if (index <= 0 || index > CurrLenth){return "error";}
        // 假设头结点为index=0，第一个结点index=1
        LinkedNode currIndex = headNode.next;
        for (int curr = 1;curr <= index;curr++,currIndex = currIndex.next){
            if (curr == index){
                return currIndex.nodeData;
            }else{
                continue;
            }
        }
        return "error";
    }

    //实现LocateLinkedElem的功能
    public int LocateLinkedElem(String elem){
        if (CurrLenth == 0){return -1;}
        LinkedNode start = headNode.next;
        int index = 1;
        for(;start != null;start = start.next,index++){
            if (start.nodeData.equals(elem)){return index;}
            else{
                continue;
            }
        }
        return -1;
    }


    //实现LinkedListInsert的功能
    public Boolean LinkedListInsert(String elem){
        /**
         * 要插入一个新的结点，需要考虑什么，跟顺序存储不同，链式存储可以称得上有
         * 无限空间，除非堆内存溢出了，所以不需要判断是否空间不足
         */
        try{
            LinkedNode linkedNode = new LinkedNode();
            linkedNode.nodeData = elem;
            if (headNode.next == null){
                // 头结点为空，表示插入的是第一个结点
                headNode.next = linkedNode;
                rear = linkedNode;
                CurrLenth++;
                return true;
            }else{
                rear.next = linkedNode; //让尾指针指向下一个结点，即将该结点放于线性表最后的位置
                linkedNode.next = null;
                rear = rear.next;
                CurrLenth++;
                return true;
            }
        }catch(Exception e){
            System.out.println("Add LinkedNode Find unknow Error!"+e);
            return false;
        }
    }

    //实现LinkedListInsertWithIndex功能
    public Boolean LinkedListInsertWithIndex(int index,String elem){
        if (index <= 0 || index > CurrLenth+1){
            // 当index = CurrLenth+1时，表示需要插入到链表尾部
            return false;
        }
        int currIndex = 1; //当前脚标
        LinkedNode currNode = headNode.next;
        LinkedNode insertNode = null; //待插入的结点
        if (index == 1){
            // 表示要插入到头结点后面的第一个结点，需要修改头结点
            insertNode = new LinkedNode();
            insertNode.nodeData = elem;
            insertNode.next = currNode;
            headNode.next = insertNode;
            CurrLenth++;
            return true;
        }
        if (index == CurrLenth+1){
            //表示是插入最后结点后面的位置，这种情况需要修改尾指针
            insertNode = new LinkedNode();
            rear.next = insertNode;
            insertNode.nodeData = elem;
            insertNode.next = null;
            rear = insertNode;
            CurrLenth++;
            return true;
        }
        while (currIndex != index-1){
            // 主要是遍历出要插入的前一个结点所处的位置
            currIndex++;
            currNode = currNode.next;
        }
        LinkedNode nextNode = currNode.next;
        insertNode = new LinkedNode();
        insertNode.nodeData = elem;
        currNode.next = insertNode;
        insertNode.next = nextNode;
        CurrLenth++;
        return true;
    }

    //实现LinkedListDelete功能
    public String LinkedListDelete(int index){
        if (index <=0 || index > CurrLenth){return "error";}
        int currIndex = 1;
        LinkedNode currNode = headNode.next;
        LinkedNode realseNode = null; //待释放的结点
        String returnString = null; //待返回的字符串
        if (index == 1){
            // 表示要删除头结点后面的位置，操作特殊，需要修改头结点指针域
            if (headNode.next.next != null){
                // 说明链表不止一个结点，删除第一个结点，不需要修改尾指针
                returnString = currNode.nodeData;
                realseNode = currNode;
                headNode.next = currNode.next;
                realseNode.next = null;
                CurrLenth--;
                return returnString;
            }else {
                returnString = currNode.nodeData;
                currNode.next = null;
                headNode.next = null;
                rear = headNode;
                CurrLenth--;
                return returnString;
            }
        }
        while (currIndex != index-1){
            currIndex++;
            currNode = currNode.next;
        }
        if (currIndex+1 == CurrLenth){
            // 表示删除的是最后一个结点，所以需要修改尾指针
            rear = currNode; // 首先将尾指针指向即将删除的尾结点的前一个结点
            realseNode = currNode.next;
            returnString = realseNode.nodeData;
            currNode.next = null;
            realseNode.next = null;
            CurrLenth--;
            return returnString;
        }else{
            realseNode = currNode.next;
            returnString = realseNode.nodeData;
            currNode.next = realseNode.next;
            realseNode.next = null;
            CurrLenth--;
            return returnString;
        }
    }

    //实现LinkedListLenth的功能
    public int LinkedListLenth(){
        return  CurrLenth;
    }

    //实现toString的功能
    public String toString(){
        StringBuffer stringBuffer = new StringBuffer();
        if (headNode.next == null){return "";} //表示是空链表
        if (headNode.next != null && headNode.next.next == null){
            // 表示该线性表只存在一个结点
            return headNode.next.nodeData;
        }
        for (LinkedNode start = headNode.next;start != null;start = start.next){
            if (start.next == null){
                //表示是最后一个结点
                stringBuffer.append(start.nodeData);
            }else{
                stringBuffer.append(start.nodeData+",");
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.LinkedListInsert("Hello");
        myLinkedList.LinkedListInsert("world");

        myLinkedList.LinkedListDelete(1);

        System.out.println(myLinkedList.toString());

//        System.out.println(myLinkedList.toString()); // Hello,world
//        System.out.println(myLinkedList.LinkedListEmpty()); //false
//        System.out.println(myLinkedList.LinkedListLenth()); // 2
//        myLinkedList.ClearLinkedList();
//        System.out.println(myLinkedList.toString()); // 为空
//        System.out.println(myLinkedList.GetLinkedElem(1)); // hello
//        System.out.println(myLinkedList.GetLinkedElem(2)); // world
//        System.out.println(myLinkedList.GetLinkedElem(3));  // error
//        System.out.println(myLinkedList.GetLinkedElem(-1)); // error
//        System.out.println(myLinkedList.LocateLinkedElem("Hello")); // 1
//        System.out.println(myLinkedList.LocateLinkedElem("world")); // 2
//        System.out.println(myLinkedList.LocateLinkedElem("world1")); // -1
//        myLinkedList.LinkedListInsertWithIndex(2,"insert");
//        System.out.println(myLinkedList.toString()); // Hello,insert,world
//
//        myLinkedList.LinkedListInsertWithIndex(1,"start");
//        System.out.println(myLinkedList.toString()); // start,Hello,insert,world
//
//        myLinkedList.LinkedListInsertWithIndex(5,"end");
//        System.out.println(myLinkedList.toString()); // start,Hello,insert,world,end
//
//        myLinkedList.LinkedListInsertWithIndex(7,"error");
//        System.out.println(myLinkedList.toString()); // start,Hello,insert,world,end

//        myLinkedList.LinkedListDelete(1);
//        System.out.println(myLinkedList.toString()); // Hello
//
//        myLinkedList.LinkedListDelete(0);
//        System.out.println(myLinkedList.toString()); // Hello
    }

}

五、两种存储方式时间复杂度分析

	最好情况时间复杂度	最差情况时间复杂度	平均时间复杂度
顺序存储的存取	O(1)	O(1)	O(1)
顺序存储的增删	O(1)	O(n)	O((n+1)/2)=O(n)
链式存储的存取	O(1)	O(n)	O((n+1)/2)=O(n)
链式存储的增删(去除遍历的开销)	O(1)	O(1)	O(1)

所以综合来讲，顺序存储的方式适合多存取，少增删，并且能够确定线性表大小的场景。链式存储适合多增删，少存取，无法确定线性表大小的场景。

代码进行过简单的校验，如果存在bug，望私信指正！