删除添加

数组添加删除

数组都对应着一段连续的内存。如果我们想要在任意位置删除一个元素，那么该位置往后的所有元素，都需要往前挪一个位置；相应地，如果要在任意位置新增一个元素，那么该位置往后的所有元素也都要往后挪一个位置。假设数组的长度是 n，那么因增加/删除操作导致需要移动的元素数量，就会随着数组长度 n 的增大而增大，呈一个线性关系。所以说数组增加/删除操作对应的复杂度就是 O(n)
⚠️JS中纯数字数组，那么对应的确实是连续内存，但是如果我们定义了不同类型的元素：

  1. const arr = ['haha', 1, {a:1}]

它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的。

链表添加删除

在链表中，添加和删除操作的复杂度是固定的——不管链表里面的结点个数 n 有多大，只要我们明确了要插入/删除的目标位置，那么我们需要做的都仅仅是改变目标结点及其前驱/后继结点的指针指向。 因此我们说链表增删操作的复杂度是常数级别的复杂度，用大 O 表示法表示为 O(1)

查找

数组查找

数组中，我们直接访问索引、可以做到一步到位，这个操作的复杂度会被降级为常数级别O(1)

链表查找

当我们试图读取某一个特定的链表结点时，必须遍历整个链表来查找它，用大 O 表示法表示为 O(n)