golang リンク リストの基礎となる実装

1. リンク リストの概要

リンク リストはノードで構成されるデータ構造であり、各ノードにはデータと次のノードへのポインタが含まれています。配列と比較して、リンク リストには、最初に連続したメモリ空間を割り当てる必要がないため、動的に拡張できるという利点があります。リンク リストは、一方向リンク リスト、二重リンク リスト、循環リンク リストなど多くの種類に分類されます。

この記事では、golang での一方向リンク リストの基本的な実装について説明します。

2. 一方向リンク リストの実装

golang では、一方向リンク リストの基礎となる実装はポインターを使用してノード間の関係を構築します。各ノードは次のように定義されます。

type Node struct {
    val interface{}
    next *Node
}

ここで、val はノードの値を表し、next は次のノードへのポインターを表します。一方向リンク リストは次のように定義されます。

type SinglyLinkedList struct {
    head *Node
}

ここで、head はリンク リストのヘッド ノード、つまり最初のノードを表します。

次に、挿入、削除、検索、走査など、リンク リストの一般的な操作を実装します。

1. 挿入操作

最初に、リンク リストの先頭への挿入とリンク リストの末尾への挿入という 2 つの挿入操作を紹介します。

リンク リストの先頭への挿入操作は次のとおりです。

func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
    node := &Node{val: val}
    node.next = l.head
    l.head = node
}

新しいノード node を作成し、ノード値を val## に設定します。 # を指定し、元のヘッド ノード l.head をポイントし、最後の更新 l.head は新しいノードをポイントできます。

リンク リストの末尾での挿入操作は次のとおりです:

func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
    node := &Node{val: val}
    if l.head == nil {
        l.head = node
    } else {
        curr := l.head
        for curr.next != nil {
            curr = curr.next
        }
        curr.next = node
    }
}

最初に新しいノード

node を作成します。リンク リストが空の場合は、新しいノードを設定しますノードをヘッド ノードとして使用します。それ以外の場合は、ヘッド ノードから開始して最後のノード curr.next == nil が見つかるまでリンク リストをトラバースし、その next が新しいノードを指すようにします。

2. 削除操作

削除操作には、指定されたノードの削除と、リンク リスト内の指定されたすべてのノード (同じノード値) の削除が含まれます。

指定したノードを削除する操作は次のとおりです。

func (l *SinglyLinkedList) DeleteNode(node *Node) {
    curr := l.head
    if curr == node {
        l.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next == node {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

削除するノードがヘッド ノードの場合は、

l.head を次のノードに直接ポイントするだけです。ノード。それ以外の場合は、ヘッド ノードから開始してリンク リストを走査し、削除するノードを見つけて (curr.next == node)、その next で次のノードを指します。

リンクリスト内の指定ノードをすべて削除する操作は次のとおりです。

func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
    for l.head != nil && l.head.val == val {
        l.head = l.head.next
    }

    curr := l.head
    for curr != nil {
        for curr.next != nil && curr.next.val == val {
            curr.next = curr.next.next
        }
        curr = curr.next
    }
}

先頭ノードの値が

val の場合、指定ノードを順番に削除します。 。次に、ヘッド ノードからリンク リストをたどって、同じ値を持つノードを順番に削除します。

3. 検索操作

検索操作には、ノード値を指定してノードを検索する方法と、リンク リスト内のノードのインデックスを検索する方法の 2 つの主な方法があります。

ノード値を指定してノードを見つける操作は次のとおりです。

func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
    curr := l.head
    for curr != nil {
        if curr.val == val {
            return curr
        }
        curr = curr.next
    }
    return nil
}

ヘッド ノードから開始してリンク リストをたどり、ノードの値と指定された値を比較します

val を返し、一致するとノードを返し、それ以外の場合は nil を返します。

リンク リスト内のノードのインデックスを見つける操作は次のとおりです。

func (l *SinglyLinkedList) FindIndex(node *Node) int {
    curr := l.head
    index := 0
    for curr != nil {
        if curr == node {
            return index
        }
        curr = curr.next
        index++
    }
    return -1
}

ヘッド ノードから開始してリンク リストをトラバースし、ノードを順番に比較して、それらが一致しているかどうかを確認します。指定されたノード

node と同じです。同じであれば、ノードが位置するインデックスを返し、それ以外の場合は、-1 を返します。

4. トラバーサル操作

トラバーサル操作には、すべてのノードを走査する方法とすべてのノードの値を走査する方法の 2 つの主な方法があります。

すべてのノードを走査する操作は次のとおりです。

func (l *SinglyLinkedList) Traverse() []*Node {
    nodes := make([]*Node, 0)
    curr := l.head
    for curr != nil {
        nodes = append(nodes, curr)
        curr = curr.next
    }
    return nodes
}

ヘッド ノードから開始してリンク リストを走査し、すべてのノードを

nodes スライスに順番に追加します。スライスを返します。

すべてのノードの値を走査する操作は次のとおりです。

func (l *SinglyLinkedList) TraverseValues() []interface{} {
    values := make([]interface{}, 0)
    curr := l.head
    for curr != nil {
        values = append(values, curr.val)
        curr = curr.next
    }

    return values
}

ヘッド ノードから開始してリンク リストを走査し、すべてのノードの値を ## に追加します。 #values

を順番にスライスし、スライスを返します。 3. 概要

golang では、一方向リンク リストの基礎となる実装はポインターを使用してノード間の関係を構築します。挿入、削除、検索、トラバーサルなどの一般的な操作を実装することで、リンク リストの性質と利点をよりよく理解できるようになり、また、golang が最下位レベルでリンク リストを実装する方法についてもよりよく理解できるようになります。実際の開発では、リンク リストは、LRU キャッシュ、逆リンク リストなど、さまざまなシナリオに適用できます。

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