golang2021数据格式(74)list原理分析

本文为“Goalng全面深入系列”中的标准库部分。

?

1. 什么是双向链表

(引用)

??????? 和单链表比较，双向链表的元素不但知道自己的下线，还知道自己的上线（越来越像传销组织了）。小煤车开起来，图里面可以看出，每个车厢除了一个指向后面车厢的箭头外，还有一个指向前面车厢的箭头（车头、车尾除外）。车头只有指向后面车厢的箭头，车尾只有指向前面车厢的箭头。

2. 和单向链表相比的优势

??? 1. 插入删除不需要移动元素外，可以原地插入删除

??? 2. 可以双向遍历

??? 插入数据到中间

删除中间数据

3、双向链表与Go的对应结构

1.节点分析

我们先把车厢分解开来。每节车厢都由煤炭、车体、拉前车厢绳索、拉后车厢绳索这4部分组成。车体是我们的运输工具，在Go语言里我们用结构提DNode表示；煤炭代表运的货物，用data变量表示；拉前车厢绳索和拉后车厢绳索我们分别用指针prev和next表示。这样一节车厢，用Go语言描述如下:

type DNode struct {
?data Object
?prev *DNode
?next *DNode
}

2、双向链表

一个运煤车队就是一个双向链表。车队要有车头、车厢、车尾，作为车队的负责人还得知道车队有多长。在Go语言里，车队用结构体DList表示，车头用head变量表示，车位用tail变量表示，车队长度就用size来表示，把这些表示合起来：

type DList struct {
?size uint64
?head *DNode
?tail *DNode
}

通过找到其中一个节点，就可以通过prev 或 next指向得到指向的数据。

?

4. Go自定义实现链表

1.初始化Init

??? 双向链表的初始化，可以理解成大卫哥准备买一个车队准备运煤。第一步，得获得国家有关部门的批准，有了批准大卫哥就可以买车厢运煤了。但是，批准下来的时候，大卫哥的车队啥都没有，没有车头、车尾，连一节车厢也没有。Go语言代码实现：

package main

//节点数据结构
type DNode struct {
??????? data interface{}
??????? prev *DNode
??????? next *DNode
}

// 链表数据结构
type DList struct {
??????? size uint64
??????? head *DNode
??????? tail *DNode
}

// 链表的初始化
func InitList() (list *DList) {
??????? list = *(DList)
??????? list.size = 0
??????? list.head = nil
??????? list.tail = nil
??????? return
}

// 新增数据
func (dlist *DList) Append(data interface{}) {
??????? // 创建一个节点
??????? newNode := &DNode{data: data}

if (*dlist).GetSize() == 0 { //只有一个节点
??????????????? (*dlist).head = newNode
??????????????? (*dlist).tail = newNode // 头尾节点都是自己
??????????????? (*newNode).prev = nil?? // 但是头尾的指向是nil
??????????????? (*newNode).next = nil
??????? } else { // 接到尾部
??????????????? // 新节点的指向修改
??????????????? (*newNode).prev = (*dlist).tail
??????????????? (*newNode).next = nil

// 之前尾节点的指向修改
??????????????? (*(*dlist).tail).next = newNode // 将之前的尾节点的next指向新增节点

// 更新链表的尾节点
??????????????? (*dlist).tail = newNode
??????? }

// 更新链表的节点计数
??????? (*dlist).size++
}

// 在节点后面插入数据InsertNext
//param
//??????? - ele 所要插入的位置
//??????? - data 所要插入的节点数据
//
func (dlist *DList) InsertNext(ele *DNode, data interface{}) bool {
??????? if ele == nil {
??????????????? return false
??????? }

if dlist.isTail(ele) { //正好在尾部
??????????????? dlist.Append(data)
??????? } else { // 在中间插入
??????????????? //构造新节点
??????????????? newNode := new(DNode)
??????????????? (*newNode).data = data
??????????????? (*newNode).prev = ele???????? // 上一个节点就是ele
??????????????? (*newNode).next = (*ele).next // 下一个节点就是ele原来的下一个节点

// ele的下一个指向新节点
??????????????? (*ele).next = newNode

// ele之前下节点的prev重新指向新节点
??????????????? *((*newNode).next).prev = newNode

// 更新链表计数
??????????????? (*dlist).size++
??????? }
}

//*====
节点之前插入接口都是类似的方式：
??????? 1. 首先根据数据创建新节点， 并设置指向
??????? 2. 更新位置节点的指向数据
??????? 3. 更新链表head , tail ,size数据

删除节点：
??????? 1. 首先获取要删除节点指向数据
??????? (验证头尾)
??????? 2. 更新要删除节点的prev节点的next为要删除节点的next节点（ 有点乱啊！！）
??????? 3. 更新链表数据

记得return要删除的节点数据（否则数据丢失）

查找节点：
??????? type MatchFun func (data1 interface{}, data2 interface{}) int
??????? func (dList *DList) Search(data Object, yourMatch MatchFun) *DNode

*=====*//

// 获取链表长度GetSize
func (dList *DList) GetSize() uint64 {
??????? return (*dList).size
}

//获取头部节点GetHead

func (dList *DList) GetHead() *DNode {
??????? return (*dList).head
}

//获取尾部节点GetTail

func (dList *DList) GetTail() *DNode {
??????? return (*dList).tail
}

?

通过自己实现链表，来更深入了解链表的结构后， 我们使用go的 container/list 库实现。

?

5.Go库container/list 实现链表操作

关于库的成员函数，我就不一一列举了， 看一看文档很详细，也很简单。

下面直接上案例：

func main() {
??????? link := list.New()

// 循环插入到头部
??????? for i := 0; i <= 10; i++ {
??????????????? link.PushBack(i)
??????? }

// 遍历链表
??????? for p := link.Front(); p != link.Back(); p = p.Next() {
??????????????? fmt.Println("Number", p.Value)
??????? }

}

?

6. slice和list的性能比较

1. 创建、 添加元素的比较

package main

import (
??????? "container/list"
??????? "fmt"
??????? "time"
)
func main(){
? T1()
}

func T1() {
??????? t := time.Now()
??????? //1亿创建添加测试
??????? // slice 创建

slice := make([]int, 10)
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? slice = append(slice, i)
??????? }
??????? fmt.Println("slice 创建成功：", time.Now().Sub(t).String())

// list创建添加
??????? t = time.Now()
??????? l := list.New()
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? l.PushBack(i)
??????? }
??????? fmt.Println("list创建成功：", time.Now().Sub(t).String())
}
func T2() {
??????? sli := make([]int, 10)
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? sli = append(sli, 1)
??????? }

l := list.New()
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? l.PushBack(1)
??????? }
??????? // 比较遍历
??????? t := time.Now()
??????? for _, _ = range sli {
??????????????? //fmt.Printf("values[%d]=%d\n", i, item)
??????? }
??????? fmt.Println("遍历slice的速度:" + time.Now().Sub(t).String())
??????? t = time.Now()
??????? for e := l.Front(); e != nil; e = e.Next() {
??????????????? //fmt.Println(e.Value)
??????? }
??????? fmt.Println("遍历list的速度:" + time.Now().Sub(t).String())
}
func T3() {
??????? sli := make([]int, 10)
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? sli = append(sli, 1)
??????? }

l := list.New()
??????? for i := 0; i < 1*100000*1000; i++ {
??????????????? l.PushBack(1)
??????? }
??????? //比较插入
??????? t := time.Now()
??????? slif := sli[:100000*500]
??????? slib := sli[100000*500:]
??????? slif = append(slif, 10)
??????? slif = append(slif, slib...)
??????? fmt.Println("slice 的插入速度" + time.Now().Sub(t).String())

var em *list.Element
??????? len := l.Len()
??????? var i int
??????? for e := l.Front(); e != nil; e = e.Next() {
??????????????? i++
??????????????? if i == len/2 {
??????????????????????? em = e
??????????????????????? break
??????????????? }
??????? }
??????? //忽略掉找中间元素的速度。
??????? t = time.Now()
??????? ef := l.PushBack(2)
??????? l.MoveBefore(ef, em)
??????? fmt.Println("list: " + time.Now().Sub(t).String())
}

简单的测试下，如果频繁的插入和删除建议用list,频繁的遍历查询选slice。

由于container/list不是并发安全的，所以需要自己手动添加一层并发的包装。