数组

访问数组元素为O(1)，插入和删除均为O（n）
查找不为O(1)，数组的正确表述是数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

特点：

一组连续的内存空间，存储相同类型的数据
根据下标寻找元素，使用内存地址访问
a[i]_address = base_address + i * data_type_size

链表

访问链表元素为O(n)，插入和删除均为O（1）
插入和删除操作比较多，就用链表

特点：

不需要连续内存空间，可以用指针把零散内存块串联起来，不知道要插入多少数据时，用链表就好

• 单链表：单个方向，只有next指针，插入删除O(1),访问元素O(N)
• 循环链表：特殊的单链表，尾结点指向头结点，处理环形结构问题，约瑟夫问题
• 双向链表：有前驱和后继指针，需要更多内存空间，但提供操作灵活性

$\color{red}{单链表和双向链表的比较：}$单链表和双向链表的比较：
只有当找到了要删除或插入的结点，双向链表的删除和插入操作才是O(1),单向链表为O(N)，
要不然遍历查找那个结点比较耗时，所以它们的复杂度都为O(n)

双向链表的好处：空间换时间，费内存但省时间

$\color{red}{数组和链表的比较：}$数组和链表的比较：

• CPU缓存友好性：
  数组可以借助CPU缓存机制，预读数组中的数据，提高访问效率，[^1]
  链表在内存中不是连续存储，对CPU缓存不友好，无法有效预读

• 内存大小限制：
  数组的大小固定了，声明的数组过大过小都会导致内存问题，而且扩容时，需要拷贝原数组，非常费时
  链表没有大小限制，天然支持动态扩容