Go言語のリンクリスト操作

リンク リストは、物理ストレージ ユニット上の非順次および非順次のストレージ構造であり、データ要素の論理的順序は、リンク リスト内のポインタのリンク順序を通じて実現されます。

 

リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 2 つの部分で構成されます。1 つはデータ要素を格納するデータ フィールドで、もう 1 つは次のノードのアドレスを格納するポインタ フィールドです。

リンクリスト構造を使用すると、配列を使用する際にデータサイズを事前に知る必要があるというデメリットを回避でき、コンピュータのメモリ空間を最大限に活用し、柔軟なメモリの動的管理を実現できます。しかし、リンクリストは配列のランダム読み取りの利点を失い、同時にノードのポインタフィールドの増加により比較的大きなスペースオーバーヘッドを持ちます。

リンク リストでは、リスト上の任意の位置でノードの挿入と削除が可能ですが、ランダム アクセスは許可されません。リンク リストには、単一リンク リスト、二重リンク リスト、循環リンク リストの 3 種類があります。

単一リンクリスト

一方向リンクリストの各ノードにはデータフィールドとポインタフィールドの 2 つの部分が含まれており、前のノードのポインタは次のノードを指し、これらが順番に接続されてリンクリストを形成します。

ここでは、ヘッド ノード、ヘッド ノード、ヘッド ポインターという 3 つの概念を紹介します。

• ヘッドノード：下図のa1の位置など、連結リストの最初の要素を格納するノードです。
• ヘッドノード: ヘッドノードの前に付加されるノードであり、そのポインタフィールドはヘッドノードを指します。ヘッド ノードのデータ フィールドには、リンク リストの長さまたはその他の情報を格納することも、情報を格納せずに空にすることもできます。
• ヘッドポインタ: リンクされたリストの最初のノードへのポインタです。リンクリストにヘッドノードが存在する場合、ヘッドポインタはヘッドノードを指し、リンクリストにヘッドノードが存在しない場合、ヘッドポインタはヘッドノードを指す。

リンク リストではヘッド ノードは必要ありませんが、ヘッド ノードを追加すると次の利点があります。

• ヘッドノードの追加後、ヘッドノードのアドレスがヘッドノードのポインタフィールドに格納され、リンクリストの最初のデータ要素に対する操作は特別な処理を行わずに他のデータ要素の操作と同じになります。
• ヘッド ノードを追加した後、リンク リストが空かどうかに関係なく、ヘッド ポインターはヘッド ノードを指す非 null ポインターになります。リンク リストが空の場合、ヘッド ノードのポインター フィールドは空になります。

Struct を使用して単一リンクリストを定義する

Structを使用すると様々なデータ型に対応でき、連結リストのノードとして使用するのに最適です。構造体には複数のメンバーを含めることができ、これらのメンバーは基本型、カスタム型、配列型、またはポインター型にすることができます。ここで、ポインター型メンバーを使用して、次のノードのアドレスを格納できます。

[例1] Structを使用して一方向リンクリストを定義します。

type Node struct {
    Data  int
    Next  *node
} 

このうち、Data というメンバはノードに有用なデータを格納するために使用され、Next は次のノードのデータ型である Node struct 型の data を指すポインタ型のメンバです。

[例 2] リンク リストに値を代入し、リンク リスト内の各ノードを走査します。

package main

import "fmt"

type Node Struct {
    data int
    next *Node
}

func Showned(p * Node) {//トラバース
    for p！=オフ {
        fmt.Println (* p)
        p = p.next //ポインタを移動する
    }
}

func main() {
     var head = new(Node)
     head.data = 1
     var node1 = new(Node)
     node1.data = 2
     head.next = node1
     var node2 = new(Node)
     node2.data = 3
     node1.next = node2
     Shownode(head)
} 

操作の結果は次のようになります。

{1 0xc00004c1e0}
{2 0xc00004c1f0}
{3 <nil>}

ノードの挿入

単結合リストのノード挿入方法には、一般的に先頭挿入方法と末尾挿入方法が用いられる。

1) ヘッド挿入方法

挿入ごとにリンク リストの先頭にノードが挿入されます。コードは次のとおりです。

package main

import "fmt"

type Node struct { //ノードの構造体
    data int //データ部分
    next *Node //次のノードのアドレス
}

func Shownode(p *Node){   //ノードを巡回する関数
    for p != nil{
        fmt.Println(*p)
        p=p.next  //ポインタを移動
    }
}

func main() {
    var head = new(Node)
    head.data = 0
    var tail *Node
    tail = head   //tail はヘッドノードのアドレスを参照する。最初は、tail のポインタはヘッドノードを指している。
    for i :=1 ;i<10;i++{
        var node = Node{data:i}
        node.next = tail   //新しいノードのnextをヘッドノードに設定する
        tail = &node      //ヘッドノードを再度割り当てる
    }

    Shownode(tail) //出力
} 

操作の結果は次のようになります。

{9 0xc000036270}
{8 0xc000036260}
{7 0xc000036250}
{6 0xc000036240}
{5 0xc000036230}
{4 0xc000036220}
{3 0xc000036210}
{2 0xc000036200}
{1 0xc0000361f0}
{0 <nil>}

2) テール挿入方法

ノードが最後に挿入されるたびに、これも私たちがよく使用する方法です。

package main

import "fmt"

type Node struct{
    data int
    next *node
}

func Shownode（p * Node）{ //トラバース
    for p！= nil{
        fmt.Println(*p）
        p = p.next //ポインターを移動する
    }
}

func main（）{
    var head = new（Node）
    head.data=0
    var tail *Node
    tail = head // tailは最後のノードのアドレスを記録するために使用されます。 最初は、tailのポインターはヘッドノードを指します
    for i：= 1; i <10; i ++ {
        var node = Node{data：i}
        node.next = tail
        tail = &node
    }

    Shownode（head）//トラバース結果
} 

操作の結果は次のようになります。

{0 0xc0000361f0}
{1 0xc000036200}
{2 0xc000036210}
{3 0xc000036220}
{4 0xc000036230}
{5 0xc000036240}
{6 0xc000036250}
{7 0xc000036260}
{8 0xc000036270}
{9 <nil>}

配列の挿入・削除操作を行う場合、メモリデータの連続性を保つために大量のデータを移動する必要があるため、比較的速度が遅くなります。リンク リスト自体の記憶領域は連続していないため、リンク リスト内のデータを挿入または削除する場合、メモリの連続性を維持するためにノードを移動する必要はありません。したがって、リンク リストへのデータの挿入と削除は非常に高速です。

ただし、長所と短所があります。リンクされたリストが k 番目の要素にランダムにアクセスしたい場合、配列ほど効率的ではありません。リンクリスト内のデータは連続して格納されないため、配列のように最初のアドレスと添字に基づいてアドレス指定式を通じて対応するメモリアドレスを直接計算することはできませんが、ポインタを1ノードずつ1トラバースするまでたどる必要があります。対応するノードが見つかりました。

循環リンクリスト

循環リンク リストは、特別な種類の単一リンク リストです。

循環リンク リストと単一リンク リストの唯一の違いは、末尾ノードです。一方向リンク リストの末尾ノード ポインタは、空のアドレスを指し、これが最後のノードであることを示します。一方、循環リンク リストの末尾ノード ポインタは、最後に接続されているリンク リストの先頭ノードを指します。下図に示すように、リング状に終わるので「ループ」と呼ばれます。」リンクリスト。

単一リンク リストと比較して、循環リンク リストの利点は、チェーンの最後からチェーンの先頭に移動するのがより便利であることです。処理対象のデータがリング構造の特徴を持つ場合には、循環リンクリストの使用が特に適しています。たとえば、有名なジョセフ問題は単一のリンク リストで実装できますが、循環リンク リストで実装すると、コードははるかに単純になります。

一方向リンクリストには一方向のみがあり、ノードには次のノードを指す後続ポインタが 1 つだけあります。名前が示すように、二重リンク リストは 2 つの方向をサポートしており、各ノードには次のノードを指す後続ポインタ next と、前のノードを指す前駆ポインタ prev が複数あります。

二重リンク リストには、後続ノードと先行ノードのアドレスを格納するために 2 つの追加スペースが必要です。したがって、同じ量のデータが保存される場合、二重リンク リストは単一リンク リストよりも多くのメモリ スペースを占有します。 2 つのポインターは記憶域の無駄ですが、双方向のトラバーサルをサポートできるため、二重リンク リスト操作の柔軟性も得られます。