链表
单链表
链表是一个个数据节点组成的，它是一个递归结构，要么为空，要么它存在一个指向另外一个数据节点的引用。
简单的链表：
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
除了单链表我们还需要知道哪些链表呢？
- 双链表。每个节点既可以找到它之前的节点也可以找到它后面的节点，是双向的。=
- 循环链表。从一个点开始往下寻找数据，转一圈之后仍可以回到它本身那个节点，形成一个回路。
- 循环单链表和循环双链表的区别就是，一个只能一个方向走，一个可以两个方向走。
接下来，我们来实现一下循环链表。
循环链表
定义结构:
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。
