顺序表与链表

发布于 2022-11-26  172 次阅读


存取方式(不同于存储结构)

  • 顺序表可以顺序存取,也可以随机(指定位置)存取
  • 链表只可以从表头顺序存取

逻辑结构

相邻与不相邻

查找,插入和删除

对于按值查找

  • 顺序表无序时,链表与顺序表两者时间复杂度均为O(n)
  • 顺序表有序时,顺序表采用折半查找,时间复杂度为O(log2n)

对于按序号查找

  • 顺序表支持随机访问,时间复杂度为O(1),
  • 链表为O(n)