区别

顺序表和链表的比较

顺序表 单链表
存取方式 可顺序存取，可随机存取 只能从表头顺序存取
逻辑结构和物理结构 顺序存储，逻辑上相邻物理上也相邻 链式存储，逻辑上相邻物理上不一定相邻，通过指针链接
按值查找 按值查找：O（n）(无序)
折半查找 O(log2n)(有序)		 O（n）
按序号查找 O（1） O（n）
插入 O（n），平均需要移动n/2个元素 只需修改相关结点
删除 O（n），平均需要移动n/2个元素 只需修改相关结点
空间分配 可能会出现存储空间大量闲置或空间不足溢出 动态申请空间，操作灵活、高效

怎样选取存储结构

  1、基于存储的考虑

    难以估计线性表的长度或存储规模时，不易采用顺序表；但链表的存储密度较低，链式存储结构的存储密度是小于1的。

  2、基于运算的考虑

    若经常做的运算是按序访问数据元素，则显然顺序表更优。

    若经常做插入删除操作，则链式存储结构则更优。

  3、基于环境的考虑

    顺序表容易实现，链表是基于指针的，相对来讲，前者实现更加简单，实现难易度也是需要考虑的一点。