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

Posted on 2022-08-21 by WalkonNet

鏈表

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

單鏈表結構

利用 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！

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

目錄

鏈表

單鏈表結構

創建節點

遍歷鏈表

頭插法

尾插法

遍歷方法

鏈表長度

鏈表轉數組

數組轉鏈表

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

鏈表

單鏈表結構

創建節點

遍歷鏈表

頭插法

尾插法

遍歷方法

鏈表長度

鏈表轉數組

數組轉鏈表

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆