Golang 單向鏈結串列實作

Go實作單向鏈結串列練習。

環境：

• Go 1.18

實作

下面實作單向鏈結串列及基本的操作方法。未充分測試可能有錯。

list/list.go

package list

// 單向鏈結串列
type SinglyLinkedList struct {
    // 指向第一個節點
    first *Node
    // 紀錄目前串列節點數
    length int
}

// 建立新串列
func New() *SinglyLinkedList {
    return new(SinglyLinkedList)
}

// 取得節點數
func (l *SinglyLinkedList) Length() int {
    return l.length
}

// 清空節點
func (l *SinglyLinkedList) Clear() {
    l.first = nil
    l.length = 0
}

// 取得第一個節點
func (l *SinglyLinkedList) First() *Node {
    return l.first
}

// 取得最後一個節點
func (l *SinglyLinkedList) Last() *Node {
    for node := l.first; node != nil; node = node.Next() {
        if node.Next() == nil {
            return node
        }
    }
    return nil
}

// 取得索引i的節點
func (l *SinglyLinkedList) Get(i int) *Node {
    if i == l.length-1 {
        return l.Last()
    }

    if i < 0 || i >= l.length {
        panic("index out of range")
    }

    node := l.First()
    for j := 0; j < i; j++ {
        node = node.Next()
    }
    return node
}

// 在串列最前插入新的值
func (l *SinglyLinkedList) InsertFirst(v string) *Node {
    node := &Node{
        Value: v,
        node:  l.first,
    }

    l.first = node
    l.length++
    return node
}

// 在串列最後插入新的值
func (l *SinglyLinkedList) InsertLast(v string) *Node {
    node := &Node{
        Value: v,
    }

    l.Get(l.length - 1).node = node
    l.length++
    return node
}

// 在串列索引i的位置插入新的值
func (l *SinglyLinkedList) Insert(i int, v string) *Node {
    if i == 0 {
        return l.InsertFirst(v)
    }
    if i == l.length {
        return l.InsertLast(v)
    }

    next := l.Get(i)
    prev := l.Get(i - 1)
    node := &Node{
        Value: v,
        node:  next,
    }
    prev.node = node
    l.length++
    return node
}

// 刪除索引i的節點
func (l *SinglyLinkedList) Delete(i int) *Node {
    if i == 0 {
        deletedNode := l.first
        l.first = l.first.node
        deletedNode.node = nil
        l.length--
        return deletedNode
    }
    if i == l.length-1 {
        deletedNode := l.Last()
        l.Get(l.length - 2).node = nil
        l.length--
        return deletedNode
    }
    deletedNode := l.Get(i)
    next := deletedNode.node
    prev := l.Get(i - 1)
    prev.node = next
    deletedNode.node = nil
    l.length--
    return deletedNode
}

// 鏈結串列的節點
type Node struct {
    // 資料欄位，儲存資料
    Value string
    // 節點欄位，儲存下個節點的指標
    node *Node
}

// 取得下一個節點
func (n *Node) Next() *Node {
    return n.node
}

測試

在main.go調用list.go的函式及方法來測試。註解方括弧代表該行執行後串列的元素狀態。

main.go

package main

import (
    "fmt"

    "abc.com/demo/list"
)

func main() {
    l := list.New()    // []
    l.InsertFirst("b") // [b]
    l.InsertLast("c")  // [b,c]

    fmt.Println(l.First().Value) // b
    fmt.Println(l.Get(0).Value)  // b

    fmt.Println(l.Last().Value)              // c
    fmt.Println(l.Get(1).Value)              // c
    fmt.Println(l.Get(l.Length() - 1).Value) // c

    l.InsertFirst("a") // [a,b,c]

    e := l.First()
    fmt.Println(e.Value)               // a
    fmt.Println(e.Next().Value)        // b
    fmt.Println(e.Next().Next().Value) // c

    l.InsertLast("e")         // [a,b,c,e]
    l.Insert(3, "d")          // [a,b,c,d,e]
    l.Insert(l.Length(), "f") // [a,b,c,d,e,f]

    for node := l.First(); node != nil; node = node.Next() {
        fmt.Print(node.Value) // abcdef
    }

    fmt.Println()
    fmt.Println(l.Length()) // 6

    d := l.Delete(2)      // [a,b,d,e,f]
    fmt.Println(d.Value)  // c
    fmt.Println(e.Next()) // nil

    d = l.Delete(0)       // [b,d,e,f]
    fmt.Println(e.Value)  // a
    fmt.Println(e.Next()) // nil

    d = l.Delete(l.Length() - 1) // [b,d,e]
    fmt.Println(e.Value)         // f
    fmt.Println(e.Next())        // nil

    for node := l.First(); node != nil; node = node.Next() {
        fmt.Print(node.Value) // bde
    }

    fmt.Println()
    fmt.Println(l.Length()) // 3

    l.Clear()               // []
    fmt.Println(l.First())  // nil
    fmt.Println(l.Last())   // nil
    fmt.Println(l.Length()) // 0
}

執行main.go後印出以下結果。

b
b
c
c
c
a
b
c
abcdef
6
c
<nil>
a
<nil>
f
<nil>
bde
3
<nil>
<nil>
0

github。