Go 言語プログラミングガイド: 単一リンクリストの実装の詳細な説明-Golang-php.cn

Go 言語プログラミングガイド: 単一リンクリストの実装の詳細な説明

PHPz

リリース： 2024-03-22 17:18:04

オリジナル

942 人が閲覧しました

Go 言語プログラミングガイド: 単一リンクリストの実装の詳細な説明

Go 言語では、単一リンクリストは一連の要素を格納するために使用される一般的なデータ構造であり、シーケンシャルアクセス。この記事では、単一リンクリストの実装原理を詳しく紹介し、具体的な Go 言語のコード例を示します。

単連結リストの定義

単連結リストは、各要素 (ノード) にデータフィールドとポインターフィールドの 2 つの部分が含まれる線形リストデータ構造です。データフィールドは要素の値を格納するために使用され、ポインターフィールドは次のノードを指します。最後のノードのポインタフィールドは通常は空で、リンクリストの終わりを示します。

単一リンクリストのノード定義

まず、単一リンクリストのノードタイプを定義します。

type Node struct {
    data int
    next *Node
}

ログイン後にコピー

その中で、dataフィールドにはノードの値が格納されます。nextフィールドには、次のノードへのポインタが格納されます。

単一リンクリストの初期化

次に、単一リンクリストの初期化関数を定義します。

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

ログイン後にコピー

初期化関数では、空のリンクリストを作成し、 head ノードポインタは null に初期化されます。

単連結リストの挿入操作

単連結リストの挿入操作は、連結リストの先頭にノードを挿入する場合と、末尾にノードを挿入する場合の 2 つの状況に分けられます。リンクされたリスト。

最初の関数は、リンクリストの先頭にノードを挿入する関数です。

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

ログイン後にコピー

この関数では、まず新しいノードを作成し、その値を渡された値に初期化します。次に、新しいノードのポインタをリンクリストの先頭にポイントし、最後にリンクリストの先頭ノードを新しいノードに更新します。

次は、リンクリストの最後にノードを挿入する関数です。

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

ログイン後にコピー

この関数は、まず新しいノードを作成し、リンクリストが空かどうかを判断します。空の場合は、新しいノードが直接ヘッドノードとして設定されます。それ以外の場合は、最後のノードが見つかるまでリンクリストが走査され、その後、新しいノードが最後のノードの後に挿入されます。

単一リンクリストの削除操作

削除操作は、ヘッドノードの削除と指定された値を持つノードの削除の 2 つの状況に分かれます。

最初の関数は、ヘッドノードを削除する関数です。

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

ログイン後にコピー

この関数は、ヘッドノードポインターを次のノードに直接ポイントすることで、ヘッドノードを削除します。

次は、指定された値を持つノードを削除する関数です:

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

ログイン後にコピー

この関数では、まずリンクリストが空かどうかを判断する必要があります。次に、ヘッドノードから開始してリンクリストを走査し、ターゲット値が存在するノードを見つけて削除します。

単一リンクリストのトラバーサル操作

最後は、単一リンクリストのトラバーサル操作です:

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

ログイン後にコピー

この関数は、ヘッドノードから開始してノードの値を 1 つずつ出力します。リンクされたリストの最後まで。

サンプルコード

以下は、単一リンクリストの使用方法を示す完全なサンプルコードです。

package main

import "fmt"

type Node struct {
    data int
    next *Node
}

type LinkedList struct {
    head *Node
}

func NewLinkedList() *LinkedList {
    return &LinkedList{}
}

func (list *LinkedList) InsertAtBeginning(value int) {
    newNode := &Node{data: value}
    newNode.next = list.head
    list.head = newNode
}

func (list *LinkedList) InsertAtEnd(value int) {
    newNode := &Node{data: value}
    if list.head == nil {
        list.head = newNode
        return
    }

    current := list.head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
}

func (list *LinkedList) DeleteAtBeginning() {
    if list.head == nil {
        return
    }
    list.head = list.head.next
}

func (list *LinkedList) DeleteByValue(value int) {
    if list.head == nil {
        return
    }
    if list.head.data == value {
        list.head = list.head.next
        return
    }

    prev := list.head
    current := list.head.next
    for current != nil {
        if current.data == value {
            prev.next = current.next
            return
        }
        prev = current
        current = current.next
    }
}

func (list *LinkedList) Print() {
    current := list.head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.next
    }
    fmt.Println()
}

func main() {
    list := NewLinkedList()

    list.InsertAtEnd(1)
    list.InsertAtEnd(2)
    list.InsertAtEnd(3)
    list.Print()

    list.DeleteByValue(2)
    list.Print()

    list.DeleteAtBeginning()
    list.Print()
}

ログイン後にコピー

上記は、Go 言語を使用して次のことを行うための詳細なガイドです。単一リンクリストを実装します。この記事の紹介とサンプルコードを通じて、読者が単一リンクリストの原理と実装についてより深く理解できることを願っています。

以上がGo 言語プログラミングガイド: 単一リンクリストの実装の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。