Bagaimana untuk melaksanakan senarai pautan berganda dalam golang

Senarai terpaut berganda ialah struktur data biasa yang boleh mewujudkan perkaitan dua hala antara elemen, menjadikan operasi seperti penyisipan, pemadaman dan traversal dalam senarai terpaut sangat cekap. Dalam bahasa Go, pelaksanaan senarai terpaut dua kali adalah sangat mudah Artikel ini akan memperkenalkan cara menggunakan Go untuk melaksanakan senarai terpaut dua kali.

Senarai berganda adalah struktur terpaut dan setiap nodnya mengandungi tiga bahagian: penuding pendahulu sebelum, penuding pengganti seterusnya dan data medan data. Dalam Go, kita boleh mentakrifkan struct untuk mewakili nod senarai berganda:

type ListNode struct {
    prev *ListNode
    next *ListNode
    data interface{}
}

di mana, prev dan next masing-masing menunjuk ke nod pendahulu dan pengganti nod semasa, dan data ialah data yang disimpan nod.

Untuk melaksanakan senarai terpaut berganda, kita perlu menentukan jenis Senarai Terpaut, yang mengandungi penuding ke nod kepala dan nod ekor senarai terpaut, serta panjang saiz senarai terpaut:

type LinkedList struct {
    head *ListNode
    tail *ListNode
    size int
}

Mari kita laksanakannya satu persatu.

Sisipkan elemen

Sisipkan elemen ke dalam senarai terpaut berganda Terdapat tiga situasi utama:

1. Sisipkan elemen di kepala senarai terpaut.
2. Sisipkan elemen di hujung senarai terpaut.
3. Sisipkan elemen di tengah-tengah senarai terpaut.

Dalam Go, kita boleh mentakrifkan kaedah Sisip untuk melaksanakan tiga situasi di atas:

func (list *LinkedList) Insert(data interface{}) {
    node := &ListNode{data: data}
    if list.head == nil {
        list.head = node
        list.tail = node
    } else {
        node.prev = list.tail
        list.tail.next = node
        list.tail = node
    }
    list.size++
}

Pertama, kami mencipta nod nod baharu untuk menyimpan data yang hendak dimasukkan. data. Jika senarai terpaut kosong, nod baharu akan digunakan sebagai nod kepala dan nod ekor. Jika tidak, masukkan nod baharu selepas nod ekor dan kemas kini penuding nod ekor ke nod baharu. Akhirnya, panjang senarai terpaut ditambah 1.

Memadamkan elemen

Sama seperti memasukkan elemen, memadamkan elemen juga mungkin melibatkan tiga situasi:

1. Memadamkan elemen kepala senarai terpaut.
2. Padamkan elemen ekor senarai terpaut.
3. Padamkan elemen di tengah-tengah senarai terpaut.

Berikut ialah contoh pelaksanaan kaedah Padam:

func (list *LinkedList) Delete(data interface{}) {
    node := list.find(data)
    if node != nil {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            list.head = node.next
        }
        if node.next != nil {
            node.next.prev = node.prev
        } else {
            list.tail = node.prev
        }
        list.size--
    }
}

func (list *LinkedList) find(data interface{}) *ListNode {
    node := list.head
    for node != nil && node.data != data {
        node = node.next
    }
    return node
}

Pertama, kita perlu mencari nod nod yang hendak dipadam, yang dilaksanakan melalui cari fungsi tambahan . Jika nod yang hendak dipadam ditemui, penunjuk nod pendahulu dan pengganti perlu dikemas kini berdasarkan kedudukan nod. Jika nod yang akan dipadamkan ialah nod kepala, kemas kini penuding nod kepala ke nod seterusnya jika nod yang akan dipadamkan ialah nod ekor, kemas kini penuding nod ekor ke nod sebelumnya. Akhir sekali, kurangkan panjang senarai terpaut sebanyak 1.

Merentasi elemen

Merentasi senarai terpaut berganda adalah sangat mudah Anda hanya perlu bermula dari nod kepala dan terus melintasi sepanjang penunjuk pengganti seterusnya. Traversal songsang boleh bermula dari nod ekor dan melintasi sepanjang penunjuk pendahulu sebelum. Berikut ialah dua kaedah untuk melaksanakan traversal ke hadapan dan ke belakang masing-masing:

func (list *LinkedList) Traverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.head
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.next
    }
    return result
}

func (list *LinkedList) ReverseTraverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.tail
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.prev
    }
    return result
}

Apabila melintasi, kita perlu mencipta hirisan untuk menyimpan hasil traversal, dan kemudian bermula dari nod kepala atau ekor dan melintasi setiap nod sepanjang penunjuk dan simpan data nod ke dalam kepingan.

Ringkasan

Melalui kod di atas, kami telah berjaya melaksanakan operasi asas senarai berganda. Dalam aplikasi praktikal, terdapat banyak sambungan dan pengoptimuman kepada senarai terpaut dua kali, seperti memasukkan atau memadam elemen pada kedudukan tertentu dalam senarai terpaut, mengakses elemen melalui indeks, dsb. Pembaca boleh menjalankan kajian dan latihan lanjut mengikut keperluan.

Sampel kod artikel ini telah dimuat naik ke GitHub untuk rujukan pembaca: https://github.com/linjiawei123/golang-doubly-linked-list

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan senarai pautan berganda dalam golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!