一文搞懂线性表(搞透链表、顺序表)

前言

通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解解分享给大家。

其实说实话，可能很多人依然分不清线性表，顺序表，和链表之间的区别和联系！

• 线性表：逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。
• 顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。

在Java中，大家都知道List接口类型，这就是逻辑结构，因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的，然后一个get，set，add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。

下面用一个图来浅析线性表的关系。可能有些不太确切，但是其中可以参考，并且后面也会根据这个图举例。

线性表基本架构

对于一个线性表来说。不管它的具体实现如何，但是它们的方法函数名和实现效果应该一致(即使用方法相同、达成逻辑上效果相同，差别的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分相似。最著名的就是List的Arraylist和LinkedList，List是一种逻辑上的结构，表示这种结构为线性表，而ArrayList，LinkedList更多的是一种物理结构(数组和链表)。

所以基于面向对象的编程思维，我们可以将线性表写成一个接口，而具体实现的顺序表和链表的类可以实现这个线性表的方法，提高程序的可读性，还有一点比较重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步，我们应当采用泛型来实现更合理。至于接口的具体设计如下：

package LinerList;
public interface ListInterface<T> {    
    void Init(int initsize);//初始化表
    int length();
    boolean isEmpty();//是否为空
    int ElemIndex(T t);//找到编号
    T getElem(int index) throws Exception;//根据index获取数据
    void add(int index,T t) throws Exception;//根据index插入数据
    void delete(int index) throws Exception;
    void add(T t) throws Exception;//尾部插入
    void set(int index,T t) throws Exception;
    String toString();//转成String输出    
}

顺序表

顺序表是基于数组实现的，所以所有实现需要基于数组特性。对于顺序表的结构应该有一个存储数据的数组data和有效使用长度length.

还有需要注意的是初始化数组的大小，你可以固定大小，但是笔者为了可用性如果内存不够将扩大二倍。

下面着重讲解一些初学者容易混淆的概念和方法实现。这里把顺序表比作一队坐在板凳上的人。

插入操作

add(int index,T t)

其中index为插入的编号位置，t为插入的数据，插入的流程为：

(1)从后(最后一个有数据位)向前到index依次后移一位，腾出index位置的空间

(2)将待插入数据赋值到index位置上，完成插入操作

可以看得出如果顺序表很长，在靠前的地方如果插入效率比较低(插入时间复杂度为O(n))，如果频繁的插入那么复杂度挺高的。

删除操作

同理，删除也是非常占用资源的。原理和插入类似，删除index位置的操作就是从index+1开始向后依次将数据赋值到前面位置上，具体可以看这张图：

代码实现

这里我实现一个顺序表给大家作为参考学习：

package LinerList;

public class seqlist<T> implements ListInterface<T> {
    private Object[] date;//数组存放数据
    private int lenth;
    public seqlist() {//初始大小默认为10
        Init(10);
    }

    public void Init(int initsize) {//初始化
        this.date=new Object[initsize];
        lenth=0;        
    }
    public int length() {        
        return this.lenth;
    }

    public boolean isEmpty() {//是否为空
        if(this.lenth==0)
            return true;
        return false;
    }

    /*
     * * @param t    
     * 返回相等结果，为-1为false
     */
    public int ElemIndex(T t) {
        // TODO Auto-generated method stub
        for(int i=0;i<date.length;i++)
        {
            if(date[i].equals(t))
            {
                return i;
            }
        }
        return -1;
    }

    /*
     *获得第几个元素
     */
    public T getElem(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        return (T) date[index];
    }

    public void add(T t) throws Exception {//尾部插入
         add(lenth,t);
    }

    /*
     *根据编号插入
     */
    public void add(int index, T t) throws Exception {
        if(index<0||index>lenth)
            throw new Exception("数值越界");
        if (lenth==date.length)//扩容
        {
            Object newdate[]= new Object[lenth*2];
            for(int i=0;i<lenth;i++)
            {
                newdate[i]=date[i];
            }
            date=newdate;
        }
        for(int i=lenth-1;i>=index;i--)//后面元素后移动
        {
            date[i+1]=date[i];
        }
        date[index]=t;//插入元素
        lenth++;//顺序表长度+1

    }

    public void delete(int index) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        for(int i=index;i<lenth;i++)//index之后元素前移动
        {
            date[i]=date[i+1];
        }
        lenth--;//长度-1    
    }