线性表概述

1.        结构

线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。

2.        特征

1)        集合中必存在唯一的一个“第一元素”；

2)        集合中必存在唯一的一个 “最后元素” ；

3)        除最后一个元素之外，均有唯一的后继(后件)；

4)        除第一个元素之外，均有唯一的前驱(前件)。

常常将非空的线性表(n>0)记作：(a1，a2，…an)。数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

3.        结构特点

1)        均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

2)        有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。

4.        在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构如链表：优点：对于新增和删除操作add和remove和方便，不需要移动元素；缺点：不方便随机访问元素，LinkedList要移动指针

顺序存储结构如数组：优点：在于随机访问元素；缺点：插入和和删除的时候，需要移动大量的元素。