顺序表和链表存储表示线性表的优缺点

线性表是最基本、最简单、也是最常用的一种。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。

线性表具有如下的结构特点：

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

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

    顺序存储表示是将数据元素存放于一个连续的存储空间中，它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充，容易造成存储空间浪费。同时，在插入或删除时，为了保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。
    链式存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。

1 顺序表VS链表的时间性能比较

        所谓时间性能是指实现基于这种存储结构的基本运算（即算法）的时间复杂度。

        像取出线性表中第 i 个元素这样的按位置随机访问的操作，使用顺序表更快一些；取前趋和后继结点的操作在顺序表中可以很容易调整当前的位置向前或向后，因此这两种操作的时间为 Ｏ (1) ；相比之下，单链表不能直接访问上述的元素，按位置访问只能从表头开始，直到找到那个特定的位置，所需要的平均时间为 Ｏ ( n ) 。

        给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为 Ｏ （ 1 ），而顺序表进行插入和删除操作需移动近乎表长一半的元素，需要的平均时间为 Ｏ ( n ) 。这在线性表中元素个数较多时，特别是当每个元素占用的空间较多时，移动元素的时间开销很大。对于许多应用，插入和删除是最主要的操作，因此它们的时间效率是举足轻重的，仅就这个原因而言，链表经常比顺序表更好。

        作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作时，则宜采用链表做存储结构。

2 顺序表和链表的空间性能比较

        所谓空间性能是指这种存储结构所占用的存储空间的大小。

        顺序表中每个元素的存储密度为 1 ，没有浪费空间；而链表的每个结点除了存放数据元素，还要附加一个指示元素之间逻辑关系的指针，如果数据域占据的空间较小，则链表的结构性开销就占去了整个存储空间的大部分，因而从结点的存储密度上讲，顺序表的存储空间利用率较高。

       由于顺序表需要预分配一定长度的存储空间，如果事先不能明确知道线性表的大致长度，则有可能对存储空间预分配得过大，致使在程序执行过程中很大一部分的存储空间得不到充分利用，而造成浪费；若估计得过小，又将造成频繁地进行存储空间的再分配。而链表的显著优点之一就是其存储分配的灵活性，不需要为链表预分配空间，只要有可用的内存空间分配，链表中的元素个数就没有限制。

      作为一般规律，当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 

      总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。