pembalikan senarai pautan golang

Golang ialah salah satu bahasa pengaturcaraan yang paling popular pada masa ini. Kesederhanaan dan kecekapannya amat digemari oleh pembangun. Di Golang, senarai terpaut digunakan secara meluas dalam pelbagai struktur data. Walau bagaimanapun, pengendalian senarai terpaut agak rumit, dan perhatian khusus perlu diberikan kepada ketepatan operasi penunjuk. Dalam artikel ini, kita akan membincangkan cara membalikkan senarai terpaut menggunakan Golang.

Apakah itu senarai terpaut?

Dalam sains komputer, senarai terpaut ialah struktur data yang merupakan koleksi nod. Setiap nod mengandungi data dan penunjuk ke nod seterusnya. Cirinya ialah ia boleh memasukkan dan memadam nod dengan cekap, tetapi mengakses nod secara rawak memerlukan merentasi keseluruhan senarai terpaut.

Struktur data senarai terpaut adalah seperti berikut:

type Node struct {
    data int
    next *Node
}

di mana data ialah data yang disimpan dalam nod dan next ialah penuding ke nod seterusnya. Apabila next bersamaan dengan nil, ini bermakna ini adalah nod terakhir senarai terpaut.

Operasi lintasan dan sisipan senarai terpaut

Operasi asas melintasi senarai terpaut ialah melintasi dari nod kepala senarai terpaut ke nod ekor senarai terpaut. Semasa proses traversal, operasi tertentu boleh dilakukan pada setiap nod, seperti mengeluarkan nilai nod. Berikut ialah contoh merentasi senarai terpaut:

func printList(head *Node) {
    p := head
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
}

Untuk operasi sisipan, kita perlu mencari kedudukan yang hendak disisipkan dahulu, dan kemudian mengubah suai penunjuk penunjuk. Contohnya, untuk memasukkan nod baharu selepas nod ketiga dalam senarai terpaut, kodnya adalah seperti berikut:

func insert(head *Node, pos int, value int) *Node {
    p := head
    for i := 1; i < pos && p != nil; i++ {
        p = p.next
    }
    if p == nil {
        return head
    }
    newNode := &Node{data: value}
    newNode.next = p.next
    p.next = newNode
    return head
}

Pembalikan senarai terpaut

Menterbalikkan senarai terpaut bermakna membalikkan susunan daripada nod dalam senarai terpaut, iaitu, nod asal Nod pertama menjadi nod terakhir, dan nod terakhir asal menjadi nod pertama. Proses membalikkan senarai terpaut melibatkan membalikkan penunjuk antara nod dalam senarai terpaut. Berikut ialah kod pelaksanaan untuk menyongsangkan senarai terpaut:

func reverseList(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    var prev *Node
    curr := head
    for curr != nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

Mula-mula, kami menentukan sama ada senarai terpaut kosong atau hanya mempunyai satu nod, tidak perlu membalikkan dan senarai terpaut asal nod kepala dikembalikan secara langsung. Kemudian kami mentakrifkan dua penunjuk, prev menunjuk ke nod sebelumnya bagi nod semasa dan curr menunjuk ke nod semasa. Kami melintasi senarai terpaut bermula dari nod kepala, dan setiap gelung menghalakan next penuding nod semasa ke nod sebelumnya, dan kemudian menggerakkan penuding prev dan curr ke belakang dengan satu nod sehingga keseluruhan senarai terpaut dilalui. Akhirnya, nod kepala senarai terbalik dikembalikan.

Kod ujian adalah seperti berikut:

func main() {
    head := &Node{data: 1}
    head.next = &Node{data: 2}
    head.next.next = &Node{data: 3}
    head.next.next.next = &Node{data: 4}
    fmt.Println("Original list:")
    printList(head)
    head = reverseList(head)
    fmt.Println("
Reversed list:")
    printList(head)
}

Hasil output ialah:

Original list:
1 2 3 4
Reversed list:
4 3 2 1

Ringkasan

Artikel ini memperkenalkan operasi asas senarai terpaut di Golang dan cara untuk membalikkan senarai terpaut. Walaupun pengendalian senarai terpaut agak rumit sedikit, ia mempunyai kelebihan pemasukan dan pemadaman yang cekap, dan digunakan secara meluas dalam pelbagai senario. Apabila menggunakan senarai terpaut, perhatian khusus perlu diberikan kepada ketepatan penunjuk untuk mengelakkan masalah seperti kebocoran memori.

Atas ialah kandungan terperinci pembalikan senarai pautan golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!