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 缓存淘汰算法。(最近最少使用的数据删除)