顺序表和链表的比较

  1. 存取方式
    顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
  2. 逻辑结构与物理结构
    采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。
    采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针来表示的。
  3. 查找、插入和删除
    | null | 顺序表 | 链表 |
    | 查找 | O(n) | O(n) |
    | 插入 | O(n) | O(1) |
    | 删除 | O(n) | O(1) |
  4. 空间分配
    顺序表是静态空间分配，链表是动态空间分配。

实际应用中表的选取

  1. 基于存储考虑
    顺序表：可以估计线性表的长度或存储规模时采用；
    链表：不用事先知道存储规模，但链表的存储密度低。
  2. 基于运算考虑
    顺序表：经常访问链表中的元素时使用；
    链表：经常插入或者删除时使用；
  3. 基于环境考虑、
    顺序表：直接采用数组，容易实现。
    链表：基于指针实现，相对较为繁琐。