链表和顺序表比较

#存取（读写）方式

  • 链表仅支持顺序存储，只能从头节点开始访问数据
  • 顺序表支持随机存储，可通过下标直接访问任意数据，也支持顺序存储

    • #逻辑结构与物理结构

  • 顺序存储中，逻辑上相邻的元素物理内存中也相邻存放
  • 链式存储中，逻辑上相邻的元素物理内存中未必相邻，逻辑关系通过指针显式维护

    • #查找，插入和删除操作

  • 按值查找：表若无序，时间复杂度均为O(n)；表若有序，顺序表可以折半查找，时间复杂度O(log2 n)。
  • 对于按序号查找：顺序表的时间复杂度为O(1)，链表则为O(n)。
  • 对于插入/删除操作：顺序表平均需要移动约一半元素，开销较大。链表在元素节点已知的情况下，只需修改指针，无需移动，但是非已知情况，则仍需O(n)

    • #空间分配

  • 顺序表无论是静态分配可能分配空间过多，造成空间浪费，动态分配需要申请新的连续内存块，且复制原有数据，也有可能无法申请到足够空间而失败，时间开销大。
  • 链表则足够灵活，但每个节点需要额外存储指针域，导致存储密度小于1，空间利用率较低。