詳解Go語言中單鏈表的使用

Posted on by

鏈表

一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。使用鏈表結構可以避免在使用數組時需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去瞭數組隨機讀取的優點，同時鏈表由於增加瞭結點的指針域，空間開銷比較大。

單鏈表結構

利用 struct 可以包容多種數據類型，結構體內也可以包含多個成員，這些成員可以是基本類型、自定義類型、數組類型，也可以是指針類型。這裡可以使用指針類型成員來存放下一個結點的地址。如以下定義，成員 data 用來存放結點中的數據(整數類型)，next 是指針類型的成員，它指向 ListNode struct 類型數據，也就是下一個結點的數據類型。

type ListNode struct {
    data int
    next *ListNode
}

創建節點

節點聲明和賦值有以下幾種格式：

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func main() {
 
    var head *ListNode
    head = new(ListNode)
    head.data = 1
 
    var node1 = new(ListNode)
    node1.data = 2
 
    var node2 = &ListNode{3, nil}
 
    var node3 = &ListNode{data: 4}
 
    fmt.Println(*head)
    fmt.Println(*node1)
    fmt.Println(*node2)
    fmt.Println(*node3)
 
}
 
/* 輸出：
{1 <nil>}
{2 <nil>}
{3 <nil>}
{4 <nil>}
*/

遍歷鏈表

一個for循環即可，結構描述的鏈表沒有空鏈表的，不論data是何種類型，一旦聲明即使不馬上賦值也會有類型默認值，比如new(ListNode)即賦值瞭ListNode{0, nil}。

func showNode(p *ListNode) {
    fmt.Print(*p)
    for p.next != nil {
        p = p.next
        fmt.Print("->", *p)
    }
    fmt.Println()
}

頭插法

新結點放在鏈表的最前面

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func showNode(p *ListNode) {
    fmt.Print(*p)
    for p.next != nil {
        p = p.next
        fmt.Print("->", *p)
    }
    fmt.Println()
}
 
func main() {
    var head = &ListNode{0, nil}
 
    for i := 1; i < 5; i++ {
        var node = ListNode{data: i}
        node.next = head
        head = &node
    }
 
    showNode(head)
 
}
 
/* 輸出：
{4 0xc000084250}->{3 0xc000084240}->{2 0xc000084230}->{1 0xc000084220}->{0 <nil>}
*/

尾插法

新結點追加到鏈表的最後面

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func showNode(p *ListNode) {
    fmt.Print(*p)
    for p.next != nil {
        p = p.next
        fmt.Print("->", *p)
    }
    fmt.Println()
}
 
func main() {
 
    var head, tail *ListNode
    head = &ListNode{0, nil}
    tail = head
    for i := 1; i < 5; i++ {
        var node = ListNode{data: i}
        (*tail).next = &node
        tail = &node
    }
 
    showNode(head)
 
}
 
/* 輸出：
{0 0xc000084220}->{1 0xc000084230}->{2 0xc000084240}->{3 0xc000084250}->{4 <nil>}
*/

遍歷方法

方法的定義：參數表放在函數名前

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func (p *ListNode) travel() {
    fmt.Print(p.data)
    for p.next != nil {
        p = p.next
        fmt.Print("->", p.data)
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    var head = &ListNode{0, nil}
    head.travel()
 
    for i := 1; i < 10; i++ {
        var node = ListNode{data: i}
        node.next = head
        head = &node
    }
 
    head.travel()
 
    var root *ListNode
    root = new(ListNode)
    root.travel()
 
}
 
/* 輸出：
0<nil>
9->8->7->6->5->4->3->2->1->0<nil>
0<nil>
*/

鏈表長度

註意：函數與方法的區別

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func (head *ListNode) size() int {
    size := 1
    for head = head.next; head != nil; size++ {
        head = head.next
    }
    return size
}
 
func Len(head *ListNode) int {
    size := 1
    for head = head.next; head != nil; size++ {
        head = head.next
    }
    return size
}
 
func main() {
 
    var head = &ListNode{0, nil}
    fmt.Println(Len(head))
    fmt.Println(head.size())
 
    for i := 1; i < 10; i++ {
        var node = ListNode{data: i}
        node.next = head
        head = &node
    }
 
    fmt.Println(Len(head))
    fmt.Println(head.size())
 
}
 
/* 輸出：
1
1
10
10
*/

鏈表轉數組

package main
 
import (
    "fmt"
)
 
type ListNode struct {
    data int
    next *ListNode
}
 
func (head *ListNode) size() int {
    size := 1
    for head = head.next; head != nil; size++ {
        head = head.next
    }
    return size
}
 
func (head *ListNode) tolist() []int {
    var res []int
    res = make([]int, 0, head.size())
    for head.next != nil {
        res = append(res, head.data)
        head = head.next
    }
    res = append(res, head.data)
    return res
}
 
func (head *ListNode) tolist2() []int {
    var res []int
    res = make([]int, 0, head.size())
    res = append(res, head.data)
    head = head.next
    for head != nil {
        res = append(res, head.data)
        head = head.next
    }
    return res
}
 
func main() {
 
    var head = &ListNode{0, nil}
 
    for i := 1; i < 10; i++ {
        var node = ListNode{data: i}
        node.next = head
        head = &node
    }
 
    fmt.Println(head.tolist())
 
    var root, tail *ListNode
    root = &ListNode{0, nil}
    tail = root
    for i := 1; i < 10; i++ {
        var node = ListNode{data: i}
        (*tail).next = &node
        tail = &node
    }
 
    fmt.Println(root.tolist2())
 
}
 
/* 輸出：
[9 8 7 6 5 4 3 2 1 0]
[0 1 2 3 4 5 6 7 8 9]
*/

數組轉鏈表

package main
 
import "fmt"
 
type ListNode struct {
    data int
    next *ListNode
}
 
func (p *ListNode) travel() {
    fmt.Print(p.data)
    for p.next != nil {
        p = p.next
        fmt.Print("->", p.data)
    }
    fmt.Println("<nil>")
}
 
func toNode(list []int) *ListNode {
    var head, tail *ListNode
    head = &ListNode{list[0], nil}
    tail = head
    for i := 1; i < len(list); i++ {
        var node = ListNode{data: list[i]}
        (*tail).next = &node
        tail = &node
    }
    return head
}
 
func main() {
 
    var lst = []int{1, 3, 2, 3, 5, 6, 6, 8, 9}
    toNode(lst).travel()
 
}
 
/* 輸出：
1->3->2->3->5->6->6->8->9<nil>
*/

到此這篇關於詳解Go語言中單鏈表的使用的文章就介紹到這瞭,更多相關Go語言單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：