专注于 JetBrains IDEA 全家桶,永久激活,教程
持续更新 PyCharm,IDEA,WebStorm,PhpStorm,DataGrip,RubyMine,CLion,AppCode 永久激活教程

golang基础-高级数据结构

背景

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内置的数据结构,已经可以应对大多数业务场景的开发。后续将会介绍一些更复杂的数据结构,如跳表,二叉树,平衡二叉树,堆。

文章永久链接:https://tech.souyunku.com/38356

未经允许不得转载:搜云库技术团队 » golang基础-高级数据结构

JetBrains 全家桶,激活、破解、教程

提供 JetBrains 全家桶激活码、注册码、破解补丁下载及详细激活教程,支持 IntelliJ IDEA、PyCharm、WebStorm 等工具的永久激活。无论是破解教程,还是最新激活码,均可免费获得,帮助开发者解决常见激活问题,确保轻松破解并快速使用 JetBrains 软件。获取免费的破解补丁和激活码,快速解决激活难题,全面覆盖 2024/2025 版本!

联系我们联系我们