Verse における連結リスト | Unreal Editor for Fortnite ドキュメンテーション

連結リストは、コンピュータサイエンスでは一般的なデータ構造です。連結リストを使用して、音楽のプレイリストを表示したり、操作の履歴を追跡したりすることができます。

概要

連結リストは、各要素がリストの次の要素への参照を格納している線形データ構造です。連結リストの各要素は ノード と呼ばれます。ノードは、データと次のノードへの参照を保持しているコンテナです。 image alt text

異なるノード同士を順次連結させていくことで、連結リストが作成されます。リストの最初のノードを先頭ノード、最後のノードを末尾ノードと呼びます。リストをトラバースするには、先頭ノードから開始して、各ノードの参照を使用して次の要素に移動します。

連結リストを使用すべきケース

連結リストは、スタックやキューなどの他のデータ構造を実装するための適切な出発点です。連結リストはシーケンシャルアクセスのためにデータを格納する簡単な方法であり、新しい要素をすばやく挿入することができます。配列とは異なり、連結リストはメモリでは連続 (隣り合わせ) していません。つまり、ノードがメモリ内の任意の場所に存在することができ、次のノードへの参照によってその位置がわかります。連結リストからノードを挿入または削除するには、次のノードへの参照を変更するだけで済みます。

連結リストを使用すべきではないケース

プログラムで要素へのランダムアクセスが必要な場合 (リストからランダムにプレイヤーを選択するなど) 、連結リストにはこれに対応する機能がありません。リストの途中の特定のノードにアクセスする必要がある場合は、先頭から開始して必要な特定のノードまでトラバースする必要があるため、連結リストを使用すると、配列より効率性が低下します。

Verse での実装

Verse API には連結リストの組み込みの実装はないものの、自分で作成することができます。

連結リストはノードで構成されており、連結リストを表すクラスを定義する必要があります。ノードの一般的な型の例を以下に示します。

list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

この例では、オプション変数 Next はリストの次のノードへの参照を格納します。これは list_node 型です。なお、Next は option 変数である必要があります。これは、ノードが常に次のノードを指すとは限らないためです (連結リストの末尾ノードなど)。リストの連結を動的に変更したい場合は、Next は var である必要があります。ノードには値も含まれます。これらは、Data に格納されます。これはノードの一般的な型であるため、Data は any 型であり、ノードには任意のデータ型を含めることができます。ノードは共通型、コンテナ、または別の連結リストである可能性もあります！

Node1 := list_node{ Next := false, Data := 1 } # int 型
Node2 := list_node{ Next := false, Data := "String" } # string 型
Node3 := list_node{ Next := false, Data := []int} # array 型
Node4 := list_node{ Next := false, Data := list_node } # list_node クラス
Node5 := list_node{ Next := false, Data := Node1 } # 最初のノード

<unique> 指定子により、list_node を比較できるようになります。これにより、ノードが他のノードと等しいかどうかを確認することができます。たとえば、ノードがリストの先頭であるか末尾であるかなどを確認できます。

数値や文字列のみを処理するノードなど、より特殊な実装が必要な場合は、Data の型と一致するように変更してください。Data が comparable 型である場合、Data 内のその値を別の値と比較して特定のノードを見つけることができます。

単方向連結リスト

連結リストの最も基本的なタイプは 単方向連結リスト です。このリストでは、各ノードに次のノードへの参照 (単方向の連結) が含まれています。複数のノードをリストに変換するには、各ノードの Next への参照を使用してノード同士を連結させます。

# 各ノードをリストの次のノードに連結させます。
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

ノード同士は連結されていますが、連結リストはクラスで定義することをお勧めします。そうすることで、最初のノードを毎回参照するのではなく、リストを使用して簡単に関数を実行できるようになります。

linked_list := class:
    var Head:list_node

基本 linked_list クラスには、先頭ノードへの参照のみが含まれます。linked_list クラスのインスタンスを作成するには、ノード同士を連結させ、先頭ノードを使用してリストをインスタンス化します。

# node1 を先頭に持つ連結リストを作成します。
BasicList:linked_list = linked_list{Head := Node1}

リストをトラバースするには、先頭ノードから開始してリストをイテレートし、末尾で停止します。これは外部関数でも linked_list クラス内のクラス関数でも実行できます。先頭から末尾までリスト全体をトラバースする関数の例を以下に示します。

linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node:= option{Head} # 現在のノード
        var NodeNumber:int = 1 # 現在のノードの番号
        Print("Starting at the Head Node...")
        # 現在のノードに次のノードがある場合は、現在のノードを
        # リストの次のノードに設定します
        loop:
            if(NextNode := CurrentNode?.Next?):
                set CurrentNode = option{NextNode}
                set NodeNumber += 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No next node, this is the Tail node!")
                break

この例では、TraverseList() 関数が CurrentNode に Next への参照が含まれているかどうかをチェックし、NextNode にその参照を格納します。参照が含まれている場合、末尾ノードに到達するまで、繰り返し CurrentNode を NextNode に設定します。末尾ノードには Next への参照がないため、ループは末尾ノードで停止します。

双方向連結リスト

単方向連結リストとは異なり、双方向連結リスト のノードには、前ノードと呼ばれるその前にあるノードへの参照も含まれます。

doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node= false
    Data:any = {}

つまり、双方向連結リストのノードは順方向にも逆方向にもトラバースすることができます。これは外部関数でもクラス関数でも可能です。先頭から末尾までリストをトラバースし、末尾から先頭まで逆方向にトラバースする関数の例を以下に示します。

doubly_linked_list := class():
    Head:doubly_linked_node

    # LinkedList をトラバースします。ただし、逆方向にも順方向にもトラバースします！
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node:= option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")
        loop:
            if(NextNode := CurrentNode?.Next?):
                set CurrentNode = option{NextNode}
                set NodeNumber += 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No next node, this is the Tail node!")
                break
        Print("Now let's go backward to the Head node...")
        loop:
            if(PreviousNode := CurrentNode?.Previous?):
                set CurrentNode = option{PreviousNode}
                set NodeNumber -= 1
                Print("Traveling to Node {NodeNumber}!")
            else:
                Print("No previous Node, we're back at the Head node!")
                break

循環連結リスト

循環連結リスト では、先頭ノードは末尾ノードに連結されています。つまり、リスト全体をトラバースし、末尾ノードを通過して、先頭ノードに戻ってくることができます。循環連結リストは単方向連結、双方向連結のどちらでもかまいません。唯一の要件は、先頭ノードが末尾ノードに連結しており、末尾ノードも先頭ノードに連結していることです。

イテレータ

イテレータは、コンテナに対してイテレートし、その過程で操作を実行することができるオブジェクトです。イテレータは、乗客が満員の電車の車両のようなものだと考えることができます。列車は線路を走り、途中の各駅に停車します。各駅で、列車は乗客の乗降などのタスクを実行します。連結リストでいうと、各駅はリストのノードに該当します。列車 (イテレータ) はリストを順方向に各ノードまで移動し、停止した場所で操作を実行することができます。

イテレータが連結リストで役立つのは、先頭や末尾のノードだけでなく、特定の場所で操作を実行できるからです。

linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # イテレータの移動先の NextNode がある場合は、そのノードに移動します
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

この例では、イテレータには、イテレートするリストへの参照とイテレータが現在停止している CurrentNode が含まれます。Next() 関数は、CurrentNode にその後にノードがあるかどうかを確認してから、そのノードに移動します。この例の Next() には <transacts> 指定子および <decides> 指定子が含まれていることに注意してください。関数は <transacts> である必要があります。この関数が CurrentNode var を更新するためです。また、この関数には <decides> を追加するようにしてください。Next() を失敗する可能性があるノードにすることで、次のノードまでイテレートしたかどうかがわかるようになるためです。

イテレータはリストの先頭から開始するように思えるかもしれませんが、実際には先頭より前から開始する必要があります。これは、イテレータが先頭ノードに対して操作を実行できるようにするためです。たとえば、先頭ノードの前にノードを挿入したり、先頭ノードを完全に削除したりできます。

イテレータを先頭の前で初期化するには、リストの先頭を次のノードとするダミーノードに CurrentNode を初期化することができます。Verse では、CurrentNode を初期化するときに List にアクセスすることはできません。これは、クラスメンバー変数に同じスコープからアクセスすることはできず、関数内など異なるスコープからのみアクセスできるためです。

linked_list_iterator := class:
    List:linked_list
    # このスコープからリストにアクセスできないため、以下の行は失敗します
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

代わりに、イテレータをインスタンス化するには、コンストラクタ関数を使用することができます。コンストラクタは、関連付けられているクラスのインスタンスを作成する複合型です。コンストラクタはオブジェクトに初期値を設定し、リストの値にアクセスしてその先頭に CurrentNode を割り当てることができます。

# 指定されたリストの先頭の前に、CurrentNode をダミー ノードとして含むイテレータを作成します。
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # コンストラクタ関数ではこのスコープからリストにアクセスできます
    CurrentNode:= list_node{Next := option{List.Head}}

linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

双方向連結リストのイテレータの初期化は、双方向に連結されたノードを使用して初期化する点を除けば、非常によく似ています。

# 指定されたリストの先頭の前に、CurrentNode をダミー ノードとして含むイテレータを作成します。
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # コンストラクタ関数ではこのスコープからリストにアクセスできます
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

ノード間でのイテレーション

リストの連結に応じて、イテレータを順方向または逆方向に進めることができます。単方向連結リストのイテレータは順方向にしか進みませんが、双方向連結リストのイテレータはどちらの方向にも進むことができます。この機能は 2 つの関数、Next() および Previous() で定義されています。なお、単方向連結リストに Previous() 関数は含まれません。循環連結リストは、単方向連結か双方向連結かに応じて、どちらかの関数を持つことができます。

# イテレータの移動先の NextNode がある場合は、そのノードに移動します
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# イテレータの移動先の PreviousNode がある場合は、そのノードに移動します
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

ノードを追加する

イテレータを使用して、連結リストの特定の場所にノードを追加できます。ノードを追加する場合、ノードをどこに追加するかを選択することが重要です。ノードを現在のノードの前または後に追加することもできますが、これはリストの構造応じて異なります。単方向連結リストでは、参照する Previous ノードへの参照がないため、他のノードの後にしかノードを追加できません。双方向連結リストでは、他のノードの前または後にノードを追加できます。

# CurrentNode の後に新しいノードを追加する
AddNextNode(NewNode:list_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

この AddNode 関数は、CurrentNode とその後ろのノードの間にノードを追加します。これは、次を行うことで実行されます。

CurrentNode の Next の参照を NewNode に設定します。
NewNode の Next の参照を NextNode に設定します。NextNode がない場合 (リストの末尾など)、関数は次のノードとして NewNode を設定するだけです。

In a doubly linked list, you have the option of adding nodes before or after CurrentNode. You can split this functionality into two functions, AddNodeAfter() and AddNodeBefore(). The implementation is very similar to the one in the singly linked list, except that you have to remember to set the Previous reference for each node as well.

# CurrentNode の後に新しいノードを追加する
AddNodeAfter(NewNode:doubly_linked_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set NewNode.Previous = option{CurrentNode}
        set CurrentNode.Next = option{NewNode}
        set NextNode.Previous = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# CurrentNode の前に新しいノードを追加する
AddNodeBefore(NewNode:doubly_linked_node):void=
    if(PreviousNode := CurrentNode.Previous?):
        set NewNode.Next = option{CurrentNode}
        set NewNode.Previous = option{PreviousNode}
        set CurrentNode.Previous = option{NewNode}
        set PreviousNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set NewNode.Next = option{CurrentNode}
        set CurrentNode.Previous = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# CurrentNode の後に新しいノードを追加する
AddNodeAfter(NewNode:doubly_linked_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set NewNode.Previous = option{CurrentNode}
        set CurrentNode.Next = option{NewNode}
        set NextNode.Previous = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

# CurrentNode の前に新しいノードを追加する
AddNodeBefore(NewNode:doubly_linked_node):void=
    if(PreviousNode := CurrentNode.Previous?):
        set NewNode.Next = option{CurrentNode}
        set NewNode.Previous = option{PreviousNode}
        set CurrentNode.Previous = option{NewNode}
        set PreviousNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set NewNode.Next = option{CurrentNode}
        set CurrentNode.Previous = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

ノードを削除する

ノードを削除するには、リストの順序を保持しながら、そのノードへの参照をすべて削除する必要があります。そのためには、削除したいノードの後ろにノードがある場合、削除したノードの前にあるノードを、そのノードの後ろにあるノードに連結する必要があります。単方向連結リストでは、Previous への参照がないため CurrentNode の後のノードしか削除できません。

# CurrentNode の後ろにある次のノードを削除します。次のノードに
# Next への参照がある場合は、そのノードを CurrentNode の次のノードに設定します。
RemoveNextNode():void=
    if(RemovedNode := CurrentNode.Next?):
        if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
            set CurrentNode.Next = option{NodeAfter}
            Print("Removed the node between CurrentNode and the node after it")
            # 削除されたノードが先頭ノードである場合は、次のノードを新しい先頭として設定します
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
        else:
            set CurrentNode.Next = false
            Print("Removed the node before CurrentNode")
    else:
        Print("Couldn't remove the node")

なお、次の特殊な状況でのみ、先頭ノードを削除することができます。この状況では、先頭ノードの後のノードを新しい先頭に設定する必要があります。これを行わない場合、連結リストを開始する場所がなくなります。

ノードの追加と同様に、双方向連結リストのノードの削除は、現在のノードの前のノードの削除と後のノードの削除に分けることができます。

# CurrentNode の後のノードを削除する
RemoveNodeAfter():void=
    if(RemovedNode := CurrentNode.Next?):
        if:
            NodeAfter := RemovedNode.Next?
            set RemovedNode.Next = false
            set RemovedNode.Previous = false
            set NodeAfter.Previous = option{CurrentNode}
            set CurrentNode.Next = option{NodeAfter}
        then:
            Print("Removed the node between CurrentNode and the node after it")
            # 削除されたノードが先頭ノードである場合は、次のノードを新しい先頭として設定します
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
                # ダミー ノードまでトラバースして戻らないようにしたい場合は、
                # 新しい先頭の Previous を false に設定します
                set NodeAfter.Previous = false       
        else:
            set CurrentNode.Next = false
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")   

# CurrentNode の前のノードを削除します。
RemoveNodeBefore():void=
    if(RemovedNode := CurrentNode.Previous?):
        if:
            NodeBefore := RemovedNode.Previous?
            set RemovedNode.Previous = false
            set CurrentNode.Previous = option{NodeBefore}
            set NodeBefore.Next = option{CurrentNode}
        then:
            Print("Removed the node between CurrentNode and the node before it")
            # 削除されたノードが先頭ノードである場合は、次のノードを新しい先頭として設定します
        else:
            set CurrentNode.Previous = false
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = CurrentNode
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

# CurrentNode の後のノードを削除する
RemoveNodeAfter():void=
    if(RemovedNode := CurrentNode.Next?):
        if:
            NodeAfter := RemovedNode.Next?
            set RemovedNode.Next = false
            set RemovedNode.Previous = false
            set NodeAfter.Previous = option{CurrentNode}
            set CurrentNode.Next = option{NodeAfter}
        then:
            Print("Removed the node between CurrentNode and the node after it")
            # 削除されたノードが先頭ノードである場合は、次のノードを新しい先頭として設定します
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = NodeAfter
                # ダミー ノードまでトラバースして戻らないようにしたい場合は、
                # 新しい先頭の Previous を false に設定します
                set NodeAfter.Previous = false       
        else:
            set CurrentNode.Next = false
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

# CurrentNode の前のノードを削除します。
RemoveNodeBefore():void=
    if(RemovedNode := CurrentNode.Previous?):
        if:
            NodeBefore := RemovedNode.Previous?
            set RemovedNode.Previous = false
            set CurrentNode.Previous = option{NodeBefore}
            set NodeBefore.Next = option{CurrentNode}
        then:
            Print("Removed the node between CurrentNode and the node before it")
            # 削除されたノードが先頭ノードである場合は、次のノードを新しい先頭として設定します
        else:
            set CurrentNode.Previous = false
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")
                set List.Head = CurrentNode
            Print("Removed the node after CurrentNode")
    else:
        Print("Couldn't remove the node")

応用編

連結リストを拡張する方法は複数あります。そのため、機能を追加するさまざまな方法を検討する必要があります。以下に、連結リストを拡張する方法をいくつか挙げます。

各リストに末尾ノードへの参照も格納するとどうなるでしょうか？
ノードの内容を出力する ToString() メソッドを実装できるでしょうか？
リストを反転させるのはどうでしょうか？Length() 機能を実装できるでしょうか？
イテレータにさらにメソッドを追加して、新しい操作を実行することはできるでしょうか？