线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
image.png
image.png

数组

  1. 数组（Array）是一种线性表数据结构。
  2. 它用一组连续的内存空间，
    1. 优点：
      1. 可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。
      2. 随机读取，按索引访问元素O(1)
    2. 缺点：
      1. 必须要占用整块连续空间，更容易导致内存不足。且扩容不方便。
      2. 插入，删除要做大量的扩容，数据复制移动，效率低。
  3. 来存储一组具有相同类型的数据。

链表

  1. 链表（Linked list）也是一种线性表数据结构。
  2. 非连续的内存空间，
    1. 优点：
      1. 可以占用非连续空间，扩容方便。
      2. 插入，删除只需要更改指针指向效率高。
    2. 缺点：
      1. 占用非连续空间，难以借助 CPU 的缓存机制，访问效率比数组低。
      2. 不支持随机访问，按索引访问元素O(n)

        内存分布

        image.png

        复杂度分析

        数组：高效的随机访问，低效的“插入”和“删除”。

        链表：高效的插入，删除，低效的随机访问。

        image.png