【Go 数据结构】链表，栈与队列

链表

单链表

链表是一个个数据节点组成的，它是一个递归结构，要么为空，要么它存在一个指向另外一个数据节点的引用。

简单的链表：

package main

import "fmt"

// 单链表
type LinkNode struct {
	Data     int64
	NextNode *LinkNode
}

func main() {
	node := new(LinkNode)

	node.Data = 1

	node1 := new(LinkNode)
	node1.Data = 2
	node.NextNode = node1

	node2 := new(LinkNode)
	node2.Data = 3
	node1.NextNode = node2

	// print list data
	nowNode := node
	for {
		if nowNode != nil {
			fmt.Println(nowNode.Data)

			nowNode = nowNode.NextNode
			continue
		}
		break
	}

}

打印结果为：

1
2
3

除了单链表我们还需要知道哪些链表呢？

1. 双链表。每个节点既可以找到它之前的节点也可以找到它后面的节点，是双向的。=
2. 循环链表。从一个点开始往下寻找数据，转一圈之后仍可以回到它本身那个节点，形成一个回路。
3. 循环单链表和循环双链表的区别就是，一个只能一个方向走，一个可以两个方向走。

接下来，我们来实现一下循环链表。

循环链表

定义结构:

type Ring struct {
	next, prev *Ring
	Value      interface{}
}

循环链表有三个字段，next 表示后驱节点，prev 表示前驱节点， Value 表示值。

初始化循环链表

// 初始化循环链表
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

创建指定大小

// New 创建一个链表
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

获取上一个/下一个节点

/*
获取下一个节点
获取上一个节点
*/

func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

func (r *Ring) Prev() *Ring {
	if r.prev == nil {
		return r.init()
	}
	return r.prev
}

获取第 n 个节点

// 当 n 为负数的时候，表示向前移动，当 n 为正数的时候，表示向后移动

func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

添加节点

// 往节点A， 连接一个节点，并且返回之前节点 p 的后驱节点
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

也就是说，在节点 r 之后插入一个新的节点 s ，而 r 节点之前的后继节点，将会链接到新节点后面，并且返回之前的第一个后驱节点 n。

删除节点

// 删除节点后的第 n 个节点

func (r *Ring) Unlink(n int) *Ring {
	if n < 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

获取长度

// 获取链表长度
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

数组与链表

一个简单的数组做成的链表：

func ArrayLink() {
	type Value struct {
		Data      string
		NextIndex int64
	}

	var array [5]Value

	array[0] = Value{"a", 3}
	array[1] = Value{"b", 4}
	array[2] = Value{"c", 1}
	array[3] = Value{"d", 2}
	array[4] = Value{"e", -1}

	node := array[0]
	for {
		fmt.Println(node.Data)
		if node.NextIndex == -1 {
			break
		}
		node = array[node.NextIndex]
	}

}

链表和数组是两个不同的概念。一个是编程语言的基本数据类型，表示一个连续的内存地址空间，可以通过一个索引来访问数据。另一个是我们自己定义的数据结构，通过一个数据节点，我们可以定位到另一个数据节点上，不要求连续的空间。

数组的优点是占用空间小，查询快，直接使用索引就可以获取数据元素，缺点是移动和删除数据元素要移动大量的空间。

链表的优点是移动和删除元素速度快，只需要把相关元素重新链接在一起就可以了，但缺点是占用空间大，查询需要进行遍历。

可变长数组

其实在 Golang 中实现对于变长数组，那就是我们熟悉的 Slice 切片。

接下来，我们会自己动手将 Slice 的底层实现一下，原理大致与切片类似。

定义数据类型

// Array 定义可变长的数组
type Array struct {
	array []int       // 使用切片来代替
	len   int         //  表示数组的真实长度
	cap   int         // 容量
	lock  *sync.Mutex // 并发安全使用锁
}

初始化数组

func Make(len, cap int) *Array {
	s := new(Array)
	if len > cap {
		panic("len > cap")
	}

	// 把切片当做数组来用
	array := make([]int, cap, cap)

	// 元数据
	s.array = array
	s.len = 0
	s.cap = cap
	s.lock = &sync.Mutex{} // 初始化锁
	return s
}

我们可以使用满容量和满长度的切片来充当固定数组。

添加元素

// Append 向数组中添加一个元素，如果数组已满，则自动扩容
func (a *Array) Append(element int) {
	a.lock.Lock()
	defer a.lock.Unlock()

	if a.len == a.cap {
		newCap := a.len * 2

		if a.cap == 0 {
			newCap = 1
		}

		newArray := make([]int, newCap, newCap)

		// 把老的数据传输到新的数组里边
		for k, v := range a.array {
			newArray[k] = v
		}

		a.array = newArray
		a.cap = newCap
	}

	a.array[a.len] = element
	a.len = a.len + 1
}

添加多个元素

// AppendMany 向数组中添加多个元素
func (a *Array) AppendMany(element ...int) {
	for _, v := range element {
		a.Append(v)
	}
}

为什么我们这里要使用锁呢？

在并发编程中，锁是一种同步机制，用于保证在任何时刻至多有一个线程执行某一段代码，这段代码通常被称为临界区。

如果在 Append 和 AppendMany 方法中不使用锁，则当多个 goroutine 同时调用这些方法时，它们可能会同时访问和修改 Array 的状态（如 len 和 cap ），这可能会导致数据竞争，并产生不一致的状态，例如你可能会遇到以下情况：

• 两个 goroutines 同时读取 Array 的长度（假设为 n ）
• 它们各自向 Array 添加一个元素
• 由于它们读取的长度都是 n，所以它们都会将元素添加到索引 n 的位置，从而导致一个元素被覆盖

通过在修改 Array 状态的操作前后获取和释放锁，我们可以保证在任何时间只有一个 goroutine 在执行这些操作，从而避免上述情况的发生。

获取指定下表元素

// Get 通过下标获取元素
func (a *Array) Get(index int) int {
	// 处理越界
	if a.len == 0 || index >= a.len {
		panic("index over len")
	}
	return a.array[index]
}

获取长度和容量

// Len 返回真实的长度
func (a *Array) Len() int {
	return a.len
}

// Cap 返回真实的容量
func (a *Array) Cap() int {
	return a.cap
}

辅助打印函数

func PrintArray(array *Array) (result string) {
	result = "["
	for i := 0; i < array.Len(); i++ {
		// 获取第一个元素
		if i == 0 {
			result += fmt.Sprintf("%s%d", result, array.Get(i))
			continue
		}

		result = fmt.Sprintf("%s, %d", result, array.Get(i))
	}
	result = result + "]"
	return
}

栈与队列

先说一下栈与队列的基本特点：

• 栈：先进后出，先进队的元素最后出来
• 队列：后进先出，先进队的元素先出来

对于这两种结构的实现，我们可以使用数组和链表两种实现方式，各有优缺点。

数组栈

定义数据类型

type ArrayStack struct {
	array []string
	size  int
	lock  sync.Mutex
}

入栈

// Push 入栈
func (stack *ArrayStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	stack.array = append(stack.array, v)

	stack.size++
}

出栈

// Pop 出栈
func (stack *ArrayStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	if stack.size == 0 {
		panic("stack is empty")
	}
	v := stack.array[stack.size-1]

	// 收缩切片，但空间可能会越拉越大
	//stack.array = stack.array[:stack.size-1]

	// 创建新的切片，长度为原来的长度-1，但是移动次数较多
	newArray := make([]string, stack.size-1, stack.size-1)
	for i := 0; i < stack.size-1; i++ {
		newArray[i] = stack.array[i]
	}
	stack.array = newArray

	stack.size--

	return v
}

获取栈顶元素

// Peek 查看栈顶
func (stack *ArrayStack) Peek() string {
	if stack.size == 0 {
		panic("stack is empty")
	}
	v := stack.array[stack.size-1]
	return v
}

获取栈大小

// Size 大小
func (stack *ArrayStack) Size() int {
	return stack.size
}

判断栈是否为空

// IsEmpty 是否为空
func (stack *ArrayStack) IsEmpty() bool {
	return stack.size == 0
}

链表栈

定义数据类型

type LinkNode struct {
	Value string
	Next  *LinkNode
}

type LinkStack struct {
	root *LinkNode // 链表起点
	size int
	lock sync.Mutex
}

入栈

// Push 入栈
func (stack *LinkStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	// 表示栈目前为空，直接向栈顶插入元素
	if stack.root == nil {
		stack.root = &LinkNode{Value: v, Next: nil}
	} else {
		// 将元素插入到栈顶 , 头插法
		preNode := stack.root

		// 新节点
		newNode := new(LinkNode)
		newNode.Value = v

		newNode.Next = preNode

		// 更新 root
		stack.root = newNode
	}
	stack.size++
}

出栈

// Pop 弹出栈顶元素
func (stack *LinkStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	if stack.size == 0 {
		panic("stack is empty")
	}

	// 栈顶元素
	topNode := stack.root
	stack.root = topNode.Next

	stack.size--

	return topNode.Value
}

获取栈顶元素

// Peek 栈顶元素
func (stack *LinkStack) Peek() string {
	// 栈为空
	if stack.size == 0 {
		panic("stack is empty")
	}
	// 栈顶元素
	v := stack.root.Value
	return v
}

获取栈的大小

// Size 栈大小
func (stack *LinkStack) Size() int {
	return stack.size
}

判断是否为空栈

// IsEmpty 栈是否为空
func (stack *LinkStack) IsEmpty() bool {
	return stack.size == 0
}

数组队列

定义数据类型

type ArrayQueue struct {
	array []string
	size  int
	lock  sync.Mutex
}

入队

// Add 添加一个元素給队列
func (queue *ArrayQueue) Add(v string) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	queue.array = append(queue.array, v)

	queue.size++
}

出队

// Remove 移除队列的第一个元素
func (queue *ArrayQueue) Remove() string {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	if queue.size == 0 {
		panic("Queue is empty")
	}

	v := queue.array[0]

	/* 原地移动，但缩容后空间不会被释放
	for i := 1; i < queue.size; i++ {
		queue.array[i-1] = queue.array[i]
	}
	// 缩容后，数组长度减1
	queue.array = queue.array[:queue.size-1]
	*/
	newArray := make([]string, queue.size-1, queue.size-1)
	for i := 1; i < queue.size; i++ {
		newArray[i-1] = queue.array[i]
	}
	queue.array = newArray
	queue.size--
	return v
}

链表队列

定义数据类型

type LinkNode struct {
	Next  *LinkNode
	Value string
}

type LinkQueue struct {
	root *LinkNode
	size int
	lock sync.Mutex
}

入队

// Add 新元素入队
func (queue *LinkQueue) Add(v string) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队列为空直接入队, 尾查法
	if queue.root == nil {
		queue.root = &LinkNode{Value: v, Next: nil}
	} else {
		newNode := new(LinkNode)
		newNode.Value = v

		nowNode := queue.root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}
		nowNode.Next = newNode

		queue.size++
	}
}

出队

func (queue *LinkQueue) Remove() string {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队列为空直接返回
	if queue.root == nil {
		panic("queue is empty")
	}
	// 头部出元素
	topNode := queue.root
	v := topNode.Value

	queue.root = queue.root.Next
	queue.size--
	return v
}

总结

本次我们介绍使用Go语言实现数据结构中的链表，栈与队列。数据结构这一系列我们没有涉及到具体的细节的讲解，适合有一定数据结构基础的童鞋，本系列代码已经上传至Github，欢迎大家 Star。