Go 容器类型之双端队列和单链表的使用与实现

双端队列 Deque

Deque，即双端队列，是一个可以扩展的容器。扩展可以发生在容器的前面或后面。当队列的顶部或尾部需要经常被引用时，经常使用双端队列。

Go 官网有一个双端队列的实现，官方地址点此处。

下面的代码块显示了 Go 双端队列 deque 的使用：

package main

import (
	"fmt"

	"github.com/gammazero/deque"
)

func main() {
	var q deque.Deque[string]
	q.PushBack("I")
	q.PushBack("love")
	q.PushBack("learning")
	q.PushBack("Go")

	fmt.Println("队列长度为: ", q.Len())  // Prints: 4
	fmt.Println("队首为元素:", q.Front()) // Prints: I
	fmt.Println("队尾为元素: ", q.Back()) // Prints: Go

	q.PopFront() // remove "I"
	q.PopBack()  // remove "Go"

	q.PushFront("Hello")
	q.PushBack("World")

	// Consume deque and print elements.
	for q.Len() != 0 {
		fmt.Println(q.PopFront())
	}
}

运行结果如图：

List

container/list

我们可以直接使用这个链表的实现:

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// Create a new list and put some numbers in it.
	l1 := list.New()

	e4 := l1.PushBack(4)
	e1 := l1.PushFront(1)
	l1.InsertBefore(3, e4)
	l1.InsertAfter(2, e1) // now l1 is [1 2 3 4]

	// Iterate through list and print its contents.
	for e := l1.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}

	l1.MoveToBack(e1) // now l1 is [4 2 3 1]
	listLength := l1.Len() // length is 4

	fmt.Printf("l1 type: %T\n", l1)
	fmt.Println("l1 length : :", listLength)
	for e := l1.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}

}

运行结果为：

1
2
3
4
l1 type: *list.List
l1 length : : 4
2
3
4
1

单链表

最后介绍一下单链表，如果我们想实现的数据结构并没有标准的容器集成，此时我们就可以通过自己根据要求来写一个自己想要的容器类型，这里以头插法的单链表举例：

package main

import "fmt"

type SinglyLinkedList struct {
	head *LinkedListNode
}

type LinkedListNode struct {
	data string
	next *LinkedListNode
}

func (ll *SinglyLinkedList) Append(node *LinkedListNode) {

	if ll.head == nil {
		ll.head = node
		return
	}

	currentNode := ll.head
	for currentNode.next != nil {
		currentNode = currentNode.next
	}
	currentNode.next = node
}

func main() {
	ll := &SinglyLinkedList{}

	ll.Append(&LinkedListNode{data: "Hello"})
	ll.Append(&LinkedListNode{data: "Gopher"})

	for e := ll.head; e != nil; e = e.next {
		fmt.Println(e.data)
	}
}

运行结果如图：

当然，还有更多的容器方法可以等着自己去扩充，这一部分读者感兴趣可以在算法和数据结构的知识点中进行学习。

总结

container

希望本文能对你有所帮助，如果喜欢本文，可以点个赞或关注。

这里是宇宙之一粟，下一篇文章见！

宇宙古今无有穷期，一生不过须臾，当思奋争。