2. 链表（Linked List）

问题：需要频繁在中间插入/删除元素，数组搬运代价太高。

核心：每个节点存储数据和指向下一个节点的指针，内存不需要连续。

特点

非连续内存，通过指针串联
插入/删除只需修改指针，O(1)（已知位置时）
不支持随机访问，只能从头遍历

优点

插入/删除快（已知前驱节点时 O(1)）
大小动态，不需要预分配
内存不需要连续块

缺点

随机访问 O(n)，必须从头遍历
每个节点额外存储指针，内存开销大
缓存不友好（内存不连续，CPU 预读失效）

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class LinkedList {
  head = null;

  // 头部插入 O(1)
  prepend(val) {
    const node = new Node(val);
    node.next = this.head;
    this.head = node;
  }

  // 查找 O(n)
  find(val) {
    let cur = this.head;
    while (cur) {
      if (cur.val === val) return cur;
      cur = cur.next;
    }
    return null;
  }

  // 在 target 节点后插入 O(1)
  insertAfter(target, val) {
    const node = new Node(val);
    node.next = target.next;
    target.next = node;
  }

  // 遍历
  toArray() {
    const res = [];
    let cur = this.head;
    while (cur) {
      res.push(cur.val);
      cur = cur.next;
    }
    return res;
  }
}

const list = new LinkedList();
list.prepend(3);
list.prepend(2);
list.prepend(1);
console.log(list.toArray()); // [1, 2, 3]

package linkedlist

type Node struct {
	Val  int
	Next *Node
}

type LinkedList struct {
	Head *Node
}

// 头部插入 O(1)
func (l *LinkedList) Prepend(val int) {
	node := &Node{Val: val, Next: l.Head}
	l.Head = node
}

// 查找 O(n)
func (l *LinkedList) Find(val int) *Node {
	for cur := l.Head; cur != nil; cur = cur.Next {
		if cur.Val == val {
			return cur
		}
	}
	return nil
}

// 在 target 节点后插入 O(1)
func (l *LinkedList) InsertAfter(target *Node, val int) {
	node := &Node{Val: val, Next: target.Next}
	target.Next = node
}

链表是栈、队列的底层实现基础；JS 用 Object 模拟节点，Go 标准库 container/list 提供双向链表。