Go源码学习之双向链表

双向链表的定义

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

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

图解

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 
}

插入操作：

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

删除操作：

• 现将元素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

总结

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

参考：

• Doubly linked list - wikipedia
• container/list - Go Doc
• 数组、单链表和双链表介绍 以及 双向链表的C/C++/Java实现