TIL

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

Cadi 2024. 12. 3. 21:50

 

 

링크드 리스트

Linked list

기본 개념

 

Linked List

  • 데이터들을 순차적으로 연결한 '자료구조'
  • 각 노드(node)는 데이터와 다음 노드를 가리키는 포인터로 구성
  • 메모리 상에서 연속적이지 않은 위치에 저장 가능

  • Node : 데이터 저장의 기본 단위
  • Data  : 실제 저장되는 정보
  • Next  : 다른 노드를 가르키는 포인터(참조)
  • Null   : 리스트의 끝

 

리스트의 종류

  1. 단일 연결 리스트 (Singly Linked List)
  2. 이중 연결 리스트 (Doubly Linked List)
  3. 원형 연결 리스트 (Circular Linked List)

장점 

  • 동적 크기 : 배열과 달리 필요에 따라 크기 조절 가능
  • 삽입/삭제의 효율성 : 포인터 변경만 하면 됨, O(1)의 시간 복잡도
  • 메모리 효율 : 필요한 만큼만 메모리 사용
  • 데이터 재구성 용이 : 노드의 연결만 변경하여 쉽게 재구성 가능

단점

  • 비효율 : 특정 위치 접근시 O(n) 시간 복잡도
  • 추가 메모리 : 포인터 저장을 위한 추가 메모리 필요
  • 캐시 비효율 : 메모리상 연속적이지 않아 캐시 활용도가 낮음 ( 무슨 말인지 찾아보기)
  • 단일 리스트의 경우, 역방향 탐색이 어려움

시간 복잡도

  • O(n) : 접근,검색,중간 삽입, 중간/뒤 삭제 (뒤 삭제는 왜 ?)

Linked List 구현

 

 그림을 생각하며 클래스를 만든다. 

public class Node<T>
{
    public T Data;
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

Node<T> 라는 클래스는 Generic Linked list를 만들기 위한 과정이다.

Generic Linked List는 변수에 상관없이 사용할 수 있다. 

우선 T라는 모든 변수를 집어넣을 수 있는 것에 Data라는 변수를 생성한다.

또한 Node<T>라는 T 데이터를 가진 Node에 Next 라는 변수(프로퍼티) 를 생성한다.

그리고 생성자인 public Node (T data) 를 만들고 각각의 변수에 기본 데이터를 할당한다.

 

이 과정으로써 우리는 단일 연결 리스트를 만들기 위한 노드를 생성할 수 있게 되었다.

이 노드는 T 라는 데이터와 Next라는 포인터(다른 노드로 향하는)를 갖는 노드이다. 

 

이제 우리는, Node를 추가할 것이다. 맨 뒤쪽에 계속해서 새로운 노드들을 추가하고, 존재했던 노드로부터 포인터를 연결할 것이다. 

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

        public void Add(T data)
        {
            Node<T> newNode = new Node<T>(data);
            if (Head == null)
            {
                Head = newNode;
            }
            else
            {
                Node<T> current = Head;
                while (current.Next != null)
                {
                    current = current.Next;
                }

                current.Next = newNode;
            }
        }
        public void Traverse()
        {
            Node<T> current = Head;
            while (current != null)
            {
                Debug.Log(current.Data);
                current = current.Next;
            }
        
        }
    }

밑의 Traverse 함수는, 하나씩 노드들을 거쳐 이동하면서 노드의 데이터들을 읽는 함수이다. 

 

함수가 잘 작성되었는지 확인하기 위해서 Start 함수에 넣어서 확인해본다. 

이를 실행하면 다음과 같이 나온다. 

올바르게 나온 것을 확인할 수 있다.

 

Doubly LInked List

이제는 이중 연결 리스트를 만들어 볼 것이다. (양방향이다)

public class DNode<T>
{
    public T Data;
    public DNode<T> Next;
    public DNode<T> Prev;

    public DNode(T data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

 

마찬가지로 DNode<T> Class를 만들고, 여기에는 T data, Next와 Prev의 참조가 있다.

생성자를 생성해주고 기본값들을 할당해 주었다. 

 

이제는 노드의 끝부분에 새로운 노드를 추가하는 코드(AddLast)

            노드의 시작부분에 새로운 노르를 추가하는 코드(AddFirst)

            노드의 중간에 새로운 노드를 추가하는 코드(Inset)

            n번의 노드를 선택하는 코드 (Get)

마지막으로 순차적으로 노드를 돌며 데이터를 출력하는 코드  (Traverse)를 생성한다.

public class DLinkedListCustom<T>
    {
        public DNode<T> head;
        public DNode<T> tail;

        public void AddLast(T data)
        {
            DNode<T> newNode = new DNode<T>(data);
            if (tail == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
                tail.Next = newNode;
                newNode.Prev = tail;
                tail = newNode;
            }
        }

        public void AddFirst(T data)
        {
            DNode<T> newNode = new DNode<T>(data);
            if (head == null)
            {
                head = newNode;
                tail = newNode;
            }
            else
            {
              head.Prev = newNode;
              newNode.Next = head;
              head = newNode;
            }
        }

        public void Traverse()
        {
            DNode<T> current = head;
            while (current != null)
            {
                Debug.Log(current.Data);
                current = current.Next;
                
            }
        }

        public DNode<T> Get(int index)
        {
            DNode<T> current = head;
            for (int i = 0; i < index; i++)
            {
                current = current.Next;
            }

            return current;
        }
        public void Insert(T data, int index)
        {
            DNode<T> newNode = new DNode<T>(data);
            var oldNode = Get(index);

            newNode.Next = oldNode.Prev.Next;
            oldNode.Prev.Next = newNode;
            newNode.Prev = oldNode.Prev;
            oldNode.Prev = newNode;
            
        }
        
    }

 

중간에 삽입하는 코드는 예외 사항은 일단 제외하였다. 

만일 추가한다면

  • 노드가 아무것도 존재하지 않을 때
  • index를 음수로 넣었을 때
  • index를 0으로 넣었을 때
  • index가 너무 클 때
  • index가 node의 갯수만큼일 때 (삽입이 아니라 마지막에 추가하는 것)

정도가 있을 수 있겠으나 생략하였다. 

Get 함수는 insert나 여기서는 쓰지 않았지만 n번째 노드를 삭제하기 위한 코드에서 편하게 이용하려고 만들었다.

 

이제 start 함수로 잘 작동하는지 체크해보자. 

 void Start()
    {
        DNode<int>.DLinkedListCustom<int> list = new DNode<int>.DLinkedListCustom<int>();

        list.AddFirst(1);
        list.AddFirst(2);
        list.AddFirst(3);
        list.AddFirst(4); 
        list.Insert(3 ,3);
        list.Traverse();

        
    }

 

결과는 다음과 같다.

 

올바르게 나왔다. 

 

중간중간 무한 루프에 빠지기도 하고, Rename 기능 알아본다고 설치다가 처음부터 다시 작성하기도 하면서 어느정도 이해한 것 같다. 틀린 내용 있으면 보시는 분들 중 언제나 어디서든 지적 환영입니다  ! 

 

추가로, 잘 작동되고 있는지 검수를 꼼꼼하게 하기 위해 다음과 같은 코드를 사용해 볼 수도 있다.

private void _Logging(DNode<T> node)
        {
            string prevValue = "null";
            string nextValue = "null";
            if (node.Prev != null) prevValue = $"{node.Prev.Data}";
            if (node.Next != null) nextValue = $"{node.Next.Data}";

            Debug.Log($"현재값: {node.Data} / Prev: {prevValue}/ Next: {nextValue}");
        }

 

* if 문이 단일문일때는 {}를 생략할 수도 있다.