Go List

链表

• 列表是一种非连续的存储容器，由多个节点组成。
• 节点通过一些变量记录彼此之间的关系
• 列表存在多种实现方法，比如单链表、双链表等。

Go语言中列表使用container/list包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置元素的插入和删除操作。

container/list包中拥有两个数据结构类型分别是List和Element，List实现了一个双向链表，Element代表链表中元素的结构。

• List代表一个双向链表，List零值为一个空的、可用的链表。
• Element类型代表双向链表中的一个元素，相当于C++中的iterator。
• Element拥有Prev和Next方法用于获得前一个或后一个Element，Element可以直接调用Value属性。

链表特点

• 链表元素不是连续存储的，相邻元素之间需要相互保存对方的指针，所以链表所占用的内存空间，往往要比包含相同元素的数组所占的内存大得多。
• 每个元素存在它所属的那个链表的指针，在初始化时就拥有了头部元素（根元素），也记录了链表的长度以方便遍历和计算。

初始化

列表的初始化有两种方式，分别是使用list.New()函数和var关键字声明，二者效果一致。

• 使用var关键字声明并初始化列表

var l list.List

• 建议使用container/list包中的New()函数初始化列表

l := list.New()
fmt.Printf("%v", l)

&{{0xc000070360 0xc000070360 <nil> <nil>} 0}

列表与切片和映射map不同的是，列表并没有具体元素类型的限制，因此列表的元素可以是任意类型。

插入

List导出了六个方法用于添加元素

方法	描述
PushBack()	追加新元素到末尾并返回该元素的指针
PushBackList()	追加另一个列表到末尾
PushFront()	添加新元素到开头并返回该元素的指针
PushFrontList()	追加另一个列表到开头
InsertAfter()	在mark后插入新元素并返回新元素指针
InsertBefore()	在mark前插入新元素并返回新元素指针

例如：使用List列表实现简单的LRU缓存

LRU全称Least Recently Used即最近最少使用，LRU算法会根据数据的历史访问记录来淘汰数据。LRU的核心思想是如果数据最近被访问过，那么将来被访问的几率也更高。

LRU缓存实现是使用一个链表来保存数据，新数据插入到链表头部，每当缓存命中即缓存数量被访问时，则将数据一直链表头部，当链表满的时候将链表尾部的数据丢弃。

package main

import (
    "container/list"
    "encoding/json"
    "errors"
    "fmt"
    "sync"
)

//LruItem IRU中data保存的数据结构
type LruItem struct {
    Key   string
    Value interface{}
}

//Lru 最近最少使用
type Lru struct {
    capacity int        //最大存储数量
    counter  int        //当前存储数量
    data     *list.List //链表 [json(LruItem)]
    mutex    sync.Mutex //互斥锁
}

//NewLru 实例化LRU
func NewLru(capacity int) *Lru {
    return &Lru{capacity, 0, list.New(), sync.Mutex{}}
}

//判断键是否存在
func (l *Lru) exists(key string) (bool, *list.Element) {
    var lruItem LruItem
    for item := l.data.Front(); item != nil; item = item.Next() {
        json.Unmarshal(item.Value.([]byte), &lruItem)
        if lruItem.Key == key {
            return true, item
        }
    }
    return false, nil
}

//清除：链表已满则删除尾部元素后添加到头部
func (l *Lru) clear() interface{} {
    //添加互斥锁
    l.mutex.Lock()
    defer l.mutex.Unlock()
    //计数器累减
    l.counter--
    //删除链表尾部元素
    item := l.data.Remove(l.data.Back())
    return item
}

//添加
func (l *Lru) add(key string, value interface{}) error {
    //判断键是否存在
    if ok, _ := l.exists(key); ok {
        return errors.New("key exists")
    }
    //判断存储是否越界
    if l.counter >= l.capacity {
        l.clear() //链表已满则删除尾部元素后添加到头部
    }
    //添加互斥锁
    l.mutex.Lock()
    defer l.mutex.Unlock()
    //计数器累加
    l.counter++
    //JSON序列化
    arr, err := json.Marshal(LruItem{key, value})
    if err != nil {
        return errors.New("json marshal error")
    }
    //保存数据到链表头部
    l.data.PushFront(arr)
    return nil
}

//设置
func (l *Lru) set(key string, value interface{}) error {
    //判断元素是否存在
    ok, item := l.exists(key)
    if !ok {
        return l.add(key, value)
    }
    //添加互斥锁
    l.mutex.Lock()
    defer l.mutex.Unlock()
    //JSON序列化
    arr, err := json.Marshal(LruItem{key, value})
    if err != nil {
        return errors.New("lru set json marshal error")
    }
    //设置链表元素
    item.Value = arr
    return nil
}

//获取
func (l *Lru) get(key string) interface{} {
    //判断是否存在
    ok, item := l.exists(key)
    if !ok {
        return nil
    }
    //添加互斥锁
    l.mutex.Lock()
    defer l.mutex.Unlock()
    //数据被访问移动到链表头部
    l.data.MoveToFront(item)
    //JSON反序列化
    var data LruItem
    json.Unmarshal(item.Value.([]byte), &data)
    return data.Value
}

//删除
func (l *Lru) del(key string) error {
    //判断键是否存在
    ok, item := l.exists(key)
    if !ok {
        return errors.New("lru delete key not exists")
    }
    //添加互斥锁
    l.mutex.Lock()
    defer l.mutex.Unlock()
    //删除链表元素
    l.data.Remove(item)
    return nil
}

//长度
func (l *Lru) len() int {
    return l.counter
}

//打印
func (l *Lru) print() {
    var lruItem LruItem
    for item := l.data.Front(); item != nil; item = item.Next() {
        json.Unmarshal(item.Value.([]byte), &lruItem)
        fmt.Println(lruItem.Key, ":", lruItem.Value)
    }
}

func main() {
    lru := NewLru(3)
    lru.add("id", 1)
    lru.add("name", "admin")
    lru.add("status", 0)
    lru.add("remark", "this is a test")
    lru.add("pid", 100)
    lru.print()
}

pid : 100
remark : this is a test
status : 0

移除

func (l *List) Remove(e *Element) interface{}

链表的Remove()函数将指定的元素从链表中移除，同时会返回该元素的值。

双向链表支持对队列前后或后方插入元素，分别对应的方法是PushFront()和PushBack()。这两个方法都会返回一个*list.Element结构，若在后续需删除插入的元素可直接使用*list.Element作为list.Remove()的参数来实现，这种删除的方式更加高效，同时也是双链表特性之一。

移动

移动函数	描述
MoveToFront()	将指定元素移动到链表头部，若指定的元素在链表中不存在则不做修改。
MoveToBack()	将指定元素移动到链表尾部，若指定元素在链表中不存在则不做处理。
MoveBefore()	将指定元素移动到某个元素之前
MoveAfter()	将指定元素移动到某个元素之后

// 将给定元素移动到另一个元素的前面
func (l *List) MoveBefore(e, mark *Element)

// 将给定元素移动到另一个元素的后面
func (l *List) MoveAfter(e, mark *Element)

// 将给定元素移动到最前面
func (l *List) MoveToFront(e *Element)

// 将给定元素移动到最后面
func (l *List) MoveToBack(e *Element)

遍历

遍历双链表需配合Front()函数来获取头部元素，遍历时只要元素不为空即可继续，每次遍历都需要调用元素的Next()函数。