Memahami dan menggunakan prinsip asas dan kaedah senarai terpaut Golang

Prinsip dan kaedah asas pelaksanaan senarai terpaut Golang

Senarai terpaut ialah struktur data biasa, yang terdiri daripada satu siri nod, setiap nod mengandungi data dan penunjuk ke nod seterusnya. Setiap nod disambungkan antara satu sama lain untuk membentuk senarai terpaut tersusun. Di Golang, kami boleh melaksanakan senarai terpaut dengan menggunakan struktur dan petunjuk Di bawah kami akan memperkenalkan prinsip asas dan kaedah senarai terpaut secara terperinci, dan melampirkan contoh kod tertentu.

Struktur asas senarai terpaut

Pertama, kita perlu menentukan struktur nod senarai terpaut Di Golang, kita boleh menggunakan struktur untuk mencapai ini.

type ListNode struct {
    Val  int       // 节点存储的数据
    Next *ListNode // 指向下一个节点的指针
}

Operasi asas senarai terpaut

Dalam senarai terpaut, operasi biasa termasuk sisipan, pemadaman dan carian. Di bawah ini kami akan memperkenalkan pelaksanaan khusus operasi ini satu demi satu.

1. Operasi sisipan

Operasi sisipan senarai terpaut boleh dibezakan antara dua situasi: memasukkan di kepala senarai terpaut dan memasukkan di tengah senarai terpaut. Pelaksanaan khusus operasi sisipan adalah seperti berikut:

func Insert(head *ListNode, val int) *ListNode {
    newNode := &ListNode{
        Val:  val,
        Next: nil,
    }
    if head == nil {
        return newNode
    }
    newNode.Next = head
    return newNode
}

Apabila memasukkan di kepala senarai terpaut, kita hanya perlu menghalakan penuding Seterusnya nod baharu ke nod kepala senarai terpaut asal, dan mengembalikan yang baharu nod sebagai nod kepala baharu.

2. Padam operasi

Operasi pemadaman senarai terpaut juga boleh dibahagikan kepada dua situasi: memadamkan nod yang ditentukan dalam senarai terpaut dan memadamkan nod dengan nilai yang ditentukan dalam senarai terpaut. Pelaksanaan khusus operasi pemadaman adalah seperti berikut:

func DeleteNode(head *ListNode, target int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    cur := dummy
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == target {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

Apabila memadamkan nod tertentu dalam senarai terpaut, kita hanya perlu menghalakan penuding Seterusnya nod semasa ke penuding Seterusnya nod seterusnya.

3. Operasi carian

Operasi carian senarai terpaut sering digunakan untuk menentukan sama ada nilai tertentu wujud dalam senarai terpaut. Pelaksanaan khusus operasi carian adalah seperti berikut:

func Search(head *ListNode, target int) bool {
    cur := head
    for cur != nil {
        if cur.Val == target {
            return true
        }
        cur = cur.Next
    }
    return false
}

Kita boleh merentasi setiap nod senarai terpaut dan menentukan sama ada nilai nod adalah sama dengan nilai sasaran Jika sama, kembalikan benar, jika tidak, teruskan merentasi sehingga akhir senarai terpaut.

Kendalian lintasan senarai terpaut

Kendalian lintasan senarai terpaut sering digunakan untuk mencetak senarai terpaut atau mendapatkan panjang senarai terpaut. Pelaksanaan khusus operasi traversal adalah seperti berikut:

func Traverse(head *ListNode) {
    cur := head
    for cur != nil {
        fmt.Println(cur.Val)
        cur = cur.Next
    }
}

func Length(head *ListNode) int {
    count := 0
    cur := head
    for cur != nil {
        count += 1
        cur = cur.Next
    }
    return count
}

Kami boleh mengakses setiap nod senarai terpaut dengan menggerakkan penuding secara berterusan dan melakukan operasi yang sepadan.

Di atas adalah prinsip asas dan kaedah pelaksanaan senarai terpaut Golang Dengan mentakrifkan struktur dan penunjuk nod untuk membina senarai terpaut, operasi seperti sisipan, pemadaman, carian dan traversal direalisasikan. Melalui operasi ini, kami boleh memproses data dalam senarai terpaut secara fleksibel dan seterusnya melaksanakan fungsi yang lebih kompleks. Saya harap artikel ini dapat membantu anda memahami prinsip dan kaedah senarai terpaut.

Atas ialah kandungan terperinci Memahami dan menggunakan prinsip asas dan kaedah senarai terpaut Golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!