Unity Doubly Linked List

🔷링크드 리스트란?

연결 리스트(Linked List)란 유연하게 크기 변경이 가능한 자료구조를 말한다. 데이터를 자유롭게 넣고 빼고 할수 있다는 장점이 있고, 집합의 단위를 리스트(List), 각 요소의 단위를 노드(Node)라고 한다.

단순 연결 리스트(Singly Linked List)는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없다. 이러한 단점을 해결하기 위해 노드에 앞 노드의 메모리 주소를 보관하는 포인터 prev를 만들어준 형태인 이중 연결 리스트(Doubly Linked List)를 만들어 보았다.

🔷 1. 노드를 작성해준다.

public class MyNode<T> where T : class
{
    public T value;
    public MyNode<T> nextNode;
    public MyNode<T> prevNode;
}

먼저 value ,
다음노드를 가르키는 nextNode
이전 노드를 가르키는 prevNode
클래스를 만들어 준다

🔷2. 이중 연결 리스트를 사용할 클래스를 만들어준다.

public class MyLinkedList<T> where T : class
{
    public MyNode<T> head; 
    public MyNode<T> tail;
    public uint length = 0;

    public MyLinkedList()
    {
        head = new MyNode<T>()
        {
            value = null
        };

        tail = new MyNode<T>()
        {
            value = null
        };

        head.prevNode = null;
        head.nextNode = tail;

        tail.prevNode = head;
        tail.nextNode = null;
    }

    public bool IsEmpty()
    {
        return (length == 0);
    }

    public void Print()
    {
        MyNode<T> searchNode = head;
        while (searchNode.nextNode != tail)
        {
            Debug.Log(searchNode.nextNode.value);
            searchNode = searchNode.nextNode;
        }
    }

    public void Add(T _value)
    {
        MyNode<T> newNode = new MyNode<T>
        {
            value = _value
        };

        if (IsEmpty())
        {
            head.nextNode = newNode;
            newNode.prevNode = head;
            newNode.nextNode = tail;
            tail.prevNode = newNode;
            Debug.Log(_value + "를 처음으로 가방에 넣었습니다.");
        }

        else
        {
            MyNode<T> searchNode = head;
            while (searchNode.nextNode != tail)
            {
                searchNode = searchNode.nextNode;
            }
            searchNode.nextNode.prevNode = newNode;
            newNode.nextNode = searchNode.nextNode;
            newNode.prevNode = searchNode;
            searchNode.nextNode = newNode;
            Debug.Log(_value + "를 가방에 넣었습니다.");
        }
        ++length;
    }

    public void Remove(T _value)
    {
        MyNode<T> searchNode = head;

        while (searchNode != tail)
        {
            if (searchNode.value == _value)
            {
                searchNode.nextNode.prevNode = searchNode.prevNode;
                searchNode.prevNode.nextNode = searchNode.nextNode;
                Debug.Log( _value + "를 뺏습니다.");

                --length;
                return;
            }
            searchNode = searchNode.nextNode;
        }
        Debug.Log("뺄 " + _value + "가 없습니다.");
    }
    public bool Constrain(T _value)
    {
        MyNode<T> searchNode = head;

        while (searchNode.nextNode != tail)
        {
            if (searchNode.value == _value)
            {
                return true;
            }
        }
        return false;
    }
}

🔷 더블 링크드 리스트를 작성후 아래와 같이 입력을 할수있게 만들어준다.

예제는 가방에 고구마와 감자를 넣고 빼고 할수있게 작성을 해보았다.
Add로 넣고 , Remove로 빼고 , Print 정보를 보여준다.

{
    MyLinkedList<string> linkedList = new MyLinkedList<string>();
   
    private void Update()
    {
        if(Input.GetKeyDown(KeyCode.Q))
        {
            linkedList.Add("감자");             
        }
        if (Input.GetKeyDown(KeyCode.W))
        {
            linkedList.Add("고구마");
        }
        if (Input.GetKeyDown(KeyCode.E))
        {
            linkedList.Print();
        }
        if (Input.GetKeyDown(KeyCode.R))
        {
            linkedList.Remove("감자");
        }
    }
}

Q 입력시 감자가 들어갈 수 있도록, W 입력시 고구마가 들어갈 수 있도록
E는 이제 가방에 정보를 볼수있게 , R은 가방에 감자를 뺄수 있도록 구현을 했다. QWER로 가방에 넣고 빼고를 할수있게 만들어졌다.