Array & Linked List

Array

数组核心特征：

连续存储 + 可通过下标直接计算地址。

第 i 个元素：

$$addr(i)=base+i\times size$$

因此随机访问：

$$O(1)$$

---

Array 插入

中间插入需要移动后续元素：

$$O(n)$$

但数组尾部追加并不一定是 O(n)。

动态数组在容量充足时尾部追加通常是 O(1)，扩容成本通过多次操作摊销，因此通常称为：

Amortized O(1)

---

Linked List

节点：

[data | next] -> [data | next] -> ...

节点不要求连续存储。

访问第 i 个节点需要沿指针依次遍历：

$$O(n)$$

---

Linked List 插入

如果已经获得插入位置对应节点：

A -> B

插入 X：

A -> X -> B

只修改指针：

$$O(1)$$

但是如果需要先找到插入位置：

$$O(n)+O(1)=O(n)$$

---

Array vs Linked List

如果业务需要频繁随机访问，优先考虑数组，因为数组可以通过下标 O(1) 定位，同时通常具有较好的缓存局部性。

如果已经能够定位节点，并需要频繁插入删除，链表只需要修改指针，不需要移动大量元素。

但链表随机访问需要 O(n)，同时每个节点存在额外的指针空间开销。

因此实际选择取决于访问模式、插删频率以及是否已经能够快速定位操作位置。

---

易错点

不要简单记：

链表插入永远比数组快。

链表 O(1) 插入的前提：

已经定位到目标位置。

---

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_1.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md