双链

双向链表

双链的删除，查找，增加都优于单链表，灵活性也更高，为什么市面上用的大部分还是单链？是由于双链的每个节点都多了一个指向上一个节点的指针，在存储中一个指针在32位机上占4b，64位机占8b，就算这个原因，导致实际中单链才是比较合适的

package main
import (
    "fmt"
    "sync"
)
type Node struct {
    Pre  *Node
    Value int
    Next *Node
}
type List struct{
    Size uint
    RW *sync.RWMutex
    Head *Node    // 首节点
    Tail *Node    // 尾节点
}
//初始化
func NewList() *List{
    return &List{
        Size:0,
        RW:new(sync.RWMutex),
        Head:nil,
        Tail:nil,
    }
}
// 向尾部添加元素
func (this *List) Append(value int){
    node := &Node{Value:value}
    this.RW.RLock()
    defer this.RW.RUnlock()
    if this.Size == 0{ // 当前链表是空的
        node.Next,node.Pre = nil,nil
        this.Head,this.Tail = node,node //头尾都是node
    }else {
        node.Next,node.Pre = nil,this.Tail
        this.Tail.Next = node // 尾节点Next指向新增得节点
        this.Tail = node //更新list尾节点
    }
    this.Size++ // 长度增加
}
// 向头部添加元素
func (this *List) Add(value int){
    node := &Node{Value:value}
    this.RW.RLock()
    defer this.RW.RUnlock()
    if this.Size == 0{ // 当前链表是空的
        node.Next,node.Pre = nil,nil
        this.Head,this.Tail = node,node //头尾都是node
    }else {
        node.Next,node.Pre = this.Head,nil
        this.Head.Pre = node //头节点得pre指向新增得节点
        this.Head = node // 更新list头节点
    }
    this.Size++ // 长度增加
}
// 从左到右遍历插入
func (this *List) InsertForward(index,value int){
    this.RW.RLock()
    defer this.RW.RUnlock()
    current := this.Head  //index-1处得node
    for index > 1{
        current = current.Next
        index--
    }
    node := &Node{Value:value}
    //新node得pre指向index-1处得node
    //新node得next指向index处得node
    node.Pre,node.Next = current,current.Next
    //index处得node得pre更新为新增得node
    //index-1处得node得next更新为新增得node
    current.Next.Pre,current.Next = node,node
    this.Size++ // 长度增加
}
// 从右到左遍历插入
func (this *List) InsertBackwards(index,value int){
    this.RW.RLock()
    defer this.RW.RUnlock()
    _index := this.Size-uint(index) //逆向
    current := this.Tail  //index-1处得node
    for _index > 1{
        current = current.Pre
        _index--
    }
    node := &Node{Value:value}
    node.Pre,node.Next = current.Pre,current
    current.Pre,current.Pre.Next = node,node
    this.Size++ // 长度增加
}
//插入
func (this *List) Insert(index,value int){
    if index <= 0 {
        this.Add(value)
    }else if uint(index) >= this.Size-1{
        this.Append(value)
    }else {
        // 如果插入得index得值在中间得左端，则向前遍历进行插入
        if this.Size/2>uint(index){
            this.InsertForward(index,value)
        }else {
            this.InsertBackwards(index,value)
        }
    }
}
// 删除与查找 ---应同插入一致，需要考虑到是从头部还剩从尾部开始遍历
//遍历
func(this *List) ForEach(opt ...string){
    //从左到右
    if opt == nil{
        current := this.Head
        for {
            fmt.Println(current.Value)
            if current.Next == nil{
                break
            }
            current = current.Next
        }
    }else {
        current := this.Tail
        for {
            fmt.Println(current.Value)
            if current.Pre == nil{
                break
            }
            current = current.Pre
        }
    }
}
func main() {
    list := NewList()
    list.Append(1)
    list.Append(2)
    list.Add(0)
    list.Append(3)
    list.Insert(1,4)
    list.Insert(3,5)
    list.ForEach("")
}