Pelaksanaan asas senarai terpaut golang

1. Pengenalan kepada senarai terpaut

Senarai terpaut ialah struktur data yang terdiri daripada nod Setiap nod mengandungi data dan penunjuk ke nod seterusnya. Berbanding dengan tatasusunan, senarai terpaut mempunyai kelebihan pengembangan dinamik kerana mereka tidak perlu memperuntukkan ruang memori berterusan pada permulaan. Senarai terpaut dibahagikan kepada banyak jenis seperti senarai terpaut sehala, senarai terpaut dua kali dan senarai terpaut bulat.

Dalam artikel ini, kita akan membincangkan pelaksanaan asas senarai pautan tunggal dalam golang.

2. Pelaksanaan senarai terpaut sehala

Dalam golang, pelaksanaan asas senarai terpaut sehala menggunakan penunjuk untuk membina hubungan antara nod. Setiap nod ditakrifkan seperti berikut:

type Node struct {
    val interface{}
    next *Node
}

di mana val mewakili nilai nod dan next mewakili penuding ke nod seterusnya. Senarai terpaut sehala ditakrifkan seperti berikut:

type SinglyLinkedList struct {
    head *Node
}

di mana head mewakili nod kepala senarai terpaut, iaitu, nod pertama.

Seterusnya, kami akan melaksanakan operasi biasa senarai terpaut, termasuk sisipan, pemadaman, carian dan traversal.

1. Operasi sisipan

Kami mula-mula memperkenalkan dua operasi sisipan: memasukkan di kepala senarai terpaut dan memasukkan di hujung senarai terpaut.

Operasi sisipan di kepala senarai terpaut adalah seperti berikut:

func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
    node := &Node{val: val}
    node.next = l.head
    l.head = node
}

Buat nod baharu node, tetapkan nilai nod kepada val, dan kemudian arahkannya ke nod kepala asal l.head, dan akhirnya Hanya kemas kini l.head untuk menghala ke nod baharu.

Operasi sisipan di hujung senarai terpaut adalah seperti berikut:

func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
    node := &Node{val: val}
    if l.head == nil {
        l.head = node
    } else {
        curr := l.head
        for curr.next != nil {
            curr = curr.next
        }
        curr.next = node
    }
}

Mula-mula buat nod baharu node Jika senarai terpaut kosong, tetapkan nod baharu sebagai kepala nod. Jika tidak, lintasi senarai terpaut bermula dari nod kepala sehingga nod terakhir curr.next == nil ditemui, dan halakan nextnya ke nod baharu.

2. Operasi pemadaman

Operasi pemadaman termasuk pemadaman nod yang ditentukan dan pemadaman semua nod yang ditentukan (nilai nod yang sama) dalam senarai terpaut.

Padamkan nod yang ditentukan seperti berikut:

func (l *SinglyLinkedList) DeleteNode(node *Node) {
    curr := l.head
    if curr == node {
        l.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next == node {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

Jika nod yang hendak dipadamkan ialah nod kepala, hanya tunjuk l.head ke nod seterusnya. Jika tidak, lintasi senarai terpaut bermula dari nod kepala, cari nod yang hendak dipadamkan (curr.next == node), dan halakan nextnya ke nod seterusnya.

Operasi untuk memadam semua nod yang ditentukan dalam senarai terpaut adalah seperti berikut:

func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
    for l.head != nil && l.head.val == val {
        l.head = l.head.next
    }

    curr := l.head
    for curr != nil {
        for curr.next != nil && curr.next.val == val {
            curr.next = curr.next.next
        }
        curr = curr.next
    }
}

Jika nilai nod kepala ialah val, padamkan nod yang ditentukan mengikut turutan. Kemudian lintasi senarai terpaut bermula dari nod kepala dan padam nod dengan nilai yang sama dalam urutan.

3. Operasi carian

Terdapat dua kaedah utama operasi carian: mencari nod dengan menyatakan nilai nod dan mencari indeks nod dalam senarai terpaut.

Operasi mencari nod dengan menyatakan nilai nod adalah seperti berikut:

func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
    curr := l.head
    for curr != nil {
        if curr.val == val {
            return curr
        }
        curr = curr.next
    }
    return nil
}

Lintas senarai terpaut bermula dari nod kepala, bandingkan nilai nod dengan nilai yang ditentukan dalam urutan val, dan kembalikan nod sebaik sahaja ia sepadan, jika tidak, kembalikan nil.

Operasi untuk mencari indeks nod dalam senarai terpaut adalah seperti berikut:

func (l *SinglyLinkedList) FindIndex(node *Node) int {
    curr := l.head
    index := 0
    for curr != nil {
        if curr == node {
            return index
        }
        curr = curr.next
        index++
    }
    return -1
}

Lintas senarai terpaut bermula dari nod kepala, dan bandingkan nod dalam urutan untuk melihat sama ada ia adalah sama dengan nod yang ditentukan node Jika ia adalah sama, kembalikan lokasi nod, jika tidak -1 dikembalikan.

4. Operasi traversal

Terdapat dua kaedah utama operasi traversal: melintasi semua nod dan melintasi nilai semua nod.

Kendalian melintasi semua nod adalah seperti berikut:

func (l *SinglyLinkedList) Traverse() []*Node {
    nodes := make([]*Node, 0)
    curr := l.head
    for curr != nil {
        nodes = append(nodes, curr)
        curr = curr.next
    }
    return nodes
}

Lintas senarai terpaut bermula dari nod kepala, tambah semua nod pada hirisan nodes mengikut tertib dan kembalikan hirisan.

Kendalian melintasi nilai semua nod adalah seperti berikut:

func (l *SinglyLinkedList) TraverseValues() []interface{} {
    values := make([]interface{}, 0)
    curr := l.head
    for curr != nil {
        values = append(values, curr.val)
        curr = curr.next
    }

    return values
}

Lintas senarai terpaut bermula dari nod kepala, tambah nilai semua nod ke values hiris mengikut tertib, dan kembalikan kepingan itu.

3. Ringkasan

Dalam golang, pelaksanaan asas senarai terpaut sehala menggunakan penunjuk untuk membina hubungan antara nod. Dengan melaksanakan operasi biasa seperti sisipan, pemadaman, carian dan traversal, kami lebih memahami sifat dan kelebihan senarai terpaut, dan juga lebih memahami cara golang melaksanakan senarai terpaut di peringkat bawah. Dalam pembangunan sebenar, senarai terpaut boleh digunakan pada banyak senario, seperti cache LRU, senarai terpaut terbalik, dsb.

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