链表
Contents
概念
链表是一种通过指针串联在一起的数据结构，每一个节点都存放着一个数据和指向下一个节点的指针。
链表的第一个节点成为都节点（head）。最后一个节点的指针指向null。
链表的实现方式
结构体
type List struct {
Val int
Next *List
}
数组
定义两个数组，一个存放数据，一个存放指针。
链表的操作
遍历
type List struct {
Val int
Next *List
}
func main() {
// 创建链表
l := createList([]int{1, 2, 3, 4, 6})
// 遍历
each(l)
}
func each(l *List) {
for l != nil {
fmt.Println(l.Val)
// 需要一个指针，并不断把next赋值给指针即可。
l = l.Next
}
}
func createList(data []int) *List {
list := new(List)
head := list
for _, v := range data {
list.Next = &List{Val: v}
list = list.Next
}
return head.Next
}
插入
type List struct {
Val int
Next *List
}
func main() {
l := createList([]int{1, 2, 3, 4, 6})
insert(l, 4, 5)
}
func createList(data []int) *List {
list := new(List)
head := list
for _, v := range data {
list.Next = &List{Val: v}
list = list.Next
}
return head.Next
}
func insert(l *List, before int, val int) {
for l != nil {
if l.Val == before {
l.Next = &List{Val: val, Next: l.Next}
break
}
l = l.Next
}
}
删除
type List struct {
Val int
Next *List
}
func main() {
l := createList([]int{1, 2, 3, 4, 6})
delete(l, 6)
}
func createList(data []int) *List {
list := new(List)
head := list
for _, v := range data {
list.Next = &List{Val: v}
list = list.Next
}
return head.Next
}
func delete(l *List, val int) {
head := &List{Next: l}
p := head
for p.Next != nil {
if p.Next.Val == val {
p.Next = p.Next.Next
break
}
p = p.Next
}
*l = *head.Next
}
应用场景
- 操作系统中的动态内存分配。
- LRU 缓存淘汰算法。（最近最少使用的数据删除）