双向链表

双向链表实现

双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码

package algorithm

import (
    "fmt"
    "sync"
)

// 节点数据
type DoubleObject interface{}

// 双链表节点
type DoubleNode struct {
    Data DoubleObject
    Prev *DoubleNode
    Next *DoubleNode
}

// 双链表
type DoubleList struct{
    mutex *sync.RWMutex
    Size uint
    Head *DoubleNode
    Tail *DoubleNode
}

func (list *DoubleList)Init()  {
    list.mutex = new(sync.RWMutex)
    list.Size = 0
    list.Head = nil
    list.Tail = nil
}
// Get 获取指定位置的节点
func (list *DoubleList)Get(index uint) *DoubleNode {
    if list.Size == 0 || index > list.Size - 1 {
        return nil
    }
    if index == 0{
        return list.Head
    }
    if index == list.Size - 1{
        return list.Tail
    }
    node := list.Head
    var i uint
    for i = 1; i <= index; i ++{
        node = node.Next
    }
    return node
}
// Append 向双链表后面追加节点
func (list *DoubleList)Append(node *DoubleNode) bool {
    if node == nil{
        return false
    }
    list.mutex.Lock()
    defer list.mutex.Unlock()
    if list.Size == 0 {
        list.Head = node
        list.Tail = node
        node.Next = nil
        node.Prev = nil
    } else {
        node.Prev = list.Tail
        node.Next = nil
        list.Tail.Next = node
        list.Tail = node
    }
    list.Size++
    return true
}

// Insert 向双链表指定位置插入节点
func (list *DoubleList)Insert(index uint, node *DoubleNode) bool {
    if index > list.Size || node == nil{
        return false
    }

    if index == list.Size{
        return list.Append(node)
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()
    if index == 0{
        node.Next = list.Head
        list.Head = node
        list.Head.Prev = nil
        list.Size++
        return true
    }

    nextNode := list.Get(index)
    node.Prev = nextNode.Prev
    node.Next = nextNode
    nextNode.Prev.Next = node
    nextNode.Prev = node
    list.Size++
    return true
}

// Delete 删除指定位置的节点
func (list *DoubleList) Delete (index uint) bool {
    if index + 1 > list.Size {
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()
    if index == 0 {
        if list.Size == 1{
            list.Head = nil
            list.Tail = nil
        } else {
            list.Head.Next.Prev = nil
            list.Head = list.Head.Next
        }
        list.Size--
        return true
    }
    if index + 1 == list.Size{
        list.Tail.Prev.Next = nil
        list.Tail = list.Tail.Prev
        list.Size--
        return true
    }

    node := list.Get(index)
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
    list.Size--
    return true
}

// Display 打印双链表信息
func (list *DoubleList)Display(){
    if list == nil || list.Size == 0 {
        fmt.Println("this double list is nil or empty")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this double list size is %d \n", list.Size)
    ptr := list.Head
    for ptr != nil {
        fmt.Printf("data is %v\n", ptr.Data)
        ptr = ptr.Next
    }
}

// Reverse 倒序打印双链表信息
func (list *DoubleList)Reverse(){
    if list == nil || list.Size == 0 {
        fmt.Println("this double list is nil or empty")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this double list size is %d \n", list.Size)
    ptr := list.Tail
    for ptr != nil {
        fmt.Printf("data is %v\n", ptr.Data)
        ptr = ptr.Prev
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇