Go源码学习之双向链表

Popwalker · · 946 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

双向链表的定义

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

这里记录一下自己学习理解的过程

图解

[图片上传失败...(image-afe880-1531019243291)]

Go的源码实现

1.首先看一下链表中存储的元素(Element)的定义:

// 双向链表的一个元素 
type Element struct {
  // 前驱指针和后继指针
  prev, next *Element

  // 该元素属于哪个链表list
  list *List

  // 该元素存储的值
  Value interface{} 
}

2.为Element这个结构体定义两个方法:

// Next 返回元素e的后一个元素 
func (e *Element) Next() *Element {
  if p := e.next; e.list != nil && &e.list.root != p {
    return p
  }
  return nil 
}

// Prev 返回元素e的前一个元素 
func (e *Element) Prev() *Element {
  if p := e.prev; e.list != nil && &e.list.root != p {
    return p
  }
  return nil 
}

3.再看链表list的定义:

// List 代表一个双向链表 
// List的零值是一个空的列表 
type List struct {
  // 根节点
  root Element
  
  // 当前链表的长度
  len int 
}

4.为链表List定义一个初始化方法

// Init 初始化一个链表,或者重置一个链表 
func (l *List) Init() (*List) {
  l.root.prev = &l.root
  l.root.next = &l.root
  l.len = 0
  return l 
}

5.为链表List定义一个工厂方法,用来生成一个链表:

func New() *List {
  return new(List).Init() 
}

6.下面看链表核心的两个方法:插入和删除,链表的其他操作方式基本都是基于这两个方法

// insert 在元素at后面插入元素e,将list的长度递增,返回该元素 
func (l *List) insert(e, at *Element) *Element {
  n := at.next
  at.next = e
  e.prev = at
  e.next = n
  n.prev = e
  e.list = l
  l.len ++
  return e 
}

// 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 
}
doubly linked list insert operate

插入操作:

  • 先将元素b的后继指针和元素c的前驱指针删除
  • 然后将元素b的后继指针指向新元素new,将新元素new 的前驱指针指向元素b
  • 再讲元素c的前驱指针指向新元素new,将新元素new 的后继指针指向元素c
  • 最后将链表长度加一
double linked list remove operate

删除操作:

  • 现将元素b的后继指针指向元素d,将元素d的前驱指针指向b
  • 再讲元素c的前驱指针和后继指针删除
  • 将链表长度减一

7.理解了链表的插入和删除操作,就可以在此基础上封装出丰富的链表操作函数:

// insertValue 是对l.insert(&Element{Value:v}, at)的包装
func (l *List) insertValue(v interface{}, at *Element) *Element {
    return l.insert(&Element{Value: v}, at)
}

// Remove 如果元素e是链表l的一个元素,则移除e
// 返回元素e的值e.Value
// 该元素e不能为nil
func (l *List) Remove(e *Element) interface{} {
    if e.list == l {
        l.remove(e)
    }
    return e.Value
}

在链表头部或尾部插入元素:

// PushFront 插入一个包含值v的新元素e到链表l的头部,并返回该元素e
func (l *List) PushFront(v interface{}) *Element {
    l.lazyInit()
    return l.insertValue(v, &l.root)
}

// PushBack 插入一个包含值v的新元素e到链表l的尾部,并返回这个新元素e
func (l *List) PushBack(v interface{}) *Element {
    l.lazyInit()
    return l.insertValue(v, l.root.prev)
}

在某个元素之前或之后插入一个新元素:

// InsertBefore 在元素mark之前插入一个值为v的新元素
// 如果mark不属于链表l,则不会更新链表l,mark也不能为nil
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
    if mark.list != nil {
        return nil
    }
    return l.insertValue(v, mark.prev)
}

// InsertAfter 在元素mark之后插入一个值为v的新元素
// 如果mark不属于链表l,则不会更新链表l,mark也不能为nil
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
    if mark.list != nil {
        return nil
    }
    return l.insertValue(v, mark)
}

将某个元素移动到链表头部或尾部:

// MoveToFront 将元素e移动到链表头部
// 如果元素e不是链表的元素,则不会更新链表
func (l *List) MoveToFront(e *Element) {
    if e.list != l || l.root.next == e {
        return
    }
    l.insert(l.remove(e), &l.root)
}

// MoveToBack 将元素e移动到链表尾部
// 如果元素e不是链表的元素,则不会更新链表
func (l *List) MoveToBack(e *Element) {
    if e.list != l || e == l.root.prev {
        return
    }
    l.insert(l.remove(e), l.root.prev)
}

将元素A移动到元素B之前 或 之后:

// MoveBefore 移动元素e到元素mark之前
func (l *List) MoveBefore(e, mark *Element) {
    if e.list != l || mark.list != l || e == mark {
        return
    }
    l.insert(l.remove(e), mark.prev)
}

// MoveAfter 移动元素e到元素mark之后
func (l *List) MoveAfter(e, mark *Element) {
    if e.list != l || e == mark || mark.list != l {
        return
    }
    l.insert(l.remove(e), mark)
}

上述代码均来自golang源码,详见Go Doc

总结

双向链表并不难理解,只要了理解了其数据结构和插入、删除的原理,就能迅速掌握。

参考:

原文地址:https://popwalker.github.io/article/c78375f9/


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:Popwalker

查看原文:Go源码学习之双向链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

946 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传