1.1 链表-编程书籍在线阅读平台-duidaima 堆代码

1.1 链表

什么是链表？
单链表
1.链表通过指针将零散的内存数据联系在一起
2.如下图所示，包含两个结构，一个是数据 data，另外一个是下一个节点的内存地址
3.最后一个节点指向 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
}

看到这里我下意识的会有两个问题：
1.为什么在 Element 当中会持有一个 List 结构？
2.为什么需要一个单独的 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

// 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
1.前面讲到的通过 Element 节点中的 List 结构来判断节点是否属于当前链表的方式，在某些情况下会出现 bug 你发现了么？
2.LRU 缓存可以参考 leetcode 进行测试，146. LRU 缓存机制，文中的 LRU 缓存实现有许多值得优化的地方，你认为有哪些可以优化的地方？

留下你的读书笔记
你还没登录，点击这里
 用户笔记留言