Go container包的介绍

目录
  • 1.简介
  • 2.list
    • 2.1数据结构
    • 2.2插入元素
  • 3.ring
    • 3.1数据结构
  • 4.heap
    • 4.1数据结构

1.简介

Container — 容器数据类型:该包实现了三个复杂的数据结构:堆、链表、环

  • List:Go中对链表的实现,其中List:双向链表,Element:链表中的元素
  • Ring:实现的是一个循环链表,也就是我们俗称的环
  • Heap:Go中对堆的实现

2.list

简单实用:

func main()  {
 // 初始化双向链表
 l := list.New()
 // 链表头插入
 l.PushFront(1)
 // 链表尾插入
 l.PushBack(2)
 l.PushFront(3)
 // 从头开始遍历
 for head := l.Front();head != nil;head = head.Next() {
  fmt.Println(head.Value)
 }
}

方法列表:

type Element
    func (e *Element) Next() *Element                                   // 返回该元素的下一个元素,如果没有下一个元素则返回 nil
    func (e *Element) Prev() *Element                                   // 返回该元素的前一个元素,如果没有前一个元素则返回nil

type List
    func New() *List                                                    // 返回一个初始化的list
    func (l *List) Back() *Element                                      // 获取list l的最后一个元素
    func (l *List) Front() *Element                                     // 获取list l的第一个元素
    func (l *List) Init() *List                                         // list l 初始化或者清除 list l
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element   // 在 list l 中元素 mark 之后插入一个值为 v 的元素,并返回该元素,如果 mark 不是list中元素,则 list 不改变
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在 list l 中元素 mark 之前插入一个值为 v 的元素,并返回该元素,如果 mark 不是list中元素,则 list 不改变
    func (l *List) Len() int                                            // 获取 list l 的长度
    func (l *List) MoveAfter(e, mark *Element)                          // 将元素 e 移动到元素 mark 之后,如果元素e 或者 mark 不属于 list l,或者 e==mark,则 list l 不改变
    func (l *List) MoveBefore(e, mark *Element)                         // 将元素 e 移动到元素 mark 之前,如果元素e 或者 mark 不属于 list l,或者 e==mark,则 list l 不改变
    func (l *List) MoveToBack(e *Element)                               // 将元素 e 移动到 list l 的末尾,如果 e 不属于list l,则list不改变
    func (l *List) MoveToFront(e *Element)                              // 将元素 e 移动到 list l 的首部,如果 e 不属于list l,则list不改变
    func (l *List) PushBack(v interface{}) *Element                     // 在 list l 的末尾插入值为 v 的元素,并返回该元素
    func (l *List) PushBackList(other *List)                            // 在 list l 的尾部插入另外一个 list,其中l 和 other 可以相等
    func (l *List) PushFront(v interface{}) *Element                    // 在 list l 的首部插入值为 v 的元素,并返回该元素
    func (l *List) PushFrontList(other *List)                           // 在 list l 的首部插入另外一个 list,其中 l 和 other 可以相等
    func (l *List) Remove(e *Element) interface{}                       // 如果元素 e 属于list l,将其从 list 中删除,并返回元素 e 的值

2.1数据结构

节点定义:

type Element struct {
 // 后继指针,前向指针
 next, prev *Element

 // 链表指针,属于哪个链表
 list *List

 // 节点value
 Value interface{}
}

双向链表定义:

type List struct {
  // 根元素
 root Element // sentinel list element, only &root, root.prev, and root.next are used
 // 实际节点数量
  len  int     // current list length excluding (this) sentinel element
}

初始化:

// 通过工厂方法返回list指针
func New() *List { return new(List).Init() }

func (l *List) Init() *List {
 l.root.next = &l.root
 l.root.prev = &l.root
 l.len = 0
 return l
}

这里可以看到root节点作为一个根节点,不承担数据,也不是实际的链表节点,节点数量len没算上它,再初始化的时候,root节点会成为一个只有一个节点的环(前后指针都指向自己)

2.2插入元素

头插法:

func (l *List) Front() *Element {
 if l.len == 0 {
  return nil
 }
 return l.root.next
}

func (l *List) PushFront(v interface{}) *Element {
 l.lazyInit()
 return l.insertValue(v, &l.root)
}

尾插法:

func (l *List) Back() *Element {
 if l.len == 0 {
  return nil
 }
 return l.root.prev
}

func (l *List) PushBack(v interface{}) *Element {
 l.lazyInit()
 return l.insertValue(v, l.root.prev)
}

在指定元素后新增元素:

func (l *List) insert(e, at *Element) *Element {
 e.prev = at
 e.next = at.next
 e.prev.next = e
 e.next.prev = e
 e.list = l
 l.len++
 return e
}

这里有个延迟初始化的逻辑:lazyInit,把初始化操作延后,仅在实际需要的时候才进行

func (l *List) lazyInit() {
 if l.root.next == nil {
  l.Init()
 }
}

移除元素:

// remove 从双向链表中移除一个元素e,递减链表的长度,返回该元素e
func (l *List) remove(e *Element) *Element {
  e.prev.next = e.next
  e.next.prev = e.prev
  e.next = nil // 防止内存泄漏
  e.prev = nil // 防止内存泄漏
  e.list = nil
  l.len --
  return e
}

3.ring

Go中提供的ring是一个双向的循环链表,与list的区别在于没有表头和表尾,ring表头和表尾相连,构成一个环

使用demo:

func main()  {

 // 初始化3个元素的环,返回头节点
 r := ring.New(3)
 // 给环填充值
 for i := 1;i <= 3;i++{
  r.Value = i
  r = r.Next()
 }
 sum := 0
 // 对环的每个元素进行处理
 r.Do(func(i interface{}) {
  sum = i.(int) + sum
 })
 fmt.Println(sum)
}

方法列表:

type Ring
    func New(n int) *Ring  // 初始化环
    func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
    func (r *Ring) Len() int // 环长度
    func (r *Ring) Link(s *Ring) *Ring // 连接两个环
    func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前(n 可以为负数)
    func (r *Ring) Next() *Ring // 当前元素的下个元素
    func (r *Ring) Prev() *Ring // 当前元素的上个元素
    func (r *Ring) Unlink(n int) *Ring // 从当前元素开始,删除 n 个元素

3.1数据结构

环节点数据结构:

type Ring struct {
 next, prev *Ring // 前继和后继指针
 Value      interface{} // for use by client; untouched by this library
}

初始化一个环:后继和前继指针都指向自己

func (r *Ring) init() *Ring {
 r.next = r
 r.prev = r
 return r
}

初始化指定数量个节点的环

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) Do(f func(interface{})) {
 if r != nil {
  f(r.Value)
  for p := r.Next(); p != r; p = p.next {
   f(p.Value)
  }
 }
}

4.heap

Go中堆使用的数据结构是最小二叉树,即根节点比左边子树和右边子树的所有值都小

使用demo:需要实现Interface接口,go中堆都是实现这个接口,定义了排序,插入和删除方法

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

实现接口:

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
 // Push and Pop use pointer receivers because they modify the slice's length,
 // not just its contents.
 *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
 old := *h
 n := len(old)
 x := old[n-1]
 *h = old[0 : n-1]
 return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
 h := &IntHeap{2, 1, 5}
 heap.Init(h)
 heap.Push(h, 3)
 fmt.Printf("minimum: %d\n", (*h)[0])
 for h.Len() > 0 {
  fmt.Printf("%d ", heap.Pop(h))
 }
 // Output:
 // minimum: 1
 // 1 2 3 5
}

4.1数据结构

上浮:

func Push(h Interface, x interface{}) {
 h.Push(x)
 up(h, h.Len()-1)
}

func up(h Interface, j int) {
 for {
  i := (j - 1) / 2 // parent
  if i == j || !h.Less(j, i) {
   break
  }
  h.Swap(i, j)
  j = i
 }
}

下沉:

func Pop(h Interface) interface{} {
 n := h.Len() - 1
 h.Swap(0, n)
 down(h, 0, n)
 return h.Pop()
}

func down(h Interface, i0, n int) bool {
 i := i0
 for {
  j1 := 2*i + 1
  if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
   break
  }
  j := j1 // left child
  if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
   j = j2 // = 2*i + 2  // right child
  }
  if !h.Less(j, i) {
   break
  }
  h.Swap(i, j)
  i = j
 }
 return i > i0
}

到此这篇关于Go container包的介绍的文章就介绍到这了,更多相关Go container包内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 基于golang中container/list包的用法说明

    list是一个双向链表 该结构具有链表的所有功能. type Element type Element struct { Value interface{} //在元素中存储的值 } func (e *Element) Next() *Element //返回该元素的下一个元素,如果没有下一个元素则返回nil func (e *Element) Prev() *Element//返回该元素的前一个元素,如果没有前一个元素则返回nil. type List func New() *List //返

  • 解决golang中container/list包中的坑

    golang中list包用法可以参看这篇文章 但是list包中大部分对于e *Element进行操作的元素都可能会导致程序崩溃,其根本原因是e是一个Element类型的指针,当然其也可能为nil,但是golang中list包中函数没有对其进行是否为nil的检查,变默认其非nil进行操作,所以这种情况下,便可能出现程序崩溃. 1.举个简单例子 Remove()函数 package main import ( "container/list" "fmt" ) func

  • Go container包的介绍

    目录 1.简介 2.list 2.1数据结构 2.2插入元素 3.ring 3.1数据结构 4.heap 4.1数据结构 1.简介 Container - 容器数据类型:该包实现了三个复杂的数据结构:堆.链表.环 List:Go中对链表的实现,其中List:双向链表,Element:链表中的元素 Ring:实现的是一个循环链表,也就是我们俗称的环 Heap:Go中对堆的实现 2.list 简单实用: func main() { // 初始化双向链表 l := list.New() // 链表头插

  • Go container包的介绍

    目录 1.简介 2.list 2.1数据结构 2.2插入元素 3.ring 3.1数据结构 4.heap 4.1数据结构 1.简介 Container - 容器数据类型:该包实现了三个复杂的数据结构:堆.链表.环 List:Go中对链表的实现,其中List:双向链表,Element:链表中的元素 Ring:实现的是一个循环链表,也就是我们俗称的环 Heap:Go中对堆的实现 2.list 简单实用: func main() { // 初始化双向链表 l := list.New() // 链表头插

  • linux内核编程container of()函数介绍

    前言 在linux 内核编程中,会经常见到一个宏函数container_of(ptr,type,member), 但是当你通过追踪源码时,像我们这样的一般人就会绝望了(这一堆都是什么呀? 函数还可以这样定义??? 怎么还有0呢???  哎,算了,还是放弃吧...). 这就是内核大佬们厉害的地方,随便两行代码就让我们怀疑人生,凡是都需要一个过程,慢慢来吧. 其实,原理很简单:  已知结构体type的成员member的地址ptr,求解结构体type的起始地址. type的起始地址 = ptr - s

  • Python中的模块和包概念介绍

    模块概述 如果说模块是按照逻辑来组织 Python 代码的方法, 那么文件便是物理层上组织模块的方法. 因此, **一个文件被看作是一个独立模块, 一个模块也可以被看作是一个文件. 模块的文件名就是模 块的名字加上扩展名 .py . 与其它可以导入类(class)的语言不同,在 Python 中你导入的是模块或模块属性**. 模块名称空间 一个名称空间就是一个名称到对象的关系映射. 导入模块 导入模块整体(import) 方式一 复制代码 代码如下: import module1 import

  • Node.js的包详细介绍

    在Node.js语言中,包和模块并没有本质的不同,包是在模块的基础上更深一步的抽象,包将某个独立的功能封装起来,用于发布.更新.依赖管理和进行版本控制.Node.js根据CommonJS规范实现了包机制,开发了npm来解决包的发布和获取需求. Node.js的包是一个目录,其中包含JSON格式的包说明文件package.json.Node.js的包基本遵循CommonJS规范,因此具备以下特征: CommonJS规范定义的包特性: 1)顶层目录包含package.json文件: 2)bin目录存

  • 使用android-apktool来逆向(反编译)APK包方法介绍

    谷歌官方提供了apktool可以逆向已经发布出去的APK应用,即反编译已经打包成功的APK文件,使用它可以将其反编译成非常接近打包前的原始格式,对于APK来说,可以具体的逆向AndroidManifest.xml.资源文件resources.arsc以及将dex文件反编译成可以调试的smali文件. Warnning 但apktool并不等于是可以用来侵犯前作者的作品的工具,所以使用apktool工具的用户千万不用用其来进行不正当.非法的使用. It is NOT intended for pi

  • Java语言Lang包下常用的工具类介绍

    无论你在开发哪中 Java 应用程序,都免不了要写很多工具类/工具函数.你可知道,有很多现成的工具类可用,并且代码质量都很不错,不用你写,不用你调试,只要你发现. 在 Apache Jakarta Common 中, Lang 这个 Java 工具包是所有 Apache Jakarta Common 项目中被使用最广泛的,几乎你所知道的名气比较大的软件里面都有用到它,包括 Tomcat, Weblogic, Websphere, Eclipse 等等.我们就从这个包开始介绍整个 common 项

  • Python包和模块的分发详细介绍

    发布Python包 上一篇介绍了如何使用别人的轮子,现在我们讨论下如何自己造轮子给别人用. 作为一个流行的开源开发项目,Python拥有一个活跃的贡献者和用户支持社区,这些社区也可以让他们的软件可供其他Python开发人员在开源许可条款下使用.这允许Python用户有效地共享和协作,从其他人已经创建的解决方案中受益于常见(有时甚至是罕见的)问题,以及可以提供他们自己的解决方案. Pypi( Python Package Index) ,公共的模块存储中心 准备 distutils 官方库dist

  • Android手机使用Fiddler方法介绍

    Fiddler是一款免费的抓包.调试工具,比Wireshark要小巧,更简洁,本节就来介绍如何通过WIFI来抓取Android手机的HTTP和HTTPS包. 一.连接Android手机 1.1.手机端配置 电脑配置WIFI后,手机需要设置当前WIFI的代理,而这个代理地址可以通过电脑的"ipconfig"命令得到,如下图所示: 以上的192.168.191.1就是本机的IP地址,然后在手机端的WIFI的高级设置中将代理地址设置为查询到的IP,端口号码自己定义,一会儿要用到,IP代理模式

  • golang中的net/rpc包使用概述(小结)

    RPC,即 Remote Procedure Call(远程过程调用),说得通俗一点就是:调用远程计算机上的服务,就像调用本地服务一样. 我的项目是采用基于Restful的微服务架构,随着微服务之间的沟通越来越频繁,消耗的系统资源越来越多,于是乎就希望可以改成用rpc来做内部的通讯,对外依然用Restful.于是就想到了golang标准库的rpc包和google的grpc. 这篇文章重点了解一下golang的rpc包. 介绍 golang的rpc支持三个级别的RPC:TCP.HTTP.JSONR

随机推荐