Go数据结构与算法01-链表: 深入理解container/list&LRU缓存的实现

• Go 数据结构与算法系列文章，本系列文章主要会包括常见的数据结构与算法实现，同时会包括 Go 标准库代码的分析理解，讲到对应章节的时候优先学习分析 Go 的源码实现，例如 slice、list、sort 等，然后可能会有一些常见的案例实现，同时这也是 极客时间-数据结构与算法之美 的课程笔记
• 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
• RoadMap: 持续更新中，预计一周更新 1 ~ 2 篇文章，预计到 202101 月底前更新完成
• 获取更新: Github、知乎、RSS、开发者头条
• 上一个系列刚刚完成了 Go 设计模式，如果感兴趣也可以进行查看

什么是链表？

• 链表通过指针将零散的内存数据联系在一起
• 如下图所示，包含两个结构，一个是数据 data，另外一个是下一个节点的内存地址
• 最后一个节点指向 NULL

• 和单链表的区别就是，将尾节点指向的头结点，将整个链表组成了一个环状

• 和在单链表的基础之上添加了一个指向上一个节点的指针，这样我们知道任意一个节点就可以同时知道他们的上下两个节点
• 这是实际使用的时候最常用的

和数组对比

标准库 Container/list 的实现

结构体定义

// Element 用于表示链表当中的节点
type Element struct {
    // next, prev 分别表示上个节点和下个节点
	next, prev *Element

	// 表示节点所在的元素
	list *List

	// 节点所保存的数据，也就是上面图中的 data
	Value interface{}
}

// List 这是一个双向链表
// List 的零值是一个空链表
type List struct {
    // 根节点，List 其实是一个双向循环链表，root， root.prev 是尾节点, 尾节点的下一个节点指向 root
    // 根节点是一个哨兵节点，是为了用来简化节点操作使用的
	root Element

    // 链表的长度，不包括哨兵节点，也就是根节点
	len  int
}

看到这里我下意识的会有两个问题：

• 为什么在 Element 当中会持有一个 List 结构？
• 为什么需要一个单独的 List 结构体，直接要一个 Root 节点不就完事了么？

Remove(e *Element) interface{} // 删除一个节点
PushFront(v interface{}) *Element // 将值插入到链表头部
PushBack(v interface{}) *Element // 将值插入到链表尾部
InsertBefore(v interface{}, mark *Element) *Element // 在 mark 节点之前插入值
InsertAfter(v interface{}, mark *Element) *Element // 在 mark 节点之后插入值
MoveToFront(e *Element) // 将节点 e 移动至链表头部
MoveToBack(e *Element) // 将节点 e 移动至链表尾部
MoveBefore(e, mark *Element) // 将节点 e 移动到 mark 节点之前
MoveAfter(e, mark *Element) // 将节点 e 移动到 mark 节点之后
PushBackList(other *List) // 将链表 other 连接到当前链表之后
PushFrontList(other *List) // 将链表 other 连接到当前链表之前

看了暴露的方法集之后我们看一下这里面核心的几个方法，上诉暴露的方法实质上都是通过调用下面的方法实现的

insert

// 将节点 e 插入 at 之后
func (l *List) insert(e, at *Element) *Element {
    // 假设 at.next 为 nt
    // 1. 将节点 e 的上一个节点指向 at
	e.prev = at
    // 2. 将节点 e 的下一个节点指向 nt
	e.next = at.next
    // 3. 这个时候  e.prev.next == at.next
    // 其实就是本来 at --> nt，修改为 at --> e
	e.prev.next = e
    // 4. e.next.prev == nt.prev
    // 本来 at <--- nt，修改为 e <--- nt
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

remove

// remove removes e from its list, decrements l.len, and returns e.
func (l *List) remove(e *Element) *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--
	return e
}

// move moves e to next to at and returns e.
func (l *List) move(e, at *Element) *Element {
	if e == at {
		return e
	}
    // 先把当前节点从原来的位置移除
	e.prev.next = e.next
	e.next.prev = e.prev

    // 再将当前节点 e 插入到 at 节点之后
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e

	return e
}

我们在看一下最开始的两个问题
1. 为什么在 Element 当中会持有一个 List 结构？

• 查看上方的 move 方法我们就可以知道，list 提供了讲节点移动到某个节点之后的方法，通过 e.List 进行对比我们就可以知道需要移动的节点是不是属于当前这个链表了，这也是 MoveToFront 等方法的实现方式

func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}

2. 为什么需要一个单独的 List 结构体，直接要一个 Root 节点不就完事了么？

• 看之前的 List 的结构我们可以发现，在结构体中包含了一个 len ，这样可以避免需要取长度的时候每次都需要从头到尾遍历一遍

如何实现一个并发安全的 Container/list？

接下来，我们使用 go test -race . 测试是否存在并发安全的问题

func TestList(t *testing.T) {
	l := list.New()
	wg := sync.WaitGroup{}
	wg.Add(1)
	go func() {
		for i := 0; i < 10; i++ {
			l.PushBack(i)
		}
		wg.Done()
	}()
	l.PushBack(11)
	wg.Wait()
}

测试结果如下，可以明显的看到存在并发问题

 go test  -v -timeout 1s -race -run ^TestList$ ./...
=== RUN   TestList
==================
WARNING: DATA RACE
Read at 0x00c00006e330 by goroutine 8:
  container/list.(*List).lazyInit()
      /usr/local/go/src/container/list/list.go:86 +0xb2

// List 链表
type List struct {
	*list.List
	mu sync.Mutex
}

// New 新建链表
func New() *List {
	return &List{List: list.New()}
}

// PushBack 像链表尾部插入值
func (l *List) PushBack(v interface{}) {
    // 加锁
	l.mu.Lock()
	defer l.mu.Unlock()
	l.List.PushBack(v)
}

go test  -v -timeout 1s -race -run ^TestList_PushBack$ ./...
=== RUN   TestList_PushBack
--- PASS: TestList_PushBack (0.00s)
PASS
ok      github.com/mohuishou/go-algorithm/01_list/list  (cached)

如何实现一个 LRU 缓存？

LRU: Least Recently Used 最近最少使用策略

这里为了训练一下代码，就没有直接使用标准库的包了

package lru

import (
	"fmt"
)

// Node 链表的节点
type Node struct {
	prev, next *Node

	list *LRU

	key   string
	value interface{}
}

// LRU 缓存
type LRU struct {
	root *Node // 根节点
	cap  int   // 当前缓存容量
	len  int   // 缓存的长度
}

// NewLRU NewLRU
func NewLRU(cap int) *LRU {
	l := &LRU{
		root: &Node{},
		cap:  cap,
	}
	l.root.prev = l.root
	l.root.next = l.root
	l.root.list = l
	return l
}

// Get 获取缓存数据
// 如果获取到数据，就把这个节点移动到链表头部
// 如果没有获取到，就返回nil
func (l *LRU) Get(key string) interface{} {
	defer l.debug()
	n := l.get(key)
	if n == nil {
		return nil
	}

	return n.value
}

func (l *LRU) get(key string) *Node {
	for n := l.root.next; n != l.root; n = n.next {
		if n.key == key {
			n.prev.next = n.next
			n.next.prev = n.prev

			n.next = l.root.next
			l.root.next.prev = n
			l.root.next = n
			n.prev = l.root
			return n
		}
	}
	return nil
}

// Put 写入缓存数据
// 如果 key 已经存在，那么更新值
// 如果 key 不存在，那么插入到第一个节点
// 当缓存容量满了的时候，会自动删除最后的数据
func (l *LRU) Put(key string, value interface{}) {
	defer l.debug()
	n := l.get(key)
	if n != nil {
		n.value = value
		return
	}

	// 缓存满了
	if l.len == l.cap {
		last := l.root.prev
		last.prev.next = l.root
		l.root.prev = last.prev
		last.list = nil
		last.prev = nil
		last.next = nil
		l.len--
	}

	node := &Node{key: key, value: value}
	head := l.root.next
	head.prev = node
	node.next = head
	node.prev = l.root
	l.root.next = node
	l.len++
	node.list = l
}

// debug for debug
func (l *LRU) debug() {
	fmt.Println("lru len: ", l.len)
	fmt.Println("lru cap: ", l.cap)
	for n := l.root.next; n != l.root; n = n.next {
		fmt.Printf("%s:%v -> ", n.key, n.value)
	}
	fmt.Println()
	fmt.Println()
}

package lru

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestNewLRU(t *testing.T) {
	l := NewLRU(3)
	assert.Equal(t, l.Get(""), nil)

	l.Put("1", 1)
	l.Put("2", 2)
	l.Put("3", 3)
	assert.Equal(t, 3, l.Get("3"))
	assert.Equal(t, 1, l.Get("1"))

	l.Put("4", 4)
	assert.Equal(t, nil, l.Get("2"))

	l.Put("3", 31)
	assert.Equal(t, 31, l.Get("3"))
}

Question

• 前面讲到的 通过 Element 节点中的 List 结构来判断节点是否属于当前链表的方式，在某些情况下会出现 bug 你发现了么？
• LRU 缓存可以参考 leetcode 进行测试，146. LRU 缓存机制，文中的 LRU 缓存实现有许多值得优化的地方，你认为有哪些可以优化的地方？
• 问题可以回复在评论区，将在下一篇文章中解答