【数据结构】Golang 实现单链表

概念

通过指针将一组零散的内存块串联在一起 ， 把内存块称为链表的“结点”。 记录下个结点地址的指针叫作后继指针 next ，第一个结点叫作头结点，把最后一个结点叫作尾结点 。

代码实现

定义单链表

在 golang 中可以通过结构体定义单链表：

// ListNode 单链表
type ListNode struct {
	Val  int
	Next *ListNode
}
1
2
3
4
5

操作单链表

使用 golang 实现单链表常用操作：添加节点、遍历链表、查找链表节点、获取链表长度

// AddNode 添加节点
func AddNode(head *ListNode, v int) *ListNode {
	newNode := &ListNode{Val: v, Next: nil}

	if head == nil {
		return newNode
	}

	current := head
	for current.Next != nil {
		current = current.Next
	}

	current.Next = newNode
	return head
}

// TraverseSingleList 遍历单链表
func TraverseSingleList(t *ListNode) {
	if t == nil {
		fmt.Println("-> 空链表!")
		return
	}
	for t != nil {
		fmt.Printf("%d -> ", t.Val)
		t = t.Next
	}
	fmt.Println()
}

// SearchSingleListNode 查找单链表节点
func SearchSingleListNode(t *ListNode, v int) bool {
	if Head == nil {
		t = &ListNode{v, nil}
		Head = t
		return false
	}
	if v == t.Val {
		return true
	}
	if t.Next == nil {
		return false
	}
	return SearchSingleListNode(t.Next, v)
}

// GetSingleListSize 获取链表长度
func GetSingleListSize(t *ListNode) int {
	if t == nil {
		fmt.Println("-> 空链表!")
		return 0
	}
	i := 0
	for t != nil {
		i++
		t = t.Next
	}
	return i
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59