算法图谱

Array

数组

线性结构入门时间 访问 O(1) / 插入 O(n)空间 O(n)

连续内存中的同构序列。按下标随机访问极快，在中间插入或删除需要搬移元素。

动画

4
0
9
1
1
2
7
3
3
4

数组：连续内存，按下标 O(1) 访问。

1 / 4

  • 默认

讲解

绝大多数算法的底层容器。缓存友好、实现简单，是动态数组、堆、哈希表的基础。

  1. 01元素按下标存放在一段连续空间，a[i] 的地址 = base + i × size。
  2. 02读取 / 写入任意下标都是常数时间。
  3. 03在中间插入：把 i 及之后的元素整体右移一格，再写入。
  4. 04删除同理，左侧填补空位。尾部 push/pop 才是均摊 O(1)。

易错点

  • 下标越界是最常见的错误，访问前确认 0 ≤ i < length。
  • 频繁在头部插入会退化成 O(n²)，应改用链表或双端队列。

代码

const a = [class="text-accent">4, class="text-accent">9, class="text-accent">1, class="text-accent">7, class="text-accent">3];
const x = a[class="text-accent">2];          // O(class="text-accent">1) 读取
a.splice(class="text-accent">2, class="text-accent">0, class="text-accent">8);       // 下标 class="text-accent">2 插入 class="text-accent">8
a.splice(class="text-accent">1, class="text-accent">1);          // 删除下标 class="text-accent">1

相关课题