Golang 常用数据结构与方法
#2023#Golang 2023-11-28

Golang 常用的数据结构与方法

本文整理了一些刷算法时，对于常见的官方已实现的数据结构与方法，整理了实现思路，这样刷题时就不用再造轮子了。

（目前只有 List，后面有时间会整理其他的。比如 sort 包）

数据结构

list.List

首先，这个链表它不是并发安全的。

其次，这个链表它不是并发安全的。

提供的方法

这是 Go 实现的一个双向链表，它提供的方法有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Init() *list.List
Len() int

// 获取链表中的节点
Front() *list.Element // 返回链表的头节点
Back() *list.Element // 返回链表的尾节点

// 插入
PushFront(v any) *list.Element // 头插入
PushBack(v any) *list.Element // 尾插入
InsertBefore(v any, mark *list.Element) *list.Element // 在某个节点前插入
InsertAfter(v any, mark *list.Element) *list.Element // 在某个节点后插入
PushBackList(other *list.List) // 尾插入一整条链表
PushFrontList(other *list.List) // 头插入一整条链表

// 删除
Remove(e *list.Element) any // 删除链表中的元素

// 特色
MoveToFront(e *list.Element) // 将当前元素移动到头部
MoveToBack(e *list.Element) // 将当前元素移动到尾部
MoveBefore(e *list.Element, mark *list.Element) // 将当前元素移动到传入节点之前
MoveAfter(e *list.Element, mark *list.Element) // 将当前元素移动到传入节点之后

实现思路

数据结构

List 的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
type List struct {
	root Element // 这是个哨兵节点，它的下一个元素才是真正的头节点，上一个元素则是尾节点
	len  int     // 当前链表的长度
}

type Element struct {
    // 前面和后面的节点
	next, prev *Element
	// 这个元素是哪个链表的
	list *List
	// 存储的元素值
	Value any
}

通过数据结构可以看到的是，List 的 root 实际上是哨兵节点。也就是说，这个环的头节点不是 root，尾节点也不是 root。并且，头节点的上一个节点也并不是尾节点。

至于这里为什么要有一个哨兵节点，官方给的解释是：实现方便。

也确实，在头插时就不需要一个中间节点等等（很巧妙

初始化

对于初始化，一般有三种方式：

1
2
3
4
5
var l1 list.List
// 这两种方式返回的类型是 *List
var l2 = list.Init()
// or
var l3 = list.New()

无论是哪种，都逃不过 Init 函数

1
2
3
4
5
6
7
8
9
func (l *List) Init() *List {
    // 当前环只有哨兵节点
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

func New() *List { return new(List).Init() }

可能会有疑惑，第一种方式没有调用 Init 呀？

请看 vcr。

在我们调用插入删除之类的方法时，会调用一个隐式方法，lazyInit。

这个函数的实现如下：

1
2
3
4
5
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}

什么情况下会出现 l.root.next == nil

也就是我们声明时是 ： var l list.List

so.

获取元素的各种姿势

**Front() *list.Element **

1
2
3
4
5
6
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}

**Back() *list.Element **

1
2
3
4
5
6
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

没啥好说的，不为空的话就直接返回哨兵节点的上下一个就行。

*Prev() Element

1
2
3
4
5
6
func (e *Element) Prev() *Element {
    if p := e.prev; e.list != nil && p != &e.list.root {
       return p
    }
    return nil
}

*Next() Element

1
2
3
4
5
6
func (e *Element) Next() *Element {
    if p := e.next; e.list != nil && p != &e.list.root {
       return p
    }
    return nil
}

if 那一行就是，先获取当前节点的前后一个，如果链表不为空，或者说不是哨兵节点，直接返回

插入元素的各种姿势

*PushFront(v any) list.Element

1
2
3
4
func (l *List) PushFront(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

先是查看是否初始化了，然后调用 insertValue 方法，将需要插入的 val 插入到哨兵节点后面（也就是头插法了）

对于 insertValue

1
2
3
4
5
6
7
8
9
10
11
12
13
func (l *List) insertValue(v any, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

很简单，也就是把传入的 val 值初始化出一个 element，将这个初始化的 element 用常规方法设置成传入节点的后置节点。

*PushBack(v any) list.Element

1
2
3
4
func (l *List) PushBack(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

和头插一样，插入到尾节点后面即可。

**InsertBefore(v any, mark list.Element) list.Element

1
2
3
4
5
6
func (l *List) InsertBefore(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	return l.insertValue(v, mark.prev)
}

**InsertAfter(v any, mark list.Element) list.Element

1
2
3
4
5
6
func (l *List) InsertAfter(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	return l.insertValue(v, mark)
}

和头插尾插一样，插入到当前节点的前面后面就行

*PushBackList(other list.List)

1
2
3
4
5
6
7
8
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
        // 获取链表长度，和头节点
        // 使用循环将这个链表插入到需要插入的链表后面
		l.insertValue(e.Value, l.root.prev)
	}
}

*PushFrontList(other list.List)

1
2
3
4
5
6
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}

和上面的一样

删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (l *List) Remove(e *Element) any {
    // 这个元素都不是当前链表的，就没必要删了
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}

func (l *List) remove(e *Element) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // 避免内存泄漏
	e.prev = nil // 避免内存泄漏
	e.list = nil
	l.len--
}

就非常常规的删除链表中的节点。

特色操作

主要依托 move 函数

move

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (l *List) move(e, at *Element) {
    // 将传入参数 e 移动到 at 后面
    // 也就是 at 的下一个节点变为 e
	if e == at {
        // 相等不需要操作
		return
	}
    // 先将 e 上一个节点和下一个节点相连
	e.prev.next = e.next
	e.next.prev = e.prev

    // at 的下一个节点改为 e
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
}

*MoveToFront(e list.Element)

1
2
3
4
5
6
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	l.move(e, &l.root)
}

**MoveBefore(e list.Element, mark list.Element)

1
2
3
4
5
6
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}

另外两个就类似了