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

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

概要

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

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

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

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

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

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

Verse での実装

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

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

Verse

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

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

Verse

Node1 := list_node{ Next := false, Data := 1 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

Node1 := list_node{ Next := false, Data := 1 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

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

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

Verse

# A container node that contains integer data and a reference
# to the next node in the list.
list_node_int := class(list_node):
    # Reference to the next node in the list.
    var Next<override>:?list_node = false
    Data<override>:int

# A container node that contains string data and a reference
# to the next node in the list.
list_node_string := class(list_node):

単方向連結リスト

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

Verse

# Link each Node to the next Node in the list
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

# Link each Node to the next Node in the list
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

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

Verse

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

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

Verse

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

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

Verse

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node
        Print("Starting at the Head Node...")
        # If the current node has a next node, set the current node to
        # the next node in the list

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

双方向連結リスト

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

Verse

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

単独でリンクされたノードの場合と同様に、特定のデータタイプのみを処理するより具体的な実装が必要な場合は、必ず Data 型をそれに合わせて変更してください

Verse

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

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

Verse

# A data structure that links multiple list_node structures together to create a chain. 
# Uses doubly linked nodes which contain references to both the next and previous nodes.
doubly_linked_list := class():
    var Head:doubly_linked_node

    # Traverse a LinkedList, but both backward and forward!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")

循環連結リスト

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

イテレータ

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

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

Verse

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

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

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

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

Verse

linked_list_iterator := class:
    List:linked_list
    # The below line will fail because you can't access List from this scope
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

linked_list_iterator := class:
    List:linked_list
    # The below line will fail because you can't access List from this scope
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

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

Verse

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

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

Verse

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

ノード間でのイテレート

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

Verse

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

ノードを追加する

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

Verse

# Adds a new node after 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!")

# Adds a new node after 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 参照を NewNode に設定します。 NextNode がない場合 (リストの末尾など)、関数は次のノードとして NewNode を設定するだけです。

双方向連結リストでは、CurrentNode の前後にノードを追加することができます。この機能は、AddNodeAfter() と AddNodeBefore() の 2 つの関数に分割することができます。実装は、各ノードの Previous への参照も忘れずに設定する必要がある点を除けば、単方向連結リストの実装と非常に似ています。

Verse

# Adds a new node after 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}

ノードを削除する

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

Verse

# Remove the next node after CurrentNode. If the next node
# has a Next reference, set that node to the next node of 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 the removed node is the Head node, set the next node as the new Head.
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")

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

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

Verse

# Remove the node after 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:

完全なコード

以下は、この例の各クラスの完全なコードです。

list_node

Verse

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    # Reference to the next node in the list.
    var Next:?list_node = false
    Data:any = {}


# A container node that contains integer data and a reference
# to the next node in the list.

linked_list

Verse

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.
linked_list := class:
    # The first node in the list.
    var Head:list_node
 
    # Traverses the linked list forward starting from the CurrentNode.
    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node.

linked_list_iterator

Verse

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node.
    Next()<transacts><decides>:list_node=
        NextNode := CurrentNode.Next?
        set CurrentNode = NextNode

応用編

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

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