golang 系列教程（四）-高级数据结构

4 years ago

source link: https://www.tuicool.com/articles/2UBBJfy
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

golang 不像c++，已经有stl这种通用的高级数据结构。所以如果想要栈，队列，链表等数据结构需要自己实现。

下面介绍下常用的几种数据结构

链表

单链表是一种链式存取的数据结构，一个链表由一个或者多个节点组成，每个节点有一个指针指向下一个节点。以下是一个节点为int的链表实现。

package list

type List struct {
    Head * ListNode
    length int
}

type ListNode struct {
	Next *ListNode
    Data int
}

func (p *List) AddNode(data int) {
    if p.Head == nil {
        p.Head = new(ListNode)
    }
    var node = &ListNode {
        Data : data,
    }
    currentNext := p.Head.Next
    p.Head.Next = node
    node.Next = currentNext
}

func (p *List) Lenth() int {
    return p.length
}

// delete specified pos
func (p *List) DeleteWithPos(pos int) {
    if pos + 1 >  p.length {
        return
    }
    var i int
    pre := p.Head
    for {
        if i == pos {
            pre.Next = pre.Next.Next
        }
        pre = pre.Next
        i++
    }
    return
}

func (p *List) DeleteWithData(data int) {
    pre := p.Head
    for {
        if pre.Next == nil {
            break
        }
        if data == pre.Next.Data {
            pre.Next = pre.Next.Next
        }
        pre = pre.Next
    }
    return
}
复制代码

队列

队列和生活中排队的队伍比较相似。特性是FIFO(first in first out)，先进先出。第一个进入队列的，会第一个出来。举个例子，你去银行存钱，有10个人排队，第一个加入队伍的即1号，必定是第一个办理业务的。

那么看下golang 如何实现一个队列：

package queue

import (
	"errors"
)

type Queue []interface{}

func (queue *Queue) Len() int {
	return len(*queue)
}

func (queue *Queue) IsEmpty() bool {
	return len(*queue) == 0
}

func (queue *Queue) Cap() int {
	return cap(*queue)
}

func (queue *Queue) Push(value interface{}) {
	*queue = append(*queue, value)
}

func (queue *Queue) Pop() (interface{}, error) {
	theQueue := *queue
	if len(theQueue) == 0 {
		return nil, errors.New("Out of index, len is 0")
	}
	value := theQueue[0]
	*queue = theQueue[1:len(theQueue)]
	return value, nil
}
复制代码

栈

一种先入后出的数据结构。栈在生活中的场景，可以对应一个桶，里面装了大米，先放进去的最后才会被取出来。这里使用interface实现一个相对通用的栈。

package stack

import "errors"

type Stack []interface{}

func (stack Stack) Len() int {
	return len(stack)
}

func (stack Stack) IsEmpty() bool {
	return len(stack) == 0
}

func (stack Stack) Cap() int {
	return cap(stack)
}

func (stack *Stack) Push(value interface{}) {
	*stack = append(*stack, value)
}

func (stack Stack) Top() (interface{}, error) {
	if len(stack) == 0 {
		return nil, errors.New("Out of index, len is 0")
	}
	return stack[len(stack)-1], nil
}

func (stack *Stack) Pop() (interface{}, error) {
	theStack := *stack
	if len(theStack) == 0 {
		return nil, errors.New("Out of index, len is 0")
	}
	value := theStack[len(theStack)-1]
	*stack = theStack[:len(theStack)-1]
	return value, nil
}
复制代码

总结

以上是几种常见的高级数据结构，结合golang内置的数据结构，已经可以应对大多数业务场景的开发。后续将会介绍一些更复杂的数据结构，如跳表，二叉树，平衡二叉树，堆。

Recommend

www.flydean.com 2 years ago
Cache

Pandas高级教程之:稀疏数据结构

如果数据中有很多NaN的值，存储起来就会浪费空间。为了解决这个问题，Pandas引入了一种叫做Sparse data的结构，来有效的存储这些NaN的值。 Spare data的例子我们创建一个数组，然后将其大部分数据设置为NaN，接着使用这个数组来创建SparseArra...

微信 mp.weixin.qq.com 4 years ago
Cache

头条高级面试题：请谈谈Redis 9种数据结构以及它们的内部编码实现

90%的人知道Redis 5种最基本的数据结构，只有不到10%的人知道8种基本数据结构（5种基本+bitmap+GeoHash+HyperLogLog），只有不到5%的人知道9种基本数据结构（5.0最新版本数据结构Streams），只有不到1%的人掌握了所有9种基本数...

pylixm.top 3 years ago
Cache

「对比Python学习Go」- 高级数据结构

本篇是「对比Python学习Go」系列的第四篇，本篇文章我们来看下Go的高级数据结构。本系列的其他文章可到

segmentfault.com 3 years ago
Cache

「对比Python学习Go」- 高级数据结构下篇

本篇是「对比 Python 学习 Go」系列的第四篇，本篇文章我们来看下 Go 的高级数据结构，因文章偏长分为两篇，此为下篇。本系列的其他文章可到「对比 Python 学...

sineatos.github.io 2 years ago
Cache

Python标准库: Python高级数据结构

1. collections collections模块包含了内建类型之外的一些有用的工具，例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。 1.1 Counter 如果你想统计一个单词在给定的...