特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64
文件位置：container/list/list.go

1 数据结构

1
2
3
4
5
6
7
8
type Element struct {
    // 指向下一个节点和前一个节点
    next, prev *Element
    // 标识当前element所属的List
    list *List
    // 存储的当前节点值
    Value any
}
1
2
3
4
type List struct {
    root Element // 哨兵节点
    len  int     // 链表长度（不算哨兵节点）
}

两者的关系如下图所示：

image-20230925202523466

2 初始化

1
2
3
4
5
6
func (l *List) Init() *List {
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}
  • 将哨兵节点的next和prev都指向自己，表示当前链表为空
  • 长度len设置为0
  • 返回一个*List
1
2
3
func New() *List { 
    return new(List).Init() 
}
  • 外部通过调用New()创建一个双向链表

image-20230925203236258

1
2
3
4
5
func (l *List) lazyInit() {
    if l.root.next == nil {
        l.Init()
    }
}
  • 懒初始化：如果该链表还为初始化，则调用Init()函数来初始化

3 遍历

返回当前节点的下一个节点

1
2
3
4
5
6
func (e *Element) Next() *Element {
    if p := e.next; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}
  • 如果当前节点已经是最后一个节点，则返回nil
  • 返回当前节点的下一个节点

返回当前节点的前一个节点

1
2
3
4
5
6
func (e *Element) Prev() *Element {
    if p := e.prev; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}
  • 如果当前节点已经是第一个节点，则返回nil
  • 返回当前节点的前一个节点

返回双向链表的第一个节点

1
2
3
4
5
6
func (l *List) Front() *Element {
    if l.len == 0 {
        return nil
    }
    return l.root.next
}
  • 长度为0，则返回nil

返回双向链表的最后一个节点

1
2
3
4
5
6
func (l *List) Back() *Element {
    if l.len == 0 {
        return nil
    }
    return l.root.prev
}
  • 长度为0，则返回nil

image-20230925204108617

4 插入

1
2
3
4
5
6
7
8
9
10
// 在at元素后面插入e，并且返回e，并更新相应的值
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
}
1
2
3
4
// 同样是插入一个元素在at后面，但是只提供一个value，需要帮他创建一个Element
func (l *List) insertValue(v any, at *Element) *Element {
    return l.insert(&Element{Value: v}, at)
}
1
2
3
4
func (l *List) PushFront(v any) *Element {
    l.lazyInit()
    return l.insertValue(v, &l.root)
}
  • 如果链表l没有初始化，则先初始化
  • 插入一个节点值为v的节点在链表l的头部
1
2
3
4
func (l *List) PushBack(v any) *Element {
    l.lazyInit()
    return l.insertValue(v, l.root.prev)
}
  • 如果链表l没有初始化，则先初始化
  • 插入一个节点值为v的节点在链表l的尾部

插入一个节点值v在mark节点前面

1
2
3
4
5
6
func (l *List) InsertBefore(v any, mark *Element) *Element {
    if mark.list != l {
        return nil
    }
    return l.insertValue(v, mark.prev)
}

插入一个节点值v在mark节点后面 

1
2
3
4
5
6
func (l *List) InsertAfter(v any, mark *Element) *Element {
    if mark.list != l {
        return nil
    }
    return l.insertValue(v, mark)
}

将链表other中的节点依次插入到链表l的后面

1
2
3
4
5
6
func (l *List) PushBackList(other *List) {
    l.lazyInit()
    for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
        l.insertValue(e.Value, l.root.prev)
    }
}

将链表other中d节点插入到链表l的前面

1
2
3
4
5
6
func (l *List) PushFrontList(other *List) {
    l.lazyInit()
    for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
        l.insertValue(e.Value, &l.root)
    }
}

5 删除

1
2
3
4
5
6
7
8
9
// 删除节点e
func (l *List) remove(e *Element) {
    e.prev.next = e.next
    e.next.prev = e.prev
    e.next = nil // avoid memory leaks
    e.prev = nil // avoid memory leaks
    e.list = nil
    l.len--
}
1
2
3
4
5
6
func (l *List) Remove(e *Element) any {
    if e.list == l {
        l.remove(e)
    }
    return e.Value
}
  • 如果节点e在链表l中，则调用remove()函数移除该节点
  • 返回节点e的值

6 移动

1
2
3
4
5
6
7
8
9
10
11
12
13
// 将e移到at的后面
func (l *List) move(e, at *Element) {
    if e == at {
        return
    }
    e.prev.next = e.next
    e.next.prev = e.prev

    e.prev = at
    e.next = at.next
    e.prev.next = e
    e.next.prev = e
}

将节点e移到链表l前面

1
2
3
4
5
6
func (l *List) MoveToFront(e *Element) {
    if e.list != l || l.root.next == e {
        return
    }
    l.move(e, &l.root)
}

将节点e移到链表l尾部

1
2
3
4
5
6
func (l *List) MoveToBack(e *Element) {
    if e.list != l || l.root.prev == e {
        return
    }
    l.move(e, l.root.prev)
}

将节点e移到节点mark的前面

1
2
3
4
5
6
func (l *List) MoveBefore(e, mark *Element) {
    if e.list != l || e == mark || mark.list != l {
        return
    }
    l.move(e, mark.prev)
}

将节点e移到节点mark的后面

1
2
3
4
5
6
func (l *List) MoveAfter(e, mark *Element) {
    if e.list != l || e == mark || mark.list != l {
        return
    }
    l.move(e, mark)
}

7 总结

从list.go源码中，看得出实现的还是很容易理解的，跟我们自己实现的双向链表几乎无差别，源码阅读起来应该也是毫无压力