【Go 数据结构】列表与字典

列表

对于列表的表示我们有如下两种实现形式：

• 顺序表示：指的是使用一组地址连续的存储单元依次存储线性表的数据，成为此线性表为顺序存储结构， 它以物理位置相邻来表示线性表中的数据间的逻辑位置，可随机存取表中的任何一个数据元素，顺序表示的也叫做顺序表，也就是用数组来实现的列表。
• 链式表示：指的是用一组任意的非连续的存储单元存储线性表中的数据元素，成为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储本身信息之外，还需要存储一个指向直接后继节点的信息，也就是用链表来实现的列表。

双端列表

定义数据类型

// 定义双端链表的数据类型
type ListNode struct {
	prev  *ListNode
	next  *ListNode
	value string
}
type DoubleList struct {
	head *ListNode  // 头节点
	tail *ListNode  // 尾节点
	len  int        // 长度
	lock sync.Mutex // 为了并发安全，引入锁
}
1
2
3
4
5
6
7
8
9
10
11
12

常见操作

/*
	一些常见的基本操作
*/

// GetValue 获取节点值
func (node *ListNode) GetValue() string {
	return node.value
}

// GetPre 获取前一个节点
func (node *ListNode) GetPre() *ListNode {
	return node.prev
}

// GetNext 获取后一个节点
func (node *ListNode) GetNext() *ListNode {
	return node.next
}

// HasNext 是否有后一个节点
func (node *ListNode) HasNext() bool {
	return node.next != nil
}

// HasPre 是否有前一个节点
func (node *ListNode) HasPre() bool {
	return node.prev != nil
}

// IsNil 是否为空
func (node *ListNode) IsNil() bool {
	return node == nil
}

// Len 获取长度
func (list *DoubleList) Len() int {
	return list.len
}

// First 头部节点
func (list *DoubleList) First() *ListNode {
	return list.head
}

// Last 尾部节点
func (list *DoubleList) Last() *ListNode {
	return list.tail
}
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

插入操作

实现从头部开始，在某个节点之前插入一个节点。

// AddNodeFormHead 从头部开始，在某个节点之前插入一个节点
// 0 表示第一个元素之前，1 表示第二个元素之前...
func (list *DoubleList) AddNodeFormHead(value string, pre int) {
	list.lock.Lock()
	defer list.lock.Unlock()

	if pre <= 0 || pre > list.len {
		panic("pre is out of range")
	}

	// 找到头部节点
	node := list.head

	// 向后进行遍历，找到pre-1个节点
	for i := 0; i <= pre; i++ {
		node = node.next
	}

	newNode := new(ListNode)
	node.value = value

	// 如果定位到的节点为空，则直接插入到头部
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 找到前一个节点
		pre := node.prev

		// 如果定位到的节点为头部，则直接插入到头部
		if pre.IsNil() {
			newNode.next = node
			node.prev = newNode
			list.head = newNode
		} else {
			// 将新节点插入到定位节点之前
			// 新节点的后一个节点为定位节点
			pre.next = newNode
			newNode.prev = pre

			// 新节点的前一个节点为定位节点的前一个节点
			node.next.prev = newNode
			newNode.next = node.next
		}
	}
	list.len++
}
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

实现从尾部开始，在某个节点之后插入一个节点。

// AddNodeFormTail 从尾部开始，在某个节点之后插入一个节点
// 0 表示第一个元素之后，1 表示第二个元素之后...
func (list *DoubleList) AddNodeFormTail(value string, next int) {
	list.lock.Lock()
	defer list.lock.Unlock()

	// 找到尾部节点
	node := list.tail

	if next <= 0 || next > list.len {
		panic("next is out of range")
	}

	// 向前进行遍历，找到next-1个节点
	for i := 0; i <= next; i++ {
		node = node.prev
	}

	newNode := new(ListNode)
	newNode.value = value

	// 如果定位到的节点为空，则直接插入到尾部
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 找到定位节点的后一个节点
		next := node.next

		// 如果定位到的节点为尾部，则直接插入到尾部,需要更新尾部节点
		if next.IsNil() {
			// 新节点的前一个节点为尾部节点
			// 新节点的后一个节点为空
			newNode.prev = node
			node.next = newNode

			list.tail = newNode
		} else {
			// 将新节点插入到定位节点之后
			// 新节点的前一个节点为定位节点
			newNode.prev = node
			node.next = newNode

			// 新节点的后一个节点为定位节点的后一个节点
			newNode.next = next
			next.prev = newNode
		}
	}
	list.len++
}
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

获取节点

实现从头部开始，获取第 n + 1 个位置上的节点。

// IndexFormHead 从头部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormHead(n int) *ListNode {
	if n > list.len || n < 0 {
		panic("index is out of range")
	}
	// 找到头部节点
	node := list.head
	// 向后进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.next
	}
	return node
}
1
2
3
4
5
6
7
8
9
10
11
12
13

实现从尾部开始，获取第 n + 1 个位置上的节点。

// IndexFormTail 从尾部开始获取第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) IndexFormTail(n int) *ListNode {
	if n > list.len || n < 0 {
		panic("index is out of range")
	}

	// 找到尾部节点
	node := list.tail

	// 向前进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.prev
	}
	return node
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除节点

实现从头部开始，删除第 n + 1 个位置上的节点。

// RemoveNodeFormHead 从头部开始，删除第 n + 1 个位置上的节点，索引从零开始
func (list *DoubleList) RemoveNodeFormHead(n int) *ListNode {
	list.lock.Lock()
	defer list.lock.Unlock()

	if n >= list.len || n < 0 {
		return nil
		panic("index is out of range")
	}

	// 找到头部节点
	node := list.head

	// 向后进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.next
	}

	// 移除节点
	pre := node.prev
	next := node.next

	// 如果前继和后继都为空，则直接删除头部节点
	if pre.IsNil() && next.IsNil() {
		list.head = nil
		list.tail = nil
	} else if pre.IsNil() {
		// 表示移除的是头部节点，让下一个节点变成头部节点
		list.head = next
		next.prev = nil
	} else if next.IsNil() {
		// 表示移除的是尾部节点，让前一个节点变成尾部节点
		list.tail = pre
		pre.next = nil
	} else {
		// 前继和后继都不为空，则将后继节点的前继节点变成前继节点
		pre.next = next
		next.prev = pre
	}
	list.len--
	return node
}
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

实现从尾部开始，删除第 n + 1 个位置上的节点。

// PopTailFromHead 从尾部开始往前找，获取第 n 个位置上的节点，并将移除返回
func (list *DoubleList) PopTailFromHead(n int) *ListNode {
	list.lock.Lock()
	defer list.lock.Unlock()

	if n >= list.len || n < 0 {
		return nil
		panic("index is out of range")
	}

	// 获取尾部元素
	node := list.tail

	// 向前进行遍历，找到第 n 个节点
	for i := 0; i < n; i++ {
		node = node.prev
	}

	// 移除的节点的前驱和后继
	pre := node.prev
	next := node.next

	// 如果前驱和后继都为空，则直接删除尾部节点
	if pre.IsNil() && next.IsNil() {
		list.head = nil
		list.tail = nil
	} else if pre.IsNil() {
		// 直接将后继节点变成尾部节点
		list.head = next
		next.prev = nil
	} else if next.IsNil() {
		list.tail = pre
		pre.next = nil
	} else if next.IsNil() {
		pre.next = next
		pre.next = nil
	} else {
		pre.next = next
		next.prev = pre
	}
	list.len--
	return node
}
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

字典

字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射。并且键不能重复。

func DicExample() {
	m := make(map[string]int64, 4)

	m["dog"] = 1
	m["hen"] = 2
	m["cat"] = 3

	fmt.Println(m)

	which := "hen"

	v, ok := m[which]
	if ok {
		// find
		fmt.Println("finn", which, "value:", v)
	} else {
		// not find
		fmt.Println("not find", which)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

不可重复集合

在 Golang 中，实现集合是一件很有意思的事情。

我们通常借助空结构体为值来实现 Set， 因为我们知道字典的键是不重复的，所以只要我们不考虑字典的值，就可以来实现集合了。

注意：空结构体并不占用内存在大小。

定义数据类型

// 思想：不考虑字典的值，我们可以实现一个set

type Set struct {
	m   map[int]struct{} // 为什么我们要使用空结构体，因为空结构体不占用内存
	len int
	sync.RWMutex
}
1
2
3
4
5
6
7

新建一个Set操作

// NewSet 新建一个set
func NewSet(cap int64) *Set {
	temp := make(map[int]struct{}, cap)
	return &Set{
		m: temp,
	}
}
1
2
3
4
5
6
7

增加一个元素

// Add 增加一个元素
func (s *Set) Add(item int) {
	s.Lock()
	defer s.Unlock()

	s.m[item] = struct{}{}
	s.len = len(s.m)
}
1
2
3
4
5
6
7
8

删除一个元素

//Remove 移除一个元素
func (s *Set) Remove(item int) {
	s.Lock()
	defer s.Unlock()

	if s.len == 0 {
		return
	}
	// 从字典中删除
	delete(s.m, item)
	// 计算长度
	s.len = len(s.m)
}
1
2
3
4
5
6
7
8
9
10
11
12
13

判断元素是否存在

// Has 判断一个元素是否在set中
func (s *Set) Has(item int) bool {
	s.RLock()
	defer s.RUnlock()

	_, ok := s.m[item]
	return ok
}
1
2
3
4
5
6
7
8

获取长度

// Len 获取set的长度
func (s *Set) Len() int {
	return s.len
}
1
2
3
4

判断是否为空

//IsEmpty 判断set是否为空
func (s *Set) IsEmpty() bool {
	if s.len == 0 {
		return true
	}
	return false
}
1
2
3
4
5
6
7

清空

// Clear 清空set
func (s *Set) Clear() {
	s.Lock()
	defer s.Unlock()

	s.m = make(map[int]struct{})
	s.len = 0
}
1
2
3
4
5
6
7
8

转化为Slice

// List 将 Set 转化为 Slice
func (s *Set) List() []int {
	s.RLock()
	defer s.RUnlock()

	list := make([]int, 0, s.len)
	for item := range s.m {
		list = append(list, item)
	}
	return list
}
1
2
3
4
5
6
7
8
9
10
11

总结

本次我们介绍使用Go语言实现数据结构中的列表和字典，并且介绍了一些常见的操作。数据结构这一系列我们没有涉及到具体的细节的讲解，适合有一定数据结构基础的童鞋，本系列代码已经上传至Github，欢迎大家 Star。