顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序)，平均需要移动一半(或近一半)元素，修改效率不高。

链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。

 

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

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

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

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

 

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

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

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

首先定义结点的 存储密度 。

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

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

 

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

 

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