什么是单链表，何时应该使用它？

Question

什么是单链表，何时应该使用它？

Accepted Answer

**singly linked list** 是一系列 **nodes** 的链，其中每个node持有一个值和指向 **next** node的指针。与数组不同，节点不是连续的——它们可以驻留在内存中的任何位置，通过引用连接。

## 结构

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## 示例

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## 复杂度

| 操作 | 时间 |
|---|---|
| 在头部插入/删除 | O(1) |
| 按索引访问 | O(n) |
| 搜索 | O(n) |

## 权衡

- **优势：** 在前端O(1)插入/删除；无需重新分配即可增长；没有浪费的容量。
- **劣势：** 无随机访问；每个node都有指针开销；缓存局部性差（分散的内存）。

## 为什么这很重要

当您经常在末端添加或删除，很少在中间进行索引操作时，链表表现出色——例如，作为 stacks、queues 和邻接表的骨干。

这里理解指针操作是 trees、graphs 和许多面试问题的基础。