一、线性表、顺序表和双向链表的区别

线性表是具有相同数据类型的n(n>0)个数据元素的有限序列。线性表的顺序存储结构就是顺序表，链式存储结构就是链表，链表又包括单向链表、双向链表、循环链表、静态链表等。

顺序表可以实现随机访问，随机存取，占用连续的存储空间，空间利用率较高，但是顺序表的插删，需要移动多个元素。

链表只能顺序访问，占用额外的存储空间存储元素间的关系，空间利用率更低，存储空间不一定连续，但是链表的插删不需要移动多个元素。

双向链表解决了单向链表只能从前向后遍历，实现了可以通过某结点访问它的直接前驱、直接后继。

线性表是一种抽象的数据类型，表中的元素的数据类型相同，首结点没有前驱结点，只有一个后继结点，尾结点没有后继结点，只有一个前驱结点，其它结点只有一个前驱和一个后继结点。

顺序表指的是线性表用顺序存储方式（一般用数组）保存。

双向链表指的是线性表用双向链表的方式存储。

延伸阅读：

二、线性表基本架构

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

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

package LinerList;

public interface ListInterface {   

    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输出   

}

上一篇

linkedlist为什么用双向链表?

下一篇

数据结构s-＞较好是什么意思?