[멋쟁이사자처럼 부트캠프 TIL 회고] 유니티 게임 개발 3기 11일차

namespace UnityGameDevelopment.Day11 {
    public class Outline {
    	public static string Chapter1 = "링크드 리스트";
    }
}

 

 

1. 링크드 리스트

데이터를 가진 노드를 순서대로 엮어 사용하는 링크드 리스트에 대해 배워봅니다.

 

자료형의 이름은 링크드 리스트(LinkedList)이고 리스트의 요소 하나를 노드(Node)라고 합니다.

 

public class Node<T>
{
    public T Data { get; set; }
    public Node<T> Next { get; set; }
    
    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

 

노드는 특정 데이터를 담을 수 있고, 이는 제네릭을 사용해서 노드가 담을 수 있는 데이터의 타입을 일반화합니다.

 

public class LinkedList<T>
{
    public Node<T> Head { get; private set; }
}

 

링크드 리스트는 첫 노드를 가리키는 Head라는 변수(여기서는 프로퍼티를 사용) 를 가지고 있습니다. 링크드 리스트에 연결된 다른 노드들은 Head로부터 접근합니다.

 

아래는 링크드 리스트의 기본 기능을 나열합니다.

• 요소 추가하기
• 요소 제거하기
• 요소 구하기

요소 추가하기

요소를 추가하려면 파라미터로 데이터를 하나 받아서 노드로 감싸주고 이 노드를 리스트에 연결합니다.

public void AddFirst(T data)
{
    Node<T> newNode = new Node<T>(data);

    newNode.Next = Head;
    Head = newNode;
}

 

맨 앞에 요소를 추가하는 함수를 리스트 멤버 함수로 작성하였습니다. 새로 생성된 노드는 첫 노드를 가리키게 되며, Head가 새로 생성된 노드를 가리키도록 하여 맨 앞에 데이터를 추가합니다.

 

public void AddLast(T data)
{
    Node<T> newNode = new Node<T>(data);

    if (Head == null)
    {
        Head = newNode;
    }
    else
    {
        Node<T> node = Head;

        while (node.Next != null)
        {
            node = node.Next;
        }

        node.Next = newNode;
    }
}

 

맨 뒤에 요소를 추가하는 함수는 Head에 아무것도 없으면 바로 가리키게 하고, 있으면 마지막 노드까지 간 다음에 마지막노드의 다음 노드로 새로 생성된 노드를 가리키게 만들어줍니다.

 

요소 제거하기

public void RemoveFirst()
{
    if (Head == null) { return; }

    Head = Head.Next;
}

 

맨 앞 요소를 제거하려면 처음 노드는 Head가 가리키는 대상의 다음을 가리켜 제거합니다.

 

public void RemoveLast()
{
    if (Head == null) { return; }

    Node<T> node = Head;

    if (node.Next == null)
    {
        Head = null;
    }
    else
    {
        while (node.Next.Next != null)
        {
            node = node.Next;
        }

        node.Next = null;
    }
}

 

마지막 노드의 제거는 노드가 없을 때, 노드가 하나일 때, 그 외 상황에 따라 다르게 동작하도록 만듭니다. 노드가 없을 때는 무시합니다. 노드가 하나 있을 때는 Head가 가리키는 대상을 null로 변경합니다. 그 외 노드가 여러 개일 때는 마지막까지 이동 후 노드의 다음 노드를 null로 변경합니다.

 

요소 구하기

N번째 요소를 구하기 위해 index 값을 파라미터로 받습니다. 그리고 반환값의 자료형은 T로 설정합니다.

public T Get(int index)
{
    Node<T> node = Head;

    for (int i = 0; i < index; i++)
    {
        node = node.Next;
    }

    return node.Data;
}

 

순회하는 노드 변수를 만들어주고 Head가 가리키는 노드로 초기화해줍니다. 이를 index 값만큼 진행시켜줍니다. 그 결과로 나온 노드의 값을 반환합니다.

실습 및 응용

▶ 값으로 요소 찾기

▶ 리스트 역순으로 바꾸기