线性表的结构特点主要表现在两个方面：一是均匀性，虽然不同数据表的数据元素可以是各式各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。二是有序性，各数据元素在线性表中按序排列，数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其他元素前面均只有一个数据元素（直接前驱）且后面均只有一个数据元素（直接后继）。

  在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。栈、队列是线性表的特殊情况，是受限的线性结构，只是在数据结构的操作上有区别，在存储结构方面和线性表一样。

  线性表的顺序存储结构如图2.8所示。

图2.8 线性表的顺序存储结构

  线性表的链式存储有三种形式：单链表、循环链表和双向链表。

• 单链表

  在单链表中，每个节点都包含指向下一个节点的指针，最后一个节点的指针为空，以标记是最后一个节点。之所以称为单链表是因为每个节点只存在一个节点指针，所以只能依次顺序访问下一个节点，访问完某节点之后再想往回查找是不可以的。为了记住单链表的第一个位置，可以定义一个头指针。单链表的链式存储结构如图2.7所示。

• 循环链表

  在单链表的基础上，可以让最后一个节点的指针指向第一个节点，这样循环起来形成的链表即为循环链表。循环列表可以顺序访问下一个节点，访问完某节点之后可以通过下一个循环再次访问到该节点。为了记住单链表的第一个位置和最后一个位置，可以定义一个头指针和一个尾指针。循环链表的链式存储结构如图2.9所示。

图2.9 循环链表

• 双向链表

  双向链表比单链表多出了一个节点指针，用来指向前一个节点的数据，这样做的好处是避免了寻找前面节点时发生的不便之举。双向链表的链式存储结构如图2.10所示。

图2.10 双向链表

  通过对线性结构的分析，可得到如下结论：对线性结构的主要操作有查找线性结构中某个信息、修改线性结构中某个信息、在固定的位置插入和删除相应的信息等，即查询、插入、删除、修改等相关操作。接下来以面向接口编程的方式，定义一个线性表接口，该接口具有如下基本操作。

  （2）删除数据元素。

  （3）替换数据元素。

  （4）获取数据元素。

  （5）获取线性表中数据元素个数。

  （6）判断线性表是否为空。

  下面是线性表接口的代码：

  接下来用顺序存储结构的数组，来存储线性表的逻辑结构，同时实现上面定义的List接口。请认真阅读该段代码，细节部分已通过注释加以描述，具体代码如下：

    final int defaultSize = 10;               //默认线性表长度       
    int maxSize;                                    //线性表长度
    int size;                                           //线性表中现有元素个数
    Object[] listArray;                          //用对象数组存储线性表
    //无参构造方法
    SeqList(){
        initiate(defaultSize);
    }
    //带线性表长度的构造方法
    SeqList(int size){
        initiate(size);
    }
    //初始化方法，设置线性表长度、现有元素个数和初始化对象数组（用线性表长度）
    public void initiate(int sz){
        maxSize = sz;
        size = 0;
        listArray = new Object[sz];
    }
    //实现在指定下标位置插入数据元素
    public void insert(int i,Object obj) throws Exception{                 
        if (size == maxSize){
            throw new Exception("线性表已满，无法插入！");
        }
        //只允许在现有线性表数据元素之前或之后插入，不允许隔着一个空位置之后插入数据元素
        if (i > size){
            throw new Exception("插入下标位置错误！");
        }
        //将插入位置后的数据元素全部后移   
        for(int j = size; j > i; j--){
            listArray[j] = listArray[j-1];
        }
        //插入数据元素，并增加线性表中现有元素个数
        listArray[i] = obj;
        size++; 
    }
    //实现删除指定下标位置的数据元素
    public Object delete(int i) throws Exception{            
        if(size == 0){
            throw new Exception("线性表已空，无法删除！");
        }
        if (i > size-1){
            throw new Exception("删除下标位置错误！");
        }
        //获得被删除的数据元素
        Object it = listArray[i];
        for(int j = i; j < size-1; j++){
            listArray[j] = listArray[j+1]; 
        }
        //返回被删除数据元素，并减少线性表中现有元素个数        
        size--;
        return it;     
    }
    //实现替换指定下标位置的数据元素
    public void update(int i, Object obj) throws Exception{              
        if(size == 0){
            throw new Exception("线性表已空，无法替换！");
        }
        if (i > size-1){
            throw new Exception("替换下标位置错误！");
        }
        //替换指定下标的数据元素
        listArray[i] = obj;         
    }
    //实现获取指定下标位置的数据元素
    public Object getData(int i) throws Exception{                  
        if(size == 0){
            throw new Exception("线性表已空，无法获取！");
        }
        if(i >= size){
            throw new Exception("获得下标位置错误！");
        }
        return listArray[i];
    }
    //实现获取线性表数据元素个数
    public int size(){
        return size;
    }
    //实现判断线性表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
}

  上述代码中，关于插入位置i和线性表中现有元素个数size的比较非常细致，也正确体现了线性表的特性，需要认真理解。例如在实现在指定下标位置插入数据元素的代码中，if(i > size){…}这行判断语句，可以理解为如果线性表中现有3个数据元素，即size值为3，则只允许在下标为0、1、2、3这四个位置（其中下标为3的这个位置是第一个空着的位置）插入数据元素，不允许让下标为3的位置空着，在下标大于3的位置插入数据元素。

  栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读取数据的时候是从栈顶开始弹出数据（最后一个进入的数据被第一个读出来）。

  仍然以面向接口编程的方式，定义一个栈接口，该接口具有如下基本操作。

  （1）把数据元素压入栈—进栈。

  （2）获取并删除栈顶数据元素—退栈。

  （3）获取但不删除栈顶数据元素。

  （4）判断栈是否为空。

  接下来仍然用顺序存储结构的数组来存储栈的逻辑结构，同时实现上面定义的Stack接口，具体代码如下：

public class SeqStack implements Stack{
    final int defaultSize = 10;
    int top;//标记栈内元素个数，即栈顶元素
    Object[] stack;
    int maxStackSize;
    public SeqStack(){
        initiate(defaultSize);
    }       
    public SeqStack(int sz){
        initiate(sz);
    }       
    private void initiate(int sz){
        maxStackSize = sz;
        top = 0;
        stack = new Object[sz];
    }
    //实现把数据元素压入栈—进栈       
    public void push(Object obj) throws Exception{
        if(top == maxStackSize){
            throw new Exception("堆栈已满！");
        }
        //进栈，栈顶标记加1
        stack[top] = obj;
        top++;
    }
    //实现获取并删除栈顶数据元素—退栈
    public Object pop() throws Exception{
        if(top == 0){
            throw new Exception("堆栈已空！");
        }
        //返回退栈数据元素，栈顶标记减1实现删除（实际并未删除）
        top--;
        return stack[top];
    }
    //实现获取但不删除栈顶数据元素
    public Object getTop() throws Exception{
        if(top == 0){
            throw new Exception("堆栈已空！");
        }
        return stack[top - 1];
    }
    //实现判断栈是否为空
    public boolean notEmpty(){
        return (top > 0);
    }
}

  该段代码比较简单，唯一需要注意的是在实现获取并删除栈顶数据元素—退栈的操作时，并没有真正删除该数据元素，而是通过top栈顶标记减1实现删除的。

  接下来的程序演示了如何使用栈这样的数据结构，具体代码如下：

  编译、运行程序，程序运行结果如图2.11所示。

图2.11 栈结构的使用

  队列也是一种特殊的线性结构，它只允许在该结构的前端进行删除操作，在后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

  在队列这种数据结构中，最先插入的元素将是最先被删除的元素，反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”的线性结构。

  接下来定义一个队列接口，该接口具有如下基本操作。

  （1）把数据元素插入队列尾部—入队。

  （2）获取并删除队列头部数据元素—出队。

  （3）获取但不删除队列头部数据元素。

  （4）判断队列是否为空。

  下面是队列接口的代码：

public interface Queue{
    //把数据元素插入队列尾部—入队
    public void EnQueue(Object obj) throws Exception;
    //获取并删除队列头部数据元素—出队
    public Object DeQueue() throws Exception;
    //获取但不删除队列头部数据元素
    public Object QueueFront() throws Exception;
    //判断队列是否为空
    public boolean notEmpty();