Go语言的双向链表、list操作和双向循环链表

最近在学习Golang，所以将学习过程记为笔记，以后翻阅的时候也方便，顺便也给大家做一点分享，希望能坚持下去。

关注后领取教程：Go语言（基础+进阶+就业）完整版

现在就开始你的Go语言学习之旅吧！人生苦短，let’s Go.

双向链表

1）双向链表的结构

双向链表结构中元素在内存中不是紧邻空间，而是每个元素中存放上一个元素和后一个元素的地址

第一个元素称为（头）元素，前连接（前置指针域）为nil
最后一个元素称为尾（foot）元素，后连接（后置指针域）尾nil

双向链表的优点

在执行新增元素或删除元素时效率高，获取任意一个元素，可以方便的在这个元素前后插入元素
充分利用内存空间，实现内存灵活管理
可实现正序和逆序遍历
头元素和尾元素新增或删除时效率较高

双向链表的缺点

链表增加了元素的指针域，空间开销比较大
遍历时跳跃性查找内容，大量数据遍历性能低

2）双向链表容器List

在Go语言标准库的container/list包提供了双向链表List

List结构体定义如下

root表示根元素
len表示链表中有多少元素

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
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
}

其中Element结构体定义如下

next表示下一个元素，使用Next()可以获取到
prev表示上一个元素，使用Prev()可以获取到
list表示元素属于哪个链表
Value表示元素的值，interface()在Go语言中表示任意类型

// Element is an element of a linked list.
type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The value stored with this element.
    Value interface{}
}

操作List

1)直接使用container/list包下的New()新建一个空的List

添加，遍历，取首尾，取中间元素

package main

import (
    "container/list"
    "fmt"
)

func main() {
    //实例化
    mylist := list.New()
    fmt.Println(mylist)

    //添加
    mylist.PushFront("a")                        //["a"]
    mylist.PushBack("b")                         //["a","b"]
    mylist.PushBack("c")                         //["a","b","c"]
    //在最后一个元素的前面添加
    mylist.InsertBefore("d",mylist.Back())       //["a","b","d","c"]
    mylist.InsertAfter("e",mylist.Front())       //["a","e","b","d","c"]

    //遍历
    for e := mylist.Front(); e != nil; e = e.Next(){
        fmt.Print(e.Value, " ")     //a e b d c
    }
    fmt.Println("")

    //取首尾
    fmt.Println(mylist.Front().Value)     //a
    fmt.Println(mylist.Back().Value)      //c

    //取中间的元素，通过不断的Next()
    n := 3
    var curr *list.Element
    if n > 0 && n <= mylist.Len(){
        if n == 1 {
            curr = mylist.Front()
        }else if n == mylist.Len(){
            curr = mylist.Back()
        }else {
            curr = mylist.Front()
            for i := 1; i < n; i++{
                curr = curr.Next()
            }
        }
    }else {
        fmt.Println("n的数值不对")
    }
    fmt.Println(curr.Value)        //b
}

2）移动元素　

package main

import (
    "container/list"
    "fmt"
)

func main() {
    //实例化
    mylist := list.New()
    fmt.Println(mylist)

    //添加
    mylist.PushFront("a")                        //["a"]
    mylist.PushBack("b")                         //["a","b"]
    mylist.PushBack("c")                         //["a","b","c"]
    //在最后一个元素的前面添加
    mylist.InsertBefore("d",mylist.Back())       //["a","b","d","c"]
    mylist.InsertAfter("e",mylist.Front())       //["a","e","b","d","c"]

    //移动，把第一个元素一道最后一个元素的前面
    mylist.MoveBefore(mylist.Front(),mylist.Back())
    //mylist.MoveAfter(mylist.Back(),mylist.Front())

    //把最后一个元素移动到最前面
    //mylist.MoveToFront(mylist.Back())
    //把第一个元素移动到最后面
    //mylist.MoveToBack(mylist.Front())

    for e := mylist.Front(); e != nil; e = e.Next(){
        fmt.Print(e.Value, " ")     //e b d a c
    }
}

3）删除

mylist.Remove(mylist.Front())

双向循环列表

1）循环链表特点是没有节点的指针域为nil，通过任何一个元素都可以找到其它元素。环形链表结构如下

双向循环链表和双向链表区别

双向循环链表没有严格意义上的头元素和尾元素
没有元素的前连接和后连接为nil
一个长度为n的双向循环链表，通过某个元素向某个方向移动，在查找最多n-1次，一定会找到另一个元素

2）在container/ring包下结构体Ring源码如下

官方明确说明了Ring是循环链表的元素，又是环形链表
实际使用时Ring遍历就是环形链表第一个元素

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

3）创建和查看　　

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    //r代表整个循环链表，又代表第一个元素
    r := ring.New(5)
    r.Value = 0
    r.Next().Value = 1
    r.Next().Next().Value = 2
    //r.Next().Next().Next().Value = 3
    //r.Next().Next().Next().Next().Value = 4
    r.Prev().Value = 4
    r.Prev().Prev().Value = 3
    //查看元素内容
    //循环链表有几个元素，func就执行几次，i当前执行元素的内容
    r.Do(func(i interface{}) {
        fmt.Print(i, " ")      //0 1 2 3 4
    })
    fmt.Println("")
    //取中间元素，用移动
    fmt.Println(r.Move(3).Value)   //3


}

4）增加

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    //r代表整个循环链表，又代表第一个元素
    r := ring.New(5)
    r.Value = 0
    r.Next().Value = 1
    r.Next().Next().Value = 2
    //r.Next().Next().Next().Value = 3
    //r.Next().Next().Next().Next().Value = 4
    r.Prev().Value = 4
    r.Prev().Prev().Value = 3

    //增加
    r1 := ring.New(2)
    r1.Value = 5
    r1.Next().Value = 6
    r.Link(r1)

    r.Do(func(i interface{}) {
        fmt.Print(i, " ")    //0 5 6 1 2 3 4
    })
}

5）删除

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    //r代表整个循环链表，又代表第一个元素
    r := ring.New(5)
    r.Value = 0
    r.Next().Value = 1
    r.Next().Next().Value = 2
    //r.Next().Next().Next().Value = 3
    //r.Next().Next().Next().Next().Value = 4
    r.Prev().Value = 4
    r.Prev().Prev().Value = 3

    //删除
    r.Unlink(1)

    r.Do(func(i interface{}) {
        fmt.Print(i, " ")    //0 2 3 4
    })
}

删除后面两个

//删除
r.Unlink(2)

r.Do(func(i interface{}) {
    fmt.Print(i, " ")    //0 3 4
})

r.Next()删除

//删除
r.Next().Unlink(2)

r.Do(func(i interface{}) {
    fmt.Print(i, " ")    //0 1 4
})qu

超出范围，取5的余数

//删除
r.Unlink(6)

r.Do(func(i interface{}) {
    fmt.Print(i, " ")    //0 2 3 4
})

参考链接：https://www.cnblogs.com/derek1184405959/p/11298618.html

以上是此篇文章的全部内容，文章教程看不懂，可以关注本公众号：Go语言圈，获取视频教程 Go语言（基础+进阶+就业）完整版 助你学习快乐！