golang melaksanakan senarai berganda

Senarai terpaut dua kali ialah struktur data yang biasa digunakan yang membolehkan kami melakukan operasi pemadaman, pemadaman atau pertanyaan di mana-mana kedudukan dalam senarai terpaut dalam kerumitan masa O(1).

Melaksanakan senarai pautan berganda di Golang memerlukan penggunaan penunjuk, kerana semua jenis dalam Golang adalah jenis nilai dan data asal tidak boleh diubah suai secara langsung. Melalui petunjuk, kami boleh mengubah suai dan memindahkan nilai dengan mudah, dengan itu merealisasikan operasi senarai berganda.

Berikut ialah pelaksanaan Golang mudah bagi senarai terpaut dua kali:

package main

import "fmt"

type Node struct {
    data     int
    previous *Node
    next     *Node
}

type LinkedList struct {
    head *Node
    tail *Node
}

func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

Dalam kod di atas, kami mula-mula mentakrifkan struktur Node, yang mengandungi setiap elemen dalam senarai terpaut Tiga data diperlukan oleh nod: data, previous dan next. Antaranya, data menyimpan nilai nod, previous menyimpan alamat nod sebelumnya dan next menyimpan alamat nod seterusnya.

Kemudian, kami mentakrifkan struktur LinkedList untuk mewakili keseluruhan senarai terpaut. Struktur ini mengandungi penuding kepala head dan penuding ekor tail senarai terpaut.

Berikut adalah beberapa kaedah yang diperlukan untuk melaksanakan senarai terpaut dua kali:

// 在链表头部插入一个元素
func (list *LinkedList) insertAtBeginning(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.head == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.next = list.head
    list.head.previous = newNode
    list.head = newNode
}

// 在链表尾部插入一个元素
func (list *LinkedList) insertAtEnd(data int) {
    newNode := &Node{
        data:     data,
        previous: nil,
        next:     nil,
    }

    if list.tail == nil {
        list.head = newNode
        list.tail = newNode
        return
    }

    newNode.previous = list.tail
    list.tail.next = newNode
    list.tail = newNode
}

// 删除链表中指定的元素
func (list *LinkedList) delete(data int) bool {
    currentNode := list.head

    for currentNode != nil {
        if currentNode.data == data {
            if currentNode == list.head {
                list.head = currentNode.next
                list.head.previous = nil
            } else if currentNode == list.tail {
                list.tail = currentNode.previous
                list.tail.next = nil
            } else {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
            }

            return true
        }

        currentNode = currentNode.next
    }

    return false
}

// 打印链表的所有元素
func (list *LinkedList) display() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Printf("%d ", currentNode.data)
        currentNode = currentNode.next
    }

    fmt.Println()
}

Selepas mentakrifkan kaedah ini, kami boleh membuat instantiate objek senarai terpaut dalam fungsi main dan melaksanakan operasi :

func main() {
    list := LinkedList{}

    list.insertAtEnd(1)
    list.insertAtEnd(2)
    list.insertAtEnd(3)
    list.insertAtBeginning(4)

    list.display()

    list.delete(3)

    list.display()
}

Dalam kod di atas, kita mula-mula membuat instantiate LinkedList objeklist, dan kemudian kita masukkan empat elemen mengikut tertib: 1, 2, 3 dan 4. Apabila kami memanggil kaedah display buat kali pertama, kami akan mengeluarkan kandungan senarai terpaut:

4 1 2 3

Kemudian, kami memadamkan elemen 3 dan memanggil kaedah display sekali lagi untuk mengeluarkan kandungan terkini senarai terpaut:

4 1 2

Pelaksanaan Golang ringkas bagi senarai terpaut dua kali ini menunjukkan cara menggunakan penunjuk untuk mencipta dan mengubah suai senarai terpaut dan cara melaksanakan operasi seperti pemasukan, pemadaman dan pertanyaan senarai terpaut. Jika anda perlu menggunakan senarai terpaut dua kali untuk mencipta struktur data yang cekap, sila rujuk kod di atas untuk mengetahui cara melaksanakan senarai terpaut dua kali di Golang.

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