线性表

顺序表和链表的对比

• 循环内的条件变量是线性变化，$O(n)$，次方变化是$O(\log n)$

• 顺序表和链表的对比：

  • 顺序表支持随机访问，链表支持顺序访问.

  • 顺序表的存储密度等于$1$，链表的存储密度$<1$.

  • 顺序表初始化需要给定大小，数组是连续存储，分配的时候需要一次性给定对应的连续长度，链表不需要，每个元素都是离散的.

  • 顺序表利于访问，不利于插入和删除，链表利于插入和删除不利于访问.

  • 顺序表如果有序，使用折半查找时间复杂度为$O(\log n)$.