数据结构学习---线性表的数组实现与单链表实现比较

1. 基于时间的比较
  线性表的操作主要有查询，插入，删除三类。
  对于查找操作有基于序号的查找，即存取线性表中i号数据元素，由于数组的随机存取特性，在线性表的顺序存储实现中可以在常数1时间内完成，而在线性表中则需要从节点开始顺着链表才能获取，无法在常数时间内完成，因此顺序存储由于链式存储。查找操作还有基于元素的查找，即线性表是否包含某个元素，元素的序号是多少，这类操作的线性表的顺序存储与链式存储都需要从线性表中的序号为0的元素开始依次查找，因此两种实现性能相同，综上所述，如果在线性表的使用中主要操作时查找，那么应当选用顺序存储实现的线性表。
  对于基于数据元素的插入，删除操作而言，当使用数组实现时，首先需要采用顺序查找定位相应数据元素，然后才能插入，删除，并且在插入，删除过程又需要移动大量元素。相对而言链表的实现只是需要在定位元素的基础上，简单的修改几个指针即可完成，因此链式存储优于顺序存储。对于基于序号的插入，删除操作，因为在顺序存储中平均需要移动一半的元素，而在链式存储中不能直接定位，平均需要比较一半的元素才能定位，因此顺序存储与链式存储性能相当。综上所述，如果在线性表的使用中主要操作时插入，删除，那么选用链式村塾的线性表为佳。
2.基于空间的比较 
  线性表的顺序存储，其存储空间是预先静态分配的，虽然在实现的过程中可以动态扩展数组空间，但是如果线性表的长度变化范围较大，空间在使用过程中育有会存在大量空闲空间，使得存储空间的利用率不高，而线性表的链式存储，其节点空间是动态分配的，不会存在存储空间没有完全利用的情况。因此线性表长度变化较大时，宜采用链式存储结构。
  线性表的数据元素结构简单，并且线性表的长度变化不大时。由于链式存储结构使用了额外存储空间来表示数据元素之间的逻辑关系，因此针对数据域而言，指针域所占的比重较大，而在线性表的顺序存储结构中，没有使用额外的存储空间来表示数据元素之间的逻辑关系，尽管有一定的空闲空间没有利用，但总体而言由于线性表长度变化不大，因此没有利用的空间比例较小，所以当线性表数据元素结构简单，长度变化不大时可以考虑采用顺序存储结构。