轉(zhuǎn)載請注明出處：數(shù)據(jù)結(jié)構(gòu)——Golang實現(xiàn)單鏈表

Golang

1. 單鏈表

1.1. 定義

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始；鏈表是使用指針進行構(gòu)造的列表；又稱為結(jié)點列表，因為鏈表是由一個個結(jié)點組裝起來的；其中每個結(jié)點都有指針成員變量指向列表中的下一個結(jié)點；
列表是由結(jié)點構(gòu)成，head指針指向第一個成為表頭結(jié)點，而終止于最后一個指向nuLL的指針。

1.2. 優(yōu)點

1. 單個結(jié)點創(chuàng)建非常方便，普通的線性內(nèi)存通常在創(chuàng)建的時候就需要設(shè)定數(shù)據(jù)的大小
2. 結(jié)點的刪除非常方便，不需要像線性結(jié)構(gòu)那樣移動剩下的數(shù)據(jù)
3. 結(jié)點的訪問方便，可以通過循環(huán)或者遞歸的方法訪問到任意數(shù)據(jù)，但是平均的訪問效率低于線性表。

2. Golang 實現(xiàn)

2.1. 相關(guān)結(jié)構(gòu)體

首先需要先定義一下鏈表相關(guān)的結(jié)果，SingleObject用于每個節(jié)點的數(shù)據(jù)，為interface{}結(jié)構(gòu)，SingleNode為鏈表中的節(jié)點，SingleList單鏈表，為了多協(xié)程讀寫安全，所以在鏈表中加了讀寫鎖。
具體定義如下：

// 節(jié)點數(shù)據(jù)
type SingleObject interface{}

// 單鏈表節(jié)點
type SingleNode struct {
    Data SingleObject
    Next *SingleNode
}

// 單鏈表
type SingleList struct{
    mutex *sync.RWMutex
    Head *SingleNode
    Tail *SingleNode
    Size uint
}

2.2. 鏈表初始化

定義完結(jié)構(gòu)，接下來就需要對單鏈表進行初始化了。代碼如下：

// 初始化
func (list *SingleList) Init()  {
    list.Size = 0
    list.Head = nil
    list.Tail = nil
    list.mutex = new(sync.RWMutex)
}

2.3. 新增節(jié)點

鏈表節(jié)點的新增分為兩種，一種是在鏈表后面追加節(jié)點，該方式，我們稱為append；另外一種方式是在指定位置插入節(jié)點，我們叫做insert。
另外新增時，若為第一個節(jié)點需特殊處理一下。下面請看代碼：

// 添加節(jié)點到鏈表尾部
func (list *SingleList)Append(node *SingleNode) bool {
    if node == nil{
        return false
    }
    list.mutex.Lock()
    defer list.mutex.Unlock()
    if list.Size == 0{
        list.Head = node
        list.Tail = node
        list.Size = 1
        return true
    }

    tail := list.Tail
    tail.Next = node
    list.Tail = node
    list.Size += 1
    return true
}

// 插入節(jié)點到指定位置
func (list *SingleList)Insert(index uint, node *SingleNode) bool {
    if node == nil {
        return false
    }

    if index > list.Size{
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0{
        node.Next = list.Head
        list.Head = node
        list.Size += 1
        return true
    }
    var i uint
    ptr := list.Head
    for i = 1; i < index; i ++ {
        ptr = ptr.Next
    }
    next := ptr.Next
    ptr.Next = node
    node.Next = next
    list.Size += 1
    return true
}

2.4. 刪除節(jié)點

有了新增功能自然就少不了刪除，此外，刪除節(jié)點時，如果指定的位置是鏈表的頭部或尾部，都需要特殊處理下?？创a：

// 刪除指定位置的節(jié)點
func (list *SingleList)Delete(index uint) bool {
    if list == nil || list.Size == 0 || index > list.Size - 1 {
        return false
    }

    list.mutex.Lock()
    defer list.mutex.Unlock()

    if index == 0 {
        head := list.Head.Next
        list.Head = head
        if list.Size == 1{
            list.Tail = nil
        }
        list.Size -= 1
        return true
    }

    ptr := list.Head
    var i uint
    for i = 1; i < index; i++{
        ptr = ptr.Next
    }
    next := ptr.Next
    
    ptr.Next = next.Next
    if index == list.Size - 1 {
        list.Tail = ptr
    }
    list.Size -= 1
    return true
}

2.6. 查詢節(jié)點

根據(jù)指定的位置索引，查詢出節(jié)點內(nèi)容。

// 獲取指定位置的節(jié)點，不存在則返回nil
func (list *SingleList)Get(index uint) *SingleNode{
    if list == nil || list.Size == 0 || index > list.Size - 1 {
        return nil
    }

    list.mutex.RLock()
    defer list.mutex.RUnlock()
    
    if index == 0{
        return list.Head
    }
    node := list.Head
    var i uint
    for i = 0; i < index; i ++ {
        node = node.Next
    }
    return node
}

2.7. 打印鏈表

最后，我們增加一個打印鏈表的功能，方便我們看整個鏈表的內(nèi)容：

// 輸出鏈表
func (list *SingleList)Display(){
    if list == nil {
        fmt.Println("this single list is nil")
        return
    }
    list.mutex.RLock()
    defer list.mutex.RUnlock()
    fmt.Printf("this single list size is %d \n", list.Size)
    ptr := list.Head
    var i uint
    for i = 0; i < list.Size; i++{
        fmt.Printf("No%3d data is %v\n", i + 1, ptr.Data)
        ptr = ptr.Next
    }
}

3. 源碼

github源碼

完

轉(zhuǎn)載請注明出處: 數(shù)據(jù)結(jié)構(gòu)——Golang實現(xiàn)單鏈表