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

 

목차

---

자료구조

연결 리스트(Linked List)

: 데이터 요소들을 순차적으로 연결한 자료구조

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성
• 메모리 상에서 연속적이지 않은 위치에 저장 가능

구조

• Node : 데이터를 저장하는 기본 단위
• Data : 실제 저장되는 정보
• Next : 다음 노드를 가리키는 포인터(참조)
• null : 리스트의 끝을 나타냄

종류

1. 단일 연결 리스트(Singly Linked List) : 각 노드가 다음 노드만을 가리킴
2. 이중 연결 리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 모두 가리킴
3. 원형 연결 리스트(Circular Linked List) : 마지막 노드가 첫 번째 노드를 가리켜 원형을 이룸

장점

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

단점

• 임의 접근의 비효율성 : 특정 위치 접근에 O(n) 시간 복잡도 --> Random Access 불가능
• 추가 메모리 사용 : 포인터 저장을 위한 추가 메모리 필요
• 캐시 비효율 : 메모리상 연속적이지 않아 캐시 활용도가 낮음
• 역방향 탐색 어려움 (단일 연결 리스트의 경우)

※ 임의 접근(Random Access)

: 무작위로 뽑아서 출력하는 것을 의미하는 것이 아니라 임의의 Index를 뽑고자 할 때, Access가 즉시 가능하느냐의 의미

Linked List 사용해보기

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ListExample : MonoBehaviour
{
    void Start()
    {
        // C#에서 제공하는 Linkedlist 체험하기
	LinkedList<int> list = new LinkedList<int>();
        list.AddLast(1); // list의 tail에 1을 추가
        list.AddLast(2);
        list.AddLast(3);
        list.AddLast(4);
        list.AddFirst(0); // list의 head에 0을 추가

        var enumerator = list.GetEnumerator();

        int findIndex = 3;
        int currentIndex = 0;

        while (enumerator.MoveNext())
        {
            if (currentIndex == findIndex)
            {
                Debug.Log(enumerator.Current);
                break;
            }
            currentIndex++;
        }
    }
}

 

열거자 (Enumerator)

: 컬렉션을 순회할 때 사용되며, 컬렉션의 각 요소에 순차적으로 접근하는 방법을 제공한다.

 

※ MoveNext() : 순회할 수 있는 데이터를 가져오는 메소드 --> 첫 Index부터 가져옴

 

Linked List 구현해보기

Generic

: 다양한 데이터 형식을 처리하는 메서드와 클래스를 작성할 수 있게 한다.

※ T말고 다른 알파벳을 써도 되지만, 주로 T를 사용한다 / T1, T2 이런 식으로 더 추가도 가능하다.

Singly Linked List

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

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 LinkedListCustom<T>
{
    public Node<T> Head { get; private set; }

    public void AddLast(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 AddFirst(T data)
    {
        Node<T> newNode = new Node<T>(data);
        
        if (Head == null)
            Head = newNode;
        else
        {
            newNode.Next = Head;
            Head = newNode;
        }
    }
    
    public void AddIndex(T data, int index)
    {
        Node<T> newNode = new Node<T>(data);
        Node<T> current = Head;
        
        if (index < 0)
        {
            Debug.Log("Index Error");
            return;
        }
        else if (index == 0)
            AddFirst(data);

        if (Head == null)
            Head = newNode;
        else
        {
            for (int i = 0; i < index - 1; i++)
            {
                if (current == null) // index가 크기보다 클 때
                {
                    Debug.Log("Index가 크기보다 큽니다.");
                    return;
                }
                current = current.Next;
            }

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

public class ListExample : MonoBehaviour
{
    void Start()
    {
        LinkedListCustom<int> listCustom = new LinkedListCustom<int>();
        listCustom.AddLast(1);
        listCustom.AddLast(2);
        listCustom.AddLast(3);
        listCustom.AddLast(4);
        listCustom.AddIndex(7, 2);
        
        listCustom.Traverse();
    }
}

 

Doubly Linked List

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

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

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

public class DLinkedListCustom<T>
{
    public DNode<T> Head { get; private set; }
    public DNode<T> Tail { get; private set; }
    
    public void AddLast(T data)
    {
        DNode<T> newNode = new DNode<T>(data);
        if (Head == null)
        {
            Head = 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 = Tail = newNode;
        }
        else
        {
            Head.Prev = newNode;
            newNode.Next = Head;
            Head = newNode;
        }
    }

    public void AddIndex(T data, int index)
    {
        DNode<T> newNode = new DNode<T>(data);
        DNode<T> current = Head;
        
        if (index < 0)
        {
            Debug.Log("Index Error");
            return;
        }
        else if (Head == null || index == 0)
            AddFirst(data);

        for (int i = 0; i < index; i++)
        {
            if (current.Next == null) // index가 크기보다 클 때
            {
                Debug.Log("Index가 크기보다 큽니다.");
                return;
            }
            current = current.Next;
        }

        current.Prev.Next = newNode;
        newNode.Next = current;
        newNode.Prev = current.Prev;
        current.Prev = newNode;
    }

    public DNode<T> Search(T data)
    {
        DNode<T> current = Head;
        DNode<T> findData = null;
        int index = 0;
        while (current != null)
        {
            if (data.Equals(current.Data))
            {
                findData = current;
                Debug.Log($"{data}은/는 index : {index}번째에 있습니다.");
                break;
            }
            current = current.Next;
            index++;
        }
        return findData;
    }

    public void Delete(T data)
    {
        DNode<T> current = Search(data);
        if (current != null)
        {
            DNode<T> prevNode = current.Prev;
            DNode<T> nextNode = current.Next;

            prevNode.Next = nextNode;
            nextNode.Prev = prevNode;
        }
    }
    
    public void Traverse()
    {
        DNode<T> current = Head;
        while (current != null)
        {
            Debug.Log(current.Data);
            current = current.Next;
        }
    }
    
    public void RTraverse()
    {
        DNode<T> current = Tail;
        while (current != null)
        {
            Debug.Log(current.Data);
            current = current.Prev;
        }
    }
}

public class ListExample : MonoBehaviour
{
    void Start()
    {
        DLinkedListCustom<int> dlistCustom = new DLinkedListCustom<int>();
        dlistCustom.AddLast(10);
        dlistCustom.AddLast(20);
        dlistCustom.AddLast(30);
        dlistCustom.AddLast(40);
        dlistCustom.AddIndex(70, 2);

        dlistCustom.Search(30);
        
        dlistCustom.Traverse();
        
        dlistCustom.Delete(70);
        dlistCustom.Traverse();
    }
}

전체 코드

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

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

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

public class DLinkedListCustom<T>
{
    public DNode<T> Head { get; private set; }
    public DNode<T> Tail { get; private set; }
    
    public void AddLast(T data)
    {
        DNode<T> newNode = new DNode<T>(data);
        if (Head == null)
        {
            Head = 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 = Tail = newNode;
        }
        else
        {
            Head.Prev = newNode;
            newNode.Next = Head;
            Head = newNode;
        }
    }

    public void AddIndex(T data, int index)
    {
        DNode<T> newNode = new DNode<T>(data);
        DNode<T> current = Head;
        
        if (index < 0)
        {
            Debug.Log("Index Error");
            return;
        }
        else if (Head == null || index == 0)
            AddFirst(data);

        for (int i = 0; i < index; i++)
        {
            if (current.Next == null) // index가 크기보다 클 때
            {
                Debug.Log("Index가 크기보다 큽니다.");
                return;
            }
            current = current.Next;
        }

        current.Prev.Next = newNode;
        newNode.Next = current;
        newNode.Prev = current.Prev;
        current.Prev = newNode;
    }

    public DNode<T> Search(T data)
    {
        DNode<T> current = Head;
        DNode<T> findData = null;
        int index = 0;
        while (current != null)
        {
            if (data.Equals(current.Data))
            {
                findData = current;
                Debug.Log($"{data}은/는 index : {index}번째에 있습니다.");
                break;
            }
            current = current.Next;
            index++;
        }
        return findData;
    }

    public void Delete(T data)
    {
        DNode<T> current = Search(data);
        if (current != null)
        {
            DNode<T> prevNode = current.Prev;
            DNode<T> nextNode = current.Next;

            prevNode.Next = nextNode;
            nextNode.Prev = prevNode;
        }
    }
    
    public void Traverse()
    {
        DNode<T> current = Head;
        while (current != null)
        {
            Debug.Log(current.Data);
            current = current.Next;
        }
    }
    
    public void RTraverse()
    {
        DNode<T> current = Tail;
        while (current != null)
        {
            Debug.Log(current.Data);
            current = current.Prev;
        }
    }
}

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 LinkedListCustom<T>
{
    public Node<T> Head { get; private set; }

    public void AddLast(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 AddFirst(T data)
    {
        Node<T> newNode = new Node<T>(data);
        
        if (Head == null)
            Head = newNode;
        else
        {
            newNode.Next = Head;
            Head = newNode;
        }
    }
    
    public void AddIndex(T data, int index)
    {
        Node<T> newNode = new Node<T>(data);
        Node<T> current = Head;
        
        if (index < 0)
        {
            Debug.Log("Index Error");
            return;
        }
        else if (index == 0)
            AddFirst(data);

        if (Head == null)
            Head = newNode;
        else
        {
            for (int i = 0; i < index - 1; i++)
            {
                if (current == null) // index가 크기보다 클 때
                {
                    Debug.Log("Index가 크기보다 큽니다.");
                    return;
                }
                current = current.Next;
            }

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

public class ListExample : MonoBehaviour
{
    void Start()
    {
        //LinkedListCustom<int> listCustom = new LinkedListCustom<int>();
        //listCustom.AddLast(1);
        //listCustom.AddLast(2);
        //listCustom.AddLast(3);
        //listCustom.AddLast(4);
        //listCustom.AddIndex(7, 2);
        //
        //listCustom.Traverse();
        
        DLinkedListCustom<int> dlistCustom = new DLinkedListCustom<int>();
        dlistCustom.AddLast(10);
        dlistCustom.AddLast(20);
        dlistCustom.AddLast(30);
        dlistCustom.AddLast(40);
        dlistCustom.AddIndex(70, 2);

        dlistCustom.Search(30);
        
        dlistCustom.Traverse();
        
        dlistCustom.Delete(70);
        dlistCustom.Traverse();
    }
}

 

※ 숙련자를 위한 과제

: List가 외부에서 이터레이션 할 수 있는 코드 작성