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

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 サイトの他の関連記事を参照してください。