Go语言数据结构——双向列表

发表于 | 分类于 >
本文字数： 3.5k | 阅读时长 ≈ 3 分钟

Golang标准库中，包含双向列表这一数据结构，先来了解一下

源码

1
2
3
4
5
6
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

    // The list to which this element belongs.
    // 该元素属于哪一个list
	list *List

    // The value stored with this element.
    // 此元素存储的值
	Value interface{}
}

声明

1
2


操作双向列表

插入值

在最前面/最后面插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
	myList := list.New()
	// 在列表最后添加元素
	myList.PushBack("a")
	printList(myList) // a

	myList.PushFront("b")
	printList(myList) // b a

	myList.PushBack("c")
	printList(myList) // b a c
}

// 遍历双向列表list
func printList(theList *list.List) {
	currElement := theList.Front()
	for i := 0; i < theList.Len(); i++ {
		fmt.Printf("%v ", currElement.Value)
		currElement = currElement.Next()
	}
	fmt.Println()
}

在指定值的前/后插入

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
func main() {
	myList := list.New()
	// 在列表最后添加元素
	myList.PushBack("a")
	myList.PushBack("b")
	myList.PushBack("c")
	myList.PushBack("d")
	myList.PushBack("e")
	myList.PushBack("f")

	printList(myList) // a b c d e f

	// 向第一个元素后面添加元素
	myList.InsertAfter("x", myList.Front())

	// 向最后一个元素前面添加元素
	myList.InsertBefore("z", myList.Back())

	printList(myList) // a x b c d e z f
}

// 遍历双向列表list
func printList(theList *list.List) {
	currElement := theList.Front()
	for i := 0; i < theList.Len(); i++ {
		fmt.Printf("%v ", currElement.Value)
		currElement = currElement.Next()
	}
	fmt.Println()
}

取出值

取出第一个值和最后一个值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
	myList := list.New()
	// 在列表最后添加元素
	myList.PushBack("a")
	myList.PushBack("b")
	myList.PushBack("c")
	myList.PushBack("d")
	myList.PushBack("e")
	myList.PushBack("f")

	printList(myList) // a b c d e f

	frontValue := myList.Front().Value
	backValue := myList.Back().Value
	fmt.Println(frontValue, backValue) // a f
}

按索引取出值

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
func main() {
	myList := list.New()
	// 在列表最后添加元素
	myList.PushBack("a")
	myList.PushBack("b")
	myList.PushBack("c")
	myList.PushBack("d")
	myList.PushBack("e")
	myList.PushBack("f")

	printList(myList)   // a b c d e f

	result := getEleFromListByIndex(myList, 4)
	fmt.Println(result) // e
}

// 按取出第几个值
func getEleFromListByIndex(theList *list.List, index int) interface{} {
	if index < 0 || index > theList.Len()-1 {
		return nil
	} else {
		if index == 0 {
			return theList.Front().Value
		} else {
			currElem := theList.Front()
			for i := 0; i < index; i++ {
				currElem = currElem.Next()
				if i == index-1 {
					return currElem.Value
				}
			}
		}
	}
	return nil
}

// 遍历双向列表list
func printList(theList *list.List) {
	currElement := theList.Front()
	for i := 0; i < theList.Len(); i++ {
		fmt.Printf("%v ", currElement.Value)
		currElement = currElement.Next()
	}
	fmt.Println()
}