博客 / 詳情

返回

go 鏈表總結

什麼是鏈表

  鏈表是一種數據結構，鏈表作為一種基礎的數據結構可以用來生成其它類型的數據結構。

  鏈表通常由一連串節點組成，節點可以在運行時動態生成，每個節點包含任意的實例數據（data fields）和存儲下一個或下一個結點地址的指針域

  鏈表是有序的列表，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的

  使用鏈表結構可以避免在使用數組時需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大

  常用的鏈表方式有三種:
  1. 單鏈表
  2. 雙向鏈表
  3. 循環鏈表

鏈表的基礎概念

鏈表包含頭節點(必須)、頭指針、首元節點、其他節點

  • 首元結點：就是鏈表中存儲第一個元素的結點，如下圖中 a1 的位置。
  • 頭結點：它是在首元結點之前附設的一個結點，其指針域指向首元結點。頭結點的數據域可以存儲鏈表的長度或者其它的信息，也可以為空不存儲任何信息。
  • 頭指針：它是指向鏈表中第一個結點的指針。若鏈表中有頭結點，則頭指針指向頭結點；若鏈表中沒有頭結點，則頭指針指向首元結點。

頭結點在鏈表中不是必須的，但增加頭結點有以下幾點好處:

  • 增加了頭結點後，首元結點的地址保存在頭結點的指針域中，對鏈表的第一個數據元素的操作與其他數據元素相同，無需進行特殊處理。
  • 增加頭結點後，無論鏈表是否為空，頭指針都是指向頭結點的非空指針，若鏈表為空的話，那麼頭結點的指針域為空

image.png

單向鏈表

單鏈表的形式如下圖所示
image.png

實現一個單鏈表

package main

import (
    "fmt"
)

//定義一個 HeroNode
type HeroNode struct {
    no int
    name  string
    nickname string
    next  *HeroNode //這個表示指向下一個結點
}

//給鏈表插入一個結點
//編寫第一種插入方法，在單鏈表的最後加入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
    //1. 先找到該鏈表的最後這個結點
    //2. 創建一個輔助結點
    temp := head
    for {
        if temp.next == nil { //表示找到最後
            break
        }
        temp = temp.next //  讓 temp 不斷的指向下一個結點
    }

    //3. 將 newHeroNode 加入到鏈表的最後
    temp.next = newHeroNode
}

//給鏈表插入一個結點
//編寫第 2 種插入方法，根據 no  的編號從小到大插入..【實用】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
    //1. 找到適當的結點
    //2. 創建一個輔助結點[跑龍套, 幫忙]
    temp := head
    flag := true
    //讓插入的結點的 no，和 temp 的下一個結點的 no 比較
    for {

        if temp.next == nil {
            //説明到鏈表的最後
            break
        } else if temp.next.no >= newHeroNode.no {
            //説明 newHeroNode 就應該插入到 temp 後面
            break
        } else if temp.next.no == newHeroNode.no {
            //説明我們額鏈表中已經有這個 no,就不然插入. flag = false
            break
        }
        temp = temp.next
    }

    if !flag {
        fmt.Println("對不起，已經存在 no=", newHeroNode.no)
        return
    } else {
        newHeroNode.next = temp.next
        temp.next = newHeroNode
    }
}

//刪除一個結點
func DelHerNode(head *HeroNode,id int){
    temp:=head
    flag:=false
    //找到要刪除節點的no,和temp的下一個結點no比較
    for {
        if temp.next == nil {
            //説明到了鏈表的最後
            break
        }else if temp.next.no == id {
            //找到了要刪除的節點
            flag = true
            break
        }
        temp = temp.next
    }
    if flag{
        temp.next = temp.next.next
    }else {
        fmt.Println("id 不存在")
    }
}

//顯示鏈表的所有結點信息
func ListHeroNode(head *HeroNode) {
    //1. 創建一個輔助結點
    temp := head

    // 先判斷該鏈表是不是一個空的鏈表
    if temp.next == nil {
        fmt.Println("空空如也。。。。")
        return
    }
    //2. 遍歷這個鏈表
    for {
        fmt.Printf("[%d , %s , %s]==>", temp.next.no, temp.next.name, temp.next.nickname)
        //判斷是否鏈表後
        temp = temp.next
        if temp.next == nil {
            break
        }
    }
}

func main() {
    //1. 先創建一個頭結點
    head := &HeroNode{}
    hero1 := &HeroNode{
        no : 1,
        name : "張三",
        nickname : "法外狂徒",
    }
    hero2 := &HeroNode{
        no : 2,
        name : "王五",
        nickname : "隔壁老王",
    }
    hero3 := &HeroNode{
        no : 3,
        name : "李四",
        nickname : "好人老四",
    }
    //3. 加入後展示
    InsertHeroNode2(head, hero3)
    InsertHeroNode2(head, hero1)
    InsertHeroNode2(head, hero2)
    ListHeroNode(head)
    fmt.Println()

    // 4.刪除一個節點
    DelHerNode(head,2)
    ListHeroNode(head)
}

執行輸出結果

>go run main.go
[1 , 張三 , 法外狂徒]==>[2 , 王五 , 隔壁老王]==>[3 , 李四 , 好人老四]==>
[1 , 張三 , 法外狂徒]==>[3 , 李四 , 好人老四]==>

雙向鏈表

雙向鏈表的形式如下圖所示
image.png

實現一個雙向鏈表

package main

import (
    "fmt"
)

//定義一個 HeroNode
type HeroNode struct {
    no int
    name  string
    nickname string
    pre   *HeroNode //這個表示指向上一個結點
    next  *HeroNode //這個表示指向下一個結點
}

//給雙向鏈表插入一個結點
//編寫第一種插入方法，最後加入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
    //1. 先找到該鏈表的最後這個結點
    //2. 創建一個輔助結點
    temp := head
    for {
        if temp.next == nil { //表示找到最後
            break
        }
        temp = temp.next //  讓 temp 不斷的指向下一個結點
    }

    //3. 將 newHeroNode 加入到鏈表的最後
    temp.next = newHeroNode
    newHeroNode.pre = temp
}

//給雙向鏈表插入一個結點
//編寫第 2 種插入方法，根據 no  的編號從小到大插入..【實用】
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
    //1. 找到適當的結點
    //2. 創建一個輔助結點[跑龍套, 幫忙]
    temp := head
    flag := true
    //讓插入的結點的 no，和 temp 的下一個結點的 no 比較
    for {
        if temp.next == nil {
            //説明到鏈表的最後
            break
        } else if temp.next.no >= newHeroNode.no {
            //説明 newHeroNode 就應該插入到 temp 後面
            break
        } else if temp.next.no == newHeroNode.no {
            //説明我們額鏈表中已經有這個 no,就不然插入.
            flag = false
            break
        }
        temp = temp.next
    }

    if !flag {
        fmt.Println("對不起，已經存在 no=", newHeroNode.no)
        return
    } else {
        newHeroNode.next = temp.next
        newHeroNode.pre = temp
        if temp.next != nil {
            temp.next.pre = newHeroNode
        }
        temp.next = newHeroNode
    }
}

//雙向鏈表種刪除一個結點
func DelHerNode(head *HeroNode,id int){
    temp:=head
    flag:=false
    //找到要刪除節點的no,和temp的下一個結點no比較
    for {
        if temp.next == nil {
            //説明到了鏈表的最後
            break
        }else if temp.next.no == id {
            //找到了要刪除的節點
            flag = true
            break
        }
        temp = temp.next
    }
    if flag{
        temp.next = temp.next.next
        if temp.next != nil {
            temp.next.pre = temp
        }
    }else {
        fmt.Println("id 不存在")
    }
}

//顯示鏈表的所有結點信息
func ListHeroNode(head *HeroNode) {
    //1. 創建一個輔助結點
    temp := head

    // 先判斷該鏈表是不是一個空的鏈表
    if temp.next == nil {
        fmt.Println("空空如也。。。。")
        return
    }
    //2. 遍歷這個鏈表
    for {
        fmt.Printf("[%d , %s , %s]==>", temp.next.no, temp.next.name, temp.next.nickname)
        //判斷是否鏈表後
        temp = temp.next
        if temp.next == nil {
            break
        }
    }
}

func ListHeroNode2(head *HeroNode) {
    //1. 創建一個輔助結點
    temp := head

    // 先判斷該鏈表是不是一個空的鏈表
    if temp.next == nil {
        fmt.Println("空空如也。。。。")
        return
    }
    //2. 讓temp定位到雙向鏈表的最後節點
    for  {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }

    //3.遍歷鏈表
    for {
        fmt.Printf("[%d , %s , %s]==>", temp.no, temp.name, temp.nickname)
        //判斷是否鏈表頭
        temp = temp.pre
        if temp.pre == nil {
            break
        }
    }
}

func main() {
    //1. 先創建一個頭結點
    head := &HeroNode{}
    hero1 := &HeroNode{
        no : 1,
        name : "張三",
        nickname : "法外狂徒",
    }
    hero2 := &HeroNode{
        no : 2,
        name : "王五",
        nickname : "隔壁老王",
    }
    hero3 := &HeroNode{
        no : 3,
        name : "李四",
        nickname : "好人老四",
    }
    //3. 加入後展示
    InsertHeroNode2(head, hero3)
    InsertHeroNode2(head, hero1)
    InsertHeroNode2(head, hero2)
    fmt.Println("\n正向打印鏈表")
    ListHeroNode(head)

    fmt.Println("\n逆向打印鏈表")
    ListHeroNode2(head)

    // 4.刪除一個節點
    DelHerNode(head,2)
    fmt.Println("\n刪除id 2後正向打印鏈表")
    ListHeroNode(head)
    fmt.Println("\n刪除id 2後逆向打印鏈表")
    ListHeroNode2(head)
}

執行的結果

>go run main.go

正向打印鏈表
[1 , 張三 , 法外狂徒]==>[2 , 王五 , 隔壁老王]==>[3 , 李四 , 好人老四]==>
逆向打印鏈表
[3 , 李四 , 好人老四]==>[2 , 王五 , 隔壁老王]==>[1 , 張三 , 法外狂徒]==>

刪除id 2後正向打印鏈表
[1 , 張三 , 法外狂徒]==>[3 , 李四 , 好人老四]==>
刪除id 2後逆向打印鏈表
[3 , 李四 , 好人老四]==>[1 , 張三 , 法外狂徒]==>
鏈表 , go
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.