线性表（Linear List） 原

1、特点

线性表是我们日常工作中最简单也是最常用的一种数据结构。 它有如下特点： 每个数据元素最多只能有一个直接前趋。 每个数据元素最多只能有一个直接后继。 只有第一个数据元素没有直接前趋。 只有最后一个数据元素没有直接后继。

2、定义

1．一般定义

线性表是n个类型相同数据元素的有限序列，一般描述为：A=(a1,a2,…ai…,an-1) A：线性表的名称。 ai（n≥i≥1）：称为线性表的数据元素。描述的是一组相同属性的数据。 n：表示线性表中包含的数据元素个数，也称为线性表的长度。当n等于0时，表示线性表为空表。

在线性表的相邻数据元素之间存在着序偶关系。

唯一没有直接前趋的元素一端称为表头。唯一没有后继的元素一端称为表尾。

在非空的线性表中每个数据元素在线性表中都有唯一确定的序号。数据元素序号的范围是[0，n-1]

2．离散定义

线性表的离散定义：B=<A,R> A：包含n个结点。 R：包含一个线性关系。

线性表中包含的数据元素个数为线性表的长度。

一个数据元素通常包含多个数据项，此时每个数据元素称为记录，含有大量的记录的线性表称为文件。

3．ADT定义

线性表是一个比较灵活的数据结构，它的长度根据需要增加或缩短，也可以对线性表的数据元素进行不同的操作，比如：访问数据元素、插入、删除数据元素等。 如下是线性表的抽象数据类型定义：

ADT List{
数据对象:D={ai|ai∈元素集合，i=1,2,……,n,n≥0}
数据关系:R={<ai-1,ai>|ai-1,ai∈元素集合，i=1,2,……,n}
基本操作:
{
  public linklist()
  创建一个空的线性表。
  public linklist(Collection c)
  建立一个包含c中的数据以及数据顺序的线性表。
  public Object getFirst()
  返回线性表的第一个元素。
  public Object getLast()
  返回线性表的最后一个元素。
  public Object get(int index)
  获取线性表中index位置的元素。
  public Object removeFirst()
  删除第一个元素，并返回该值。
  public Object removeLast()
  删除最后一个元素，并返回该值。
  public boolean remove(Object o)
  将表中第一次出现的o元素删除，成功返回true。
  public void clear()
  删除表中所有元素。
  public Object remove(int index)
  删除表中index位置的元素。
  public void addFirst(Object o)
  将o插入表中开头位置。
  pubic void addLast(Object o)
  将o插入表中末尾位置。
  public boolean add(Object o)
  将o插入表的末尾，成功返回true
  public addAll(Collection c)
  将c中的数据依次插入到表末尾
  public addAll(int index,Collection c)
  将c中的数据从index位置开始依次插入，index及之后的数据顺位后移。
  public boolean set(int index,Object element)
  将o替代表中index位置的元素。
  public void add(int index,Object element)
  将element插入到线性表index位置之后。
  public boolean contains(Object o)
  检查o是否在链表中存在，如果存在返回true，如果不存在返回false。
  public int size()
  返回线性表的元素个数。
  public int indexOf(Object o)
  返回o在表中第一次出现的位置，若不窜在返回-1。
  public int lastIndexOf(Object o)
  返回o在表中最后一个出现的位置，若不存在返回-1。
  public ListIterator listIterator(int index)
  返回表中index位置开始的元素内容。
  }
}ADT List

3、分类

线性表的窜出结构分为顺序存储和非顺序存储。

1．顺序存储

其中顺序存储也称为向量存储或一维数组存储。 向量存储的结点存放的物理顺序与逻辑顺序完全一致。 线性表的第一个数据元素的位置通常称为起始位置或基地址。 线性表的这种机内表示称作线性表的顺序存储结构。 顺序存储结构实现的链表只有顺序表。

1>优点

顺序存储结构可以实现随机存取，可以直接取的数据元素，不需要移动元素。

2>缺点

插入和删除元素会造成大量的数据元素移动，消耗资源。 如果使用静态分配存储单元，还要预先占用连续的存储空间，造成空间浪费。

3>顺序表

①定义

使用顺序存储结构存储的线性表叫做顺序表。 顺序表中相邻的元素之间具有相邻的存储位置。 假设线性表的每个数据元素需占用K个存储单元，并以元素所占的第一个存储单元的地址作为数据元素的存储地址。则线性表中序号为i的数据元素的存储地址LOC(ai)与序号为i+1 的数据元素的存储地址LOC(ai+1)之间的关系为 LOC(ai+1) = LOC(ai) + K  通常来说，线性表的i号元素ai的存储地址为 LOC(ai) = LOC(a0) + i×K  其中LOC(a0)为0号元素a0的存储地址，通常称为线性表的起始地址。

②基本运算

顺序表容易实现线性表的某些操作，如随机存取第i个数据元素等，但是在插入或删除元素数据时，则比较繁琐，所以顺序表比较适合存取数据元素。

1)插入元素

用顺序表作为新兴表的存储结构时，必须保证数据存储的连续性，必须从要插入的位置的元素到最后一个元素整体向后平移，空出一个存储单元后，才能插入该元素。 对数据元素进行向后平移时，要从最后一个元素开始，否则会造成数据丢失。另外还应判断插入的位置是否超出范围，以及顺序表的容量是否超出。

2)删除元素

删除元素时，同样需要保证数据存储的连续性，必须从要删除的元素位置之后一个位置的元素开始到最后一个元素整体向前平移，直接覆盖要删除的元素即可。 对数据元素进行向前平移时，要从开始的位置开始移动，否则会造成数据丢失。另外这里需要判断删除的位置是否超出范围，或者删除的元素是否存在。以及元素个数是否为0。

3)显示所有元素

使用循环语句遍历打印即可，但是首先要判断表否是为空。

4)整体实现

/**
 * 使用数组实现一个顺序表
 * @author xh
 *
 */
public class SequenceList {

    private Object object[];//数组容器
    private int size;//元素个数
    //默认构造，默认大小16
    public SequenceList() {
        object=new Object[16];
        size=0;
    }
    public SequenceList(int len) {
        if(len <=0) {
            System.out.println("请输入大于0的整数！");
        }else{
            object=new Object[len];
            size=0;
        }
    }
    /**
     * 追加元素
     * @param o 要添加的元素
     * @return 添加成功返回true
     */
    public boolean add(Object o) {
        if(size>=object.length) {
            return false;
        }
        object[size]=o;
        size++;
        return true;
    }
    /**
     * 指定位置插入元素
     * @param index 插入的位置
     * @param o 插入的元素
     * @return 成功返回true
     */
    public boolean insert(int index, Object o) {
        if (index > object.length - 1 || index < 0) {
            System.out.println(index + "not exist");
            return false;
        } else {
            for(int i=size+1;i>index;i--) {
                object[i]=object[i-1];
            }
            object[index]=o;
            size++;
            return true;
        }
    }
    /**
     * 删除指定位置的元素
     * @param index 要删除的位置
     * @return 成功返回true
     */
    public boolean delete(int index) {
        if(index <0 || index >size) {
            System.out.println("输入的数据不合法！");
            return false;
        }else {
            for(int i=index;i<size;i++) {
                object[i]=object[i+1];
            }
            size--;
            return true;
        }
    }
    /**
     * 删除第一次出现的指定元素
     * @param o 要删除的元素
     * @return 成功返回true
     */
    public boolean delete(Object o) {
        int index=indexOf(o);
        return delete(index);
    }
    /**
     * 查找指定元素的位置
     * @param o 指定元素
     * @return 返回指定元素第一次出现的位置，如果不存在返回-1
     */
    public int indexOf(Object o) {
        if(o==null) {
            return -1;
        }else{
            for (int i=0;i<size;i++) {
                if(object[i].equals(o)) {
                    return i;
                }
            }
            return -1;
        }
    }
    public void print() {
        if(size==0) {
            System.out.println("()");
        }else {
            System.out.print("(");
            for(int i=0;i<size;i++) {
                System.out.print(object[i]+",");
            }
            System.out.print(")");
        }
    }
}

2．链式存储

链式存储只要逻辑结构是相邻的即可，不要求物理结构相邻。 使用链式存储结构实现的表有单向链表、循环链表、双链表。

1>优点

不要求物理相邻，不会造成空间浪费。 删除和插入不需要移动数据元素。

2>缺点

不能随机存取。

3>单向链表

①定义

单向链表（single linked list）的每个数据元素在存储单元中的存储形式如下：

其中，data是数据域，存放数据元素的值，next是指针域，存放相邻的下一个结点的地址。

单向链表是指结点中的指针域只有一个沿着同一方向表示的链式存储结构。 整个链表的存取必须从头指针开始，头指针指示链表中第一个结点的存储位置。 由于最后一个数据元素没有直接后继，则最后一个结点的指针为空（null）。 链表的第一个结点为链表的首结点。 链表的最后一个结点为链表的尾结点。 单链表的一个重要特性就是只能通过前趋结点找到后继结点，而无法从后继结点找到前趋结点。

②基本操作

1)插入元素

插入元素时需要完成以下三步： 1.创建一个新结点，并给新结点的数据域赋值。 2.将插入位置的前趋结点的指针域赋值给新插入的结点的指针域。 3.插入位置的前趋结点的指针域指向新插入的结点。 如下图：C为新插入的数据，先将C数据域赋值，然后将A结点的next域赋值给C的next域，然后将A的next域指向C，插入完成。

2)删除元素 删除过程是将当前结点的直接前趋结点的next域，指向当前结点的直接后继结点即可。 如下图：可以直接将B结点的next域赋值给A结点的next域即可。

删除结点只是将结点从链表中删除，该结点仍然存在，所以不能“丢失”被删除的结点的内存，需要将结点保留以便返回给空闲存储器，为便于将删除的结点返回，需要被删除的结点指针域赋值给临时的指针。

3)建立链表

因为单向链表的长度不固定，所以应采用动态建立单向链表的方法。动态建立单向链表的方法有两种，分别是：尾插入法和头插入法。

<1>尾插入法

该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针tail的开销，使其是中指向当前链表的尾结点。

<2>头插入法

如果在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来一下两个优点。 第一链表在第一个位置上的操作就和在表的其他位置上操作一致，无需进行特殊处理。 第二无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

4)查找运算

<1>按序号查找

链表的查找，只能从头开始，顺着指针域进行逐个查找，只能顺序存取，不能随机存取。

<2>按数值查找 从头开始，对比数值是否相同，如果相同则返回其存储位置，否则返回null。

5)求链表长度

求链表长度，基本和序号查找相同，从头开始挨个遍历计数。

4>循环链表

循环链表又称循环线性表，其结构基本同单向链表。 将单向链表的末尾结点的指针域指向第一个结点，逻辑上行程一个环形，该存储结构称之为单向循环链表。

优点 不增加任何空间的情况下能够已知任意几点的地址，可以找到链表中的所有结点。

缺点 查找前趋结点时，会增加时间开销。 如果已知条件为头结点会造成一下两种情况的时间开销： 1.删除末尾结点；2.在第一个结点前插入新结点。 使用末尾结点作为已知结点则可以解决以上两个问题。

为了防止循环链表的查询进入死循环，所以判断条件应该用curr.next()!=head。

5>双链表

①定义

在单链表的基础上，为每个结点增加一个直接前趋的指针域prior，这样形成的链表中有两条方向不同的链，故称为双向链表。其结点结构如下图：

element标书结点的数据。prev表示指针，指向该结点的直接前趋结点。next表示指针，指向该结点的直接后继结点。

②基本运算

双向链的运算类似于单向链。

1)插入结点

双向链插入结点基本和单向链相同，但是在插入的时候这里需要修改的指针增加了，单向链需要修改两个，而双项链则需要修改四个。

2)删除结点 双向链删除结点基本和单向链相同，但是在删除的时候修改的指针也增加了。单向链需要修改一个指针，双向链需要修改两个指针。

3)查询结点 查找和单向链是相同的。

6>双向循环链表

如果将双向链表头结点的前趋指针指向链表的最后一个结点，而末尾几点的后继指针指向第一个结点，此时所有结点连接起来也构成循环链表，称之为双向循环链表。 双向循环链表的各种算法与双向链表的算法大同小异，其区别于单链表和单循环链表的区别一样。

3．顺序存储结构和链式存储结构的比较

1>特点对比

①物理存储 顺序存储结构一般要求数据存放的物理和逻辑地址连续。是静态分配空间。 链式存储结构数据存放地址可连续可不连续。是动态分配空间。

②存储数据 顺序存储结构一般存储的都是定长的数据。 链式存储结构可以存储任何数据。

③算法 顺序存储结构是随机存取，链式存储结构为顺序存取。 顺序存储结构便于随机存取，链式存储结构便于增删。

2>使用选择

①基于空间的考虑 当线性表的长度变化较大，难于估计其存储规模时，采用动态链表作为存储结构较好。 如果存储规模较小，并且线性表的长度一般固定时，可以使用顺序存储。

②基于时间的考虑 若对线性表的操作主要是进行查找，很少做插入和删除，采用顺序存储结构较好。 如果在线性表中需要做较多的插入和删除，采用链式存储结构较好。

参考文献：《数据结构与算法分析 Java语言描述》、《数据结构与算法分析 Java语言描述第二版》、《数据结构与算法（Java语言版解密）》