Introduction

和 array 一样，linked list 用于表示序列数据。不同的是，linked list 的顺序不由内存中物理位置决定，而是通过节点的指针相连。每个 node 包含 data 和 next 指针（指向下一个 node）。

Advantages

在已知位置时，插入/删除节点是 O(1)，而数组需要移动后续元素。

Disadvantages

随机访问慢。无法像数组那样 arr[4] 直接取值，必须从头遍历，因此是 O(n)。

Learning resources

每个 node 指向下一个 node，最后一个 node 的 next 指向 null。

每个 node 有 next 和 prev 指针。第一个 node 的 prev 和最后一个 node 的 next 指向 null。

单向链表中最后一个 node 指回第一个 node。还有 circular doubly linked list：第一个 node 的 prev 指向最后一个 node，最后一个 node 的 next 指向第一个 node。

常见语言里只有 Java 提供 linked list 实现。自己实现也不难。

linked list 题常见套路：

在 head/tail 加 dummy node 可处理很多边界情况，避免对 head/tail 做复杂判断。记得操作结束后移除 dummy。

双指针是经典套路：

很多题可以新建链表解决，但会用额外空间，难度变低。面试官通常要求 in-place 修改。可以参考 Reverse a Linked List 的思路。

Linked list 可修改 next 指针，操作灵活：

该 topic 必练题。

在掌握基础后推荐练习。