1. 链表的结构★★☆☆☆⏱ 4 min

链表是一种动态线性数据结构，每个元素（称为节点）同时存储数据和指向序列中下一个节点的指针。与数组不同，节点不需要存储在连续内存位置，因此链表大小可以在运行时动态增减。

2. 常用链表操作★★★☆☆⏱ 6 min

链表的四个核心操作是遍历、查找、插入和删除。每个操作都遵循指针操作规则来维护链表结构。

• 遍历：从头节点开始，通过next指针从一个节点移动到下一个节点，直到到达null

• 查找：遍历链表，找到存储目标数据值的节点

• 插入：在链表的头部、中间或尾部添加新节点

• 删除：从链表的任意位置移除已有节点

Exam tip:

一定要先设置新节点的指针，再修改原有节点的指针。这样可以避免丢失链表剩余部分的引用。

3. 链表 vs 静态数组★★★☆☆⏱ 5 min

链表和数组都是线性数据结构，但常用操作的性能特征差异很大。下表总结了关键区别：

当需要频繁插入/删除操作，且事先不知道集合大小时，更适合使用链表。当核心需求是元素的随机访问时，数组更有优势。

4. 操作的时间复杂度★★★★☆⏱ 3 min

CIE 9618经常要求你写出并解释常用链表操作的时间复杂度。时间复杂度描述了操作时间随链表节点数n的变化关系。

• 遍历 / 查找：最坏情况 O(n)

• 头部插入 / 删除：总是 O(1)

• 尾部插入 / 删除：带尾指针为O(1)，不带尾指针为O(n)

• 中间插入 / 删除：最坏情况 O(n)

Exam tip:

一定要说明复杂度是最坏情况还是平均情况，并解释你的推理过程才能拿到满分。