Verse의 연결된 목록 | Fortnite 문서

연결된 목록은 컴퓨터 공학에서 흔히 사용되는 데이터 구조입니다. 연결된 목록은 음악 플레이리스트를 만들거나 작업의 히스토리를 추적하는 등의 용도로 사용할 수 있습니다.

개요

연결된 목록은 목록에서 각 엘리먼트가 다음 엘리먼트에 대한 레퍼런스를 저장하는 단방향 데이터 구조입니다. 연결된 목록의 각 엘리먼트는 노드(node)라고 합니다. 노드는 일부 데이터와 다음 노드에 대한 레퍼런스를 저장하는 컨테이너입니다.

서로 다른 노드를 시퀀스에서 연결하면 연결된 목록이 생성됩니다. 목록의 첫 번째 노드는 헤드(head) 노드가 되며, 마지막 노드는 테일(tail) 노드가 됩니다. 목록을 따라 이동하기 위해서는 먼저 헤드에서 시작하여 각 노드의 레퍼런스를 사용하여 다음 엘리먼트로 이동하게 됩니다.

사용해야 하는 경우

연결된 목록은 스택 또는 큐와 같은 다른 데이터 구조를 구현하는 데 좋은 시작점 역할을 합니다. 연결된 목록은 순차적 액세스를 위해 데이터를 저장하는 직관적인 방법으로, 새로운 엘리먼트를 빠르게 삽입할 수 있도록 지원합니다. 연결된 목록은 배열과 달리 메모리에서 인접해 있지 않습니다. 즉, 노드는 메모리의 어디에나 있을 수 있으며 다음 노드에 대한 레퍼런스를 통해 위치를 알 수 있습니다. 연결된 목록에서 노드를 삽입하거나 삭제하려면 다음에 오는 노드에 대한 레퍼런스를 변경하기만 하면 됩니다.

사용하지 않아야 하는 경우

목록에서 랜덤 플레이어를 선택해야 하는 경우와 같이 프로그램에서 엘리먼트에 랜덤으로 액세스해야 하는 경우에는 연결된 목록을 통해 이러한 함수 기능을 구현하기에는 적합하지 않습니다. 연결된 목록은 목록 중간에 있는 특정 노드에 액세스해야 하는 경우 일단 헤드부터 해당 노드까지 이동해야 하므로 배열보다 효율성이 떨어집니다.

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를 comparable로 만듭니다. 이를 통해 노드가 다른 노드와 동일한지, 즉 노드가 목록의 헤드인지 또는 테일인지 등을 확인할 수 있습니다.

숫자 또는 스트링만 처리하는 노드처럼 보다 구체적으로 구현해야 하는 경우에는 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

노드 간에 반복작업하기

목록의 연결에 따라 이터레이터를 앞뒤로 이동할 수도 있습니다. 단방향으로 연결된 목록의 이터레이터는 앞으로만 이동할 수 있지만, 양방향으로 연결된 목록의 이터레이터는 양방향으로 이동할 수 있습니다. 이 같은 함수 기능은 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 레퍼런스를 NextNode에 설정합니다. 목록의 테일인 경우에서와 같이 NextNode가 없는 경우 이 함수는 NewNode를 다음 노드로만 설정합니다.

양방향으로 연결된 목록에서는 CurrentNode의 노드 앞뒤에 노드를 추가할 수 있습니다. 이 함수 기능은 AddNodeAfter()와 AddNodeBefore()라는 두 함수로 분리할 수 있습니다. 그 구현은 단방향으로 연결된 목록에서와 매우 유사한데, 각 노드에 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() 함수 기능을 구현할 수 있을까요?
이터레이터에 메서드를 더 추가하여 새로운 연산을 수행할 수 있을까요?