链表

基础与数据结构

说明

节点通过指针串联；已知节点后插入 O(1)，按位置查找 O(n)。

分析

节点只保存值和下一个节点的指针，插入时改写相邻指针即可。示例已持有目标节点，因此操作不需要遍历；若只知道下标，仍要从头走到该位置。

把q插到p与r之间时，先保存原后继r，再令q.next=r、p.next=q。覆盖p.next后才寻找原后继可能丢失后半条链。图表示逻辑连接，不表示内存连续；只知道位置时还须先遍历定位。

查看图表代码

适用前提与边界

链表会产生额外指针与分配开销，Go 中普通顺序数据通常优先用切片。 InsertAfter要求传入节点非空；删除操作还需维护头尾和前驱，示例没有实现删除接口。

示例输入与调用

head := &Node{Value: 1}
	InsertAfter(head, 2)
	fmt.Println(head.Value, head.Next.Value)

运行输出

1 2

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

func InsertAfter(n *Node, value int) {
	n.Next = &Node{Value: value, Next: n.Next}
}

func main() {
	head := &Node{Value: 1}
	InsertAfter(head, 2)
	fmt.Println(head.Value, head.Next.Value)
}