线性表总结

谁更优

这两个结构各有优势,很难说谁更优?严格他们俩,相辅相成的两个结构

比较

  1. 存取(读写)方式
    i. 顺序表可以顺序存取 也可以随机存取
    ii. 链表只能从表头顺序存取元素

  2. 逻辑结构与物理结构
    i. 顺序存储结构-> 在逻辑上相邻的元素 对应的物理位置也相邻
    ii. 链式存储结构-> 在逻辑上相邻的元素 物理存储位置不一定相邻(由指针链表示)

  3. 查找/ 插入/ 删除 操作
    i. 按值查找

     - 顺序表无序 : 两者时间复杂度均为 O(n)
     - 顺序表有序 : 顺序表时间复杂度为O($$log_2 n$$)  (折半查找)  
    

    i. 按序号查找

     - 顺序表: 时间复杂度仅为O(1)(随机访问)
     - 链表: 平均时间复杂度为O(n)
    

    iii. 插入/删除

     - 顺序表: 平均移动半个表的长度
     - 链表:  只需修改相应结点的指针域
    
  4. 空间分配
    i. 顺序表 :

     - 静态存储 -> 不可扩容: 分配过大 会闲置空间 分配过小 会内存溢出  
     - 动态存储 -> 可以扩容:  需要移动大量元素 操作效率降低且 内存中如果没有更大快的连续存储空间 会分配失败
    

    ii. 链表:

     - 按需申请 灵活高效
    

各自优缺点

顺序表

优点 :

  1. 支持随机访问 需要随机访问结构的算法可以很好的适用
  2. CPU高速缓存命中率更高

缺点 :

  1. 头部中部插入删除 时间效率低O(n)
  2. 连续的物理空间 空间不够了需要扩容
    a. 增容有一定程度消耗
    b. 为了避免频繁扩容, 一般选择按倍数去扩容, 用不完可能造成空间浪费.

链表(双向带头循环链表)

优点 :

  1. 任意位置插入效率高
  2. 按需申请, 释放空间

缺点 :

  1. 不支持随机访问 (用下标访问) 意味着 一些排序二分查找等在这种结构不适用
  2. 链表存储一个值, 同时需要存储链接指针, 也有一定的消耗
  3. CPU高速缓存命中率更低

Code地址