golangは二重リンクリストを実装します

二重リンク リスト (二重リンク リスト) は一般的に使用されるデータ構造であり、リンク リスト内の任意の位置で挿入、削除、またはクエリ操作を O(1) 時間以内に実行できます。

Golang で二重リンク リストを実装するには、ポインターを使用する必要があります。これは、Golang の型はすべて値型であり、元のデータを直接変更できないためです。ポインタを介して値の変更や転送を容易に行うことができ、二重連結リストの操作を実現します。

以下は、二重リンク リストの単純な Golang 実装です:

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()
}

上記のコードでは、まず、リンク リストを含む Node 構造を定義します。各ノードには、data、previous、および next のデータが必要です。このうち、data にはノードの値が格納され、previous には前のノードのアドレスが格納され、next には次のノードのアドレスが格納されます。

次に、リンク リスト全体を表す LinkedList 構造を定義します。この構造体には、リンク リストの先頭ポインタ head と末尾ポインタ tail が含まれています。

以下は、二重リンク リストの実装に必要なメソッドです。

// 在链表头部插入一个元素
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()
}

これらのメソッドを定義した後、main 関数オブジェクトでリンク リストをインスタンス化し、実行できます。操作:

func main() {
    list := LinkedList{}

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

    list.display()

    list.delete(3)

    list.display()
}

上記のコードでは、最初に LinkedList オブジェクト list をインスタンス化し、次に 4 つの要素を順番に挿入します: 1、2、3、4 。初めて display メソッドを呼び出すと、リンク リストの内容が出力されます。

4 1 2 3

次に、要素 3 を削除して、display メソッドを呼び出します。メソッドを再度実行して、リンク リストの最新の内容を出力します:

4 1 2

二重リンク リストのこの単純な Golang 実装では、ポインタを使用してリンク リストを作成および変更する方法、および挿入、削除、挿入などの操作を実装する方法を示します。リンクされたリストのクエリ。効率的なデータ構造を作成するために二重リンク リストを使用する必要がある場合は、上記のコードを参照して、Golang で二重リンク リストを実装する方法を学習してください。

以上がgolangは二重リンクリストを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。