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

 

 

11일차 요약

링크드 리스트(Linked List)

• 데이터 요소를 순차적으로 연결한 자료구조
• 장점
  • 삽입, 삭제에 용이
    • 맨 앞/뒤: O(1), 중간: O(n)
  • 동적 크기
• 단점
  • 접근에 불리: O(N)
  • 캐시 비효율
  • 역방향 탐색에 불리

 

더블 링크드 리스트(Double Linked List)

• 링크드 리스트에서 이전 노드를 가리키는 포인터가 추가된 자료구조
• 장점
  • 역방향 연산을 개선
  • 이전 노드에 대한 즉시 접근 가능
• 단점
  • 추가적인 메모리 필요(이전 노드 포인터)
  • 삽입, 삭제 시 좀 더 복잡한 연산 필요

---

 

 

 

 

 

 

링크드 리스트(Linked List)

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

[Data|Next] -> [Data|Next] -> [Data|Next] -> null

 

링크드 리스트의 종류

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

 

링크드 리스트의 장점

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

링크드 리스트의 단점

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

 

주요 연산과 시간 복잡도

1. 접근 (Access): O(n)
2. 검색 (Search): O(n)
3. 삽입 (Insertion):
   • 맨 앞/뒤: O(1)
   • 중간: O(n)
4. 삭제 (Deletion):
   • 맨 앞: O(1)
   • 중간/뒤: O(n)

 

예시

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

public class ListExample : MonoBehaviour
{
     void Start()
    {
        LinkedList<int> list = new LinkedList<int>();
        
        // AddLast는 list의 tail(꼬리) 뒤에다가 1을 추가한다.
        list.AddLast(1);
        list.AddLast(2);
        list.AddLast(3);
        list.AddLast(4);
        
        // AddFirst는 list의 head(머리) 앞에다가 0을 추가한다.
        list.AddFirst(0);

        var enumerator = list.GetEnumerator();

        int findIndex = 3;
        int currentIndex = 0;

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

            currentIndex++;
        }
    }
}

 

 

직접 구현

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 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;
        }
    }
}

• T는 Generic으로 C++의 템플릿과 유사한 의미이다.
  • 다양한 자료형을 지원하는 것을 의미한다.
  • 이는 컴파일 타임에 평가된다.
• {}에 있는 get, set은 프로퍼티로 설정하는 부분이다.
  • 프로퍼티란 클래스 멤버에 대한 은닉성을 설정할 수 있는 기능이다.
  • 세부적인 접근 제어를 위해 사용된다.
  • 현재의 경우, get은 public set은 private으로 설정된 것이다.

Add함수는 Head가 null이라면 생성한 새로운 노드를 Head로 설정한다.
만약, Head가 이미 존재한다면 끝 노드를 탐색하여 마지막에 생성한 새로운 노드를 추가한다.

 

순회는 다음과 같이 진행된다.

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

---

 

 

 

더블 링크드 리스트(Double Linked List)

링크드 리스트에서 이전 노드를 추가로 관리하는 자료구조이다.

null <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> null

장점

• 양방향 탐색 가능
• 이전 노드에 대한 즉시 접근 가능

단점

• 추가 메모리 사용 (이전 노드 포인터)
• 삽입/삭제 시 더 많은 포인터 조작 필요

 

함수

AddLast

public void AddLast(T data)
{
    Node<T> newNode = new Node<T>(data);
    if (Head == null && Tail == null)
    {
        Head = newNode;
        Tail = newNode;
    }
    else
    {
        Tail.Next = newNode;
        newNode.Prev = Tail;

        Tail = newNode;
    }
}

만약, Head가 null이고 Tail이 null이라면 새로 생성한 node를 Head와 Tail로 설정한다.

그렇지 않다면 Tail의 다음 노드로 새로 생성한 node를 설정하고 기존 Tail노드를 새로 생성한 노드의 이전 노드로 설정한다.

AddFirst

public void AddFirst(T data)
{
    Node<T> newNode = new Node<T>(data);
    if (Head == null && Tail == null)
    {
        Head = newNode;
        Tail = newNode;
    }
    else
    {
        newNode.Next = Head;
        Head.Prev = newNode;

        Head = newNode;
    }
}

AddLast와 동일하게 Head와 Tail이 null이라면 새로 생성한 node를 Head 및 Tail로 설정한다.

그렇지 않다면, 새로 생성한 node가 Head가 되도록 설정한다.

Insert

public void Insert(T data, int index)
{
    Node<T> newNode = new Node<T>(data);

    int cnt = 0;
    var current = Head;
    while (cnt++ < index && current.Next != null)
    {
        current = current.Next;
    }

    if (cnt != index)
    {
        //index가 전체 사이즈를 넘은 경우
        Tail.Next = newNode;
        newNode.Prev = Tail;
        Tail = newNode;
    }
    else
    {
        //그렇지 않은 경우
        if (current == Head) Head = newNode;
    
        if(current.Prev != null) current.Prev.Next = newNode;
        newNode.Prev = current.Prev;
    
        newNode.Next = current;
        current.Prev = newNode;
    }
}

index번째에 새로운 node를 삽입하기 위해 Head에서부터 index번째까지 Next를 통해 이동한다.

만약, 다음 노드가 없다면 제일 끝에 삽입한다.

index번째 node가 존재한다면, 해당 노드의 Prev, Next값들을 적절하게 조절한다.

 

Remove

public void Remove(int index)
{
    var current = Head;
    int cnt = 0;
    while (current != null && cnt++ < index)
    {
        current = current.Next;
    }

    if (current == Head)
    {
        Head = current.Next;
    }

    if (current == Tail)
    {
        Tail = current.Prev;
    }

    if(current.Prev != null) current.Prev.Next = current.Next;
    if(current.Next.Prev != null) current.Next.Prev = current.Prev;
}

Remove도 Insert와 마찬가지로 index번째 node를 찾는 과정을 수행한다.

만약, 전체 길이를 넘는 index가 주어졌을 때는 마지막 node를 삭제한다.

이때, Head나 Tail이 삭제될 수 있기 때문에 설정하는 것을 잊으면 안 된다.

---