数组和链表的总结和比较

选择数组还是链表

插入、删除和随机访问的时间复杂度

数组的缺点

  • 若申请内存空间很大，比如 100 M ,但若内存空间没有 100 M 的连续空间是，则会申请失败，尽管内存可用空间超过 100 M 。
  • 大小固定，若空间存储不足，需要进行扩容，一旦扩容就要进行数据复杂，而这是非常费时的。

链表的缺点

  • 内存空间消耗更大，因为需要额外的空间存储指针信息。
  • 对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，还可能会造成频繁的 GC (自动辣鸡回收器) 操作。

如何选择链表和数组

数组简单易用，在实现上使用连续的内存空间，可以借助 CPU 的缓冲机制预读数组中的数据，所以访问效率更高。

而链表在内存中并不是连续存储的，所以为 CPU 缓存不友好，没办法预读。

如果代码对内存的使用非常苛刻，那数组就更适合。