Go語言數(shù)據(jù)結構之單鏈表的實例詳解

更新時間：2022年08月26日 09:12:25 作者：Hann Yang

鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態(tài)生成。本文將通過五個例題帶大家深入了解Go語言中單鏈表的用法，感興趣的可以了解一下

任意類型的數(shù)據(jù)域

之前的鏈表定義數(shù)據(jù)域都是整型int，如果需要不同類型的數(shù)據(jù)就要用到 interface{}。

空接口 interface{}

對于描述起不到任何的作用(因為它不包含任何的method），但interface{}在需要存儲任意類型的數(shù)值的時候相當有用，因為它可以存儲任意類型的數(shù)值。

一個函數(shù)把interface{}作為參數(shù)，那么它可以接受任意類型的值作為參數(shù)；如果一個函數(shù)返回interface{}，那么也就可以返回任意類型的值，類似于C語言的void*類型。

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    node := new(List)
    node.push("abc")
    node.push(3.142)
    node.push('a')
    node.push(3 + 4i)
    node.push([]int{1, 2, 3})
    node.push([8]byte{'a', 3: 'd'})
    node.push(Node{1, &Node{2, nil}}.data)
    node.push(Node{1, &Node{2, nil}}.next)
    node.travel()
 
}
 
/*輸出：
abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 <nil>}<nil>
*/

實例01

把字串中漢字除外的所有字符逐個存入鏈表，且數(shù)字以整型保存。

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    node := new(List)
    str := "Golang數(shù)據(jù)結構123:單鏈表0789"
 
    for _, s := range str {
        if s >= 48 && s < 58 {
            node.push(s - 48)
        } else if s < 128 {
            node.push(string(s))
        }
    }
    node.travel()
 
}
 
/*輸出：
G->o->l->a->n->g->1->2->3->:->0->7->8->9<nil>
*/

快慢指針

給單鏈表設置2個指針，其中一個指針先移動n個節(jié)點，然后同時移動這2個指針，那么當先移動的指針到達尾部時，后移動的那個指針就是倒數(shù)第 n 個節(jié)點。先移動的指針稱“快指針”，后出發(fā)的指針稱“慢指針”，其實一樣“快”只是出發(fā)有先后。

實例02

刪除鏈表中倒數(shù)第 n 個結點

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func (list *List) removNthBack(n int) {
    if n > list.size() {
        panic("range error: n <= List's size")
    }
    var fast, slow *Node
    head := list.head
    fast = head
    slow = head
    for i := 0; i < n; i++ {
        fast = fast.next
    }
    if fast == nil {
        list.head = head.next
        return
    }
    for fast.next != nil {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
}
 
func removNthBack(list *List, n int) *List {
    if n > list.size() {
        panic("range error: n <= List's size")
    }
    var fast, slow *Node
    head := list.head
    fast = head
    slow = head
    for i := 0; i < n; i++ {
        fast = fast.next
    }
    if fast == nil {
        list.head = head.next
        return list
    }
    for fast.next != nil {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return list
}
 
func (list *List) push(value interface{}) {
    node := &Node{data: value}
    p := list.head
    if p != nil {
        for p.next != nil {
            p = p.next
        }
        p.next = node
    } else {
        list.head = node
    }
}
 
func (list *List) size() int {
    length := 0
    for p := list.head; p != nil; p = p.next {
        length++
    }
    return length
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    lst := new(List)
    str := "12309"
 
    for _, s := range str {
        lst.push(s - 48)
    }
    lst.travel()
 
    lst.removNthBack(3)
    lst.travel()
    lst = removNthBack(lst, 3)
    lst.travel()
    lst.removNthBack(2)
    lst.travel()
    //lst.removNthBack(10) //panic error
    lst.removNthBack(2)
    lst.travel()
    lst.removNthBack(1)
    lst.travel()
    //lst.removNthBack(1) //panic error
 
}
 
/*輸出：
1->2->3->0->9<nil>
1->2->0->9<nil>
1->0->9<nil>
1->9<nil>
9<nil>
<nil>
*/

反轉鏈表

遍歷一個鏈表，每個結點用頭插法相接的新鏈表就是原鏈表的反轉結果。

實例03

反轉整個鏈表

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func (list *List) reverse() {
    res := &List{}
    for p := list.head; p != nil; p = p.next {
        node := &Node{p.data, nil}
        node.next = res.head
        res.head = node
    }
    list.head = res.head
}
 
func (list *List) pushHead(value interface{}) {
    node := &Node{data: value}
    node.next = list.head
    list.head = node
}
 
func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}
 
func (list *List) clear() {
    list.head = nil
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    lst := new(List)
 
    for n := 5; n > 0; n-- {
        lst.pushHead(n)
    }
    lst.travel()
    lst.reverse()
    lst.travel()
 
    lst.clear()
    lst.build([]interface{}{6.13, "/", 100000, "Hann", 1.0e-5})
    lst.travel()
    lst.reverse()
    lst.travel()
 
}
 
/*輸出：
1->2->3->4->5<nil>
5->4->3->2->1<nil>
6.13->/->100000->Hann->1e-05<nil>
1e-05->Hann->100000->/->6.13<nil>
*/

實例04

反轉鏈表的其中一段，反轉從第m個結點到n個結點(其中0<m<=n<=length of List)

Input: 1->2->3->4->5->nil, m = 2, n = 4
Output: 1->4->3->2->5->nil

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func reverseBetween(list *List, m int, n int) *List {
    list = list.Copy()
    head := list.head
    if head == nil || m >= n {
        return list
    }
    if m < 1 { //防止范圍左端超限
        m = 1
    }
    node := &Node{0, head}
    p := node
    for i := 0; p.next != nil && i < m-1; i++ {
        p = p.next
    }
    if p.next == nil {
        return list
    }
    cur := p.next
    for i := 0; i < n-m && cur.next != nil; i++ {
        //由cur.next != nil防止范圍右端超限
        tmp := p.next
        p.next = cur.next
        cur.next = cur.next.next
        p.next.next = tmp
    }
    list.head = node.next
    return list
}
 
func (list *List) reverseBetween(m int, n int) {
    head := list.head
    if head == nil || m >= n {
        return
    }
    if m < 1 { //防止范圍左端超限
        m = 1
    }
    node := &Node{0, head}
    p := node
    for i := 0; p.next != nil && i < m-1; i++ {
        p = p.next
    }
    if p.next == nil {
        return
    }
    cur := p.next
    for i := 0; i < n-m && cur.next != nil; i++ {
        //由cur.next != nil防止范圍右端超限
        tmp := p.next
        p.next = cur.next
        cur.next = cur.next.next
        p.next.next = tmp
    }
    list.head = node.next
}
 
func (list *List) pushHead(value interface{}) {
    node := &Node{data: value}
    node.next = list.head
    list.head = node
}
 
func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}
 
func (list *List) Copy() *List {
    p := list.head
    res := &List{}
    if p != nil {
        node := &Node{p.data, nil}
        q := node
        for p = p.next; p != nil; p = p.next {
            q.next = &Node{p.data, nil}
            q = q.next
        }
        res.head = node
    }
    return res
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    list1 := new(List)
    list2 := new(List)
    for n := 5; n > 0; n-- {
        list1.pushHead(n)
    }
    list1.travel()
 
    list2 = reverseBetween(list1, 2, 4)
    list2.travel()
    list2 = reverseBetween(list1, 2, 3)
    list2.travel()
    list2 = reverseBetween(list1, 2, 5)
    list2.travel()
    list2 = reverseBetween(list1, 2, 6)
    list2.travel()
    list2 = reverseBetween(list1, 1, 6)
    list2.travel()
    list2 = reverseBetween(list1, 0, 3)
    list2.travel()
    list1.reverseBetween(1, 3)
    list1.travel()
 
}
 
/*輸出：
1->2->3->4->5<nil>
1->4->3->2->5<nil>
1->3->2->4->5<nil>
1->5->4->3->2<nil>
1->5->4->3->2<nil>
5->4->3->2->1<nil>
3->2->1->4->5<nil>
3->2->1->4->5<nil>
*/

交換節(jié)點

實例05

鏈表的相鄰節(jié)點兩兩交換位置

Given 1->2->3->4, you should return the list as 2->1->4->3.

package main
 
import "fmt"
 
type Node struct {
    data interface{}
    next *Node
}
 
type List struct {
    head *Node
}
 
func (list *List) swapPairs() {
    p := list.head
    if p == nil || p.next == nil {
        return
    }
    head := p.next
    var node, node2 *Node
    for p.next != nil {
        cur := p.next
        if node != nil && node.next != nil {
            node.next = cur
        }
        if p.next.next != nil {
            node2 = p.next.next
        }
        if p.next.next != nil {
            p.next = node2
        } else {
            p.next = nil
        }
        cur.next = p
        node = p
        if p.next != nil {
            p = node2
        }
    }
    list.head = head
}
 
func swapPairs(list *List) *List {
    list = list.Copy()
    p := list.head
    if p == nil || p.next == nil {
        return list
    }
    head := p.next
    var node, node2 *Node
    for p.next != nil {
        cur := p.next
        if node != nil && node.next != nil {
            node.next = cur
        }
        if p.next.next != nil {
            node2 = p.next.next
        }
        if p.next.next != nil {
            p.next = node2
        } else {
            p.next = nil
        }
        cur.next = p
        node = p
        if p.next != nil {
            p = node2
        }
    }
    list.head = head
    return list
}
 
func (list *List) Copy() *List {
    p := list.head
    res := &List{}
    if p != nil {
        node := &Node{p.data, nil}
        q := node
        for p = p.next; p != nil; p = p.next {
            q.next = &Node{p.data, nil}
            q = q.next
        }
        res.head = node
    }
    return res
}
 
func (list *List) build(lst []interface{}) {
    for i := len(lst) - 1; i >= 0; i-- {
        node := &Node{data: lst[i]}
        node.next = list.head
        list.head = node
    }
}
 
func (list *List) travel() {
    p := list.head
    for p != nil {
        fmt.Print(p.data)
        p = p.next
        if p != nil {
            fmt.Print("->")
        }
    }
    fmt.Println("<nil>")
}
 
func main() {
 
    list1 := new(List)
    list2 := new(List)
    list1.build([]interface{}{1, 2, 3, 4, 5, 6})
    list1.travel()
 
    list2 = swapPairs(list1)
    list2.travel()
 
    list2 = &List{&Node{0, nil}}
    list2.head.next = list1.Copy().head
    list2.travel()
    list2.swapPairs()
    list2.travel()
 
}
 
/*輸出：
1->2->3->4->5->6<nil>
2->1->4->3->6->5<nil>
0->1->2->3->4->5->6<nil>
1->0->3->2->5->4->6<nil>
*/

以上就是Go語言數(shù)據(jù)結構之單鏈表的實例詳解的詳細內容，更多關于Go語言單鏈表的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

golang監(jiān)聽ip數(shù)據(jù)包的實現(xiàn)步驟(golang純享版)
這篇文章主要給大家介紹了golang監(jiān)聽ip數(shù)據(jù)包的實現(xiàn)步驟,本文以ip4 作為案例進行包抓取示范,ip6抓取與ip4方式異曲同工,可自行舉一反三得出,文中通過圖文結合給大家介紹的非常詳細,需要的朋友可以參考下
2024-02-02
在go中使用omitempty的代碼實例
今天小編就為大家分享一篇關于在go中使用omitempty的代碼實例，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2019-04-04
go同步原語Phaser和Barrier區(qū)別
這篇文章主要為大家介紹了通過java講解go同步原語Phaser和Barrier區(qū)別,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
2023-12-12
Golang之casbin權限管理的實現(xiàn)
這篇文章主要介紹了Golang之casbin權限管理的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-10-10
Go語言題解LeetCode724尋找數(shù)組的中心下標
這篇文章主要為大家介紹了Go語言題解LeetCode724尋找數(shù)組的中心下標，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-12-12
Go 類型轉化工具庫cast函數(shù)詳解
這篇文章主要介紹了Go 類型轉化工具庫cast函數(shù)詳解，cast 是在Github上開源的工具庫，就像他的名字一樣，他為我們提供了非常便捷的類型轉化的方法
2022-07-07
go語言的工作空間和GOPATH環(huán)境變量介紹
這篇文章主要介紹了go語言的工作空間和GOPATH環(huán)境變量介紹，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-12-12
go語言?nil使用避坑指南
這篇文章主要為大家介紹了go語言?nil使用避坑指南詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-09-09
基于Go+WebSocket實現(xiàn)實時通信功能
在互聯(lián)網應用程序中,實時通信是一種非常重要的功能,WebSocket 是一種基于 TCP 的協(xié)議,它允許客戶端和服務器之間進行雙向通信,本文將介紹如何使用 Golang 創(chuàng)建單獨的 WebSocket 會話,以實現(xiàn)實時通信功能,需要的朋友可以參考下
2023-10-10
GO語言gin框架實現(xiàn)管理員認證登陸接口
這篇文章主要介紹了GO語言gin框架實現(xiàn)管理員認證登陸接口,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-10-10