[자료구조] LinkedList

https://thepathfinder.co.kr/entry/C-%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8

1. LinkedList가 무엇인지 알고 있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?

• 일련의 노드로 구성되어 데이터를 저장하는 선형 자료구조. 각 노드는 데이터를 저장하는 필드(Data)와 다음 노드를 가리키는 포인터(Next)를 가지고 있고, 포인터를 통해 노드들을 탐색하고 삽입, 삭제 등의 연산을 수행한다.

2. LinkedList의 특성을 설명해주세요.

• 선형 자료구조
  • LinkedList는 데이터를 순차적으로 저장하는 선형 자료구조입니다.
• 동적 크기
  • LinkedList는 크기가 고정되지 않고, 필요에 따라 동적으로 크기를 조절할 수 있습니다.
• 데이터 삽입 및 삭제:
  • ArrayList: 데이터 삽입과 삭제 시 해당 데이터 뒤쪽의 모든 데이터를 이동시켜야 하므로 비용이 높습니다.
  • LinkedList: 삽입과 삭제 시 앞, 뒤 노드의 포인터만 변경하면 되므로, 삽입/삭제 연산의 비용이 낮습니다.
• 추가적인 메모리 사용
  • 각 노드는 데이터를 저장하는 공간 외에도 다음 노드를 가리키는 포인터를 저장해야 하므로, 추가적인 메모리를 사용합니다.

3. LinkedList는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

• 데이터 크기가 계속 변동하고, 데이터 삽입과 삭제가 빈번하게 일어날 때, 사용하면 좋다.
• 탐색 연산을 할 때는 비용이 높기 때문에 탐색 연산을 자주할 때는 LinkedList보다는 ArrayList를 사용하는 것이 좋다.

4. LinkedList를 본인의 프로젝트에 적용해본 경험을 말해주세요.

• LinkedList를 써본 적은 없지만 사용하면 좋을 것 같은 부분들에 대해서 얘기해보겠다.
• LinkedList는 삽입/삭제에 큰 장점을 가지기 때문에 삽입 삭제가 빈번하게 일어나는 상황에 사용하는 것이 좋을 것 같다.
  • 오브젝트 풀링
  • 게임 이벤트 관리

 5. LinkedList를 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다.

LinkedList.cs

public class My_LinkedList<T>
{
    private class Node
    {
        public T Data;
        public Node Next;

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

    private Node head;
    private int count;

    public My_LinkedList()
    {
        head = null;
        count = 0;
    }

    public bool IsEmpty()
    {
        // ****** CODE HERE ******
        return count == 0;
        // ***********************
    }

    public void AddFirst(T item)
    {
        // ****** CODE HERE ******
        Node newNode = new Node(item); 
        newNode.Next = head;
        head = newNode;
        count++;
        // ***********************
    }

    public void Insert(int n, T item)
    {
        if (n < 0 || n > count)
        {
            throw new ArgumentOutOfRangeException($"{n} is not vaild");
        }

        // ****** CODE HERE ******
        if (n == 0)
        {
            AddFirst(item);
        }
        else
        {
            Node newNode = new Node(item);
            Node current = head;
            for (int i = 1; i < n; i++)
            {
                current = current.Next;
            }
            newNode.Next = current.Next;
            current.Next = newNode;
            count++;
        }
        // ***********************
    }

    public T RemoveFirst()
    {
        // ****** CODE HERE ******
        if (IsEmpty())
        {
            throw new InvalidOperationException("List is empty");
        }

        Node nodeToRemove = head;
        head = head.Next;
        count--;
        return nodeToRemove.Data;
        // ***********************
    }

    public T Remove(int n)
    {
        // ****** CODE HERE ******
        if (n < 0 || n >= count)
        {
            throw new ArgumentOutOfRangeException($"{n} is not vaild");
        }

        if (n == 0)
        {
            return RemoveFirst();
        }

        Node current = head;
        for (int i = 1; i < n; i++)
        {
            current = current.Next;
        }

        Node nodeToRemove = current.Next;
        current.Next = nodeToRemove.Next;
        count--;
        return nodeToRemove.Data;
        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******
        return count;
        // ***********************
    }

    public void PrintAllNodes()
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.Data + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

// 구현 확인을 위한 코드입니다.
class Program
{
    static void Main(string[] args)
    {
        My_LinkedList<int> list = new My_LinkedList<int>();

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

        Console.WriteLine("Linked List:");
        list.PrintAllNodes();

        Console.WriteLine("Remove First: " + list.RemoveFirst());
        Console.WriteLine("Remove at 2: " + list.Remove(2));

        Console.WriteLine("Linked List:");
        list.PrintAllNodes();

        Console.WriteLine("Count: " + list.Count());
    }
}

 

 

 

ObjectPool.cs

public class Bullet
{
    public static int BulletCount = 0;
    public Bullet() => ID = BulletCount++;
    ~Bullet() => BulletCount--;
    public int ID { get; private set; }
    public (float, float) Position { get; set; }
}

public class ObjectPool<T>
{
    private LinkedList<T> pool;
    private Func<T> createFunc;
    private Action<T> resetAction;

    public ObjectPool(int size, Func<T> createFunc, Action<T> resetAction = null)
    {
        this.pool = new LinkedList<T>();
        this.createFunc = createFunc ?? throw new ArgumentNullException(nameof(createFunc));
        this.resetAction = resetAction;

        for (int i = 0; i < size; i++)
            pool.AddFirst(createFunc());
    }

    public T GetObject()
    {
        // ****** CODE HERE ******
        if (pool.Count == 0)
        {
            return createFunc();
        }
        else
        {
            T obj = pool.First.Value;
            pool.RemoveFirst();
            return obj;
        }
        // ***********************
    }

    public void ReleaseObject(T obj)
    {
        // ****** CODE HERE ******
        resetAction?.Invoke(obj);
        pool.AddFirst(obj);
        // ***********************
    }

    public int Count()
    {
        return pool.Count;
    }
}

// 구현 확인을 위한 코드입니다.
class Program
{
    static void Main(string[] args)
    {
        ObjectPool<Bullet> bulletPool = new ObjectPool<Bullet>(
            10,
            () => new Bullet(),
            bullet => { bullet.Position = (0, 0); }
        );

        // 현재 풀에 있는 객체 수를 출력합니다.
        Console.WriteLine($"Objects in pool: {bulletPool.Count()}");

        // 여러 개의 Bullet 객체를 풀에서 얻습니다.
        for (int i = 1; i <= 5; i++)
        {
            Bullet bullet = bulletPool.GetObject();
            bullet.Position = (i * 10.0f, i * 20.0f);
            Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
        }

        // 풀에서 객체를 다시 얻어서 출력했다가 반환합니다. 객체는 초기화된 상태여야 합니다.
        for (int i = 1; i <= 3; i++)
        {
            Bullet bullet = bulletPool.GetObject();
            Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
            bulletPool.ReleaseObject(bullet);
        }

        // 몇 개의 객체를 풀에 반환합니다.
        for (int i = 6; i <= 10; i++)
        {
            Bullet bullet = bulletPool.GetObject();
            bullet.Position = (i * 10.0f, i * 20.0f);
            bulletPool.ReleaseObject(bullet);
        }

        // 최종적으로 풀에 있는 객체 수를 출력합니다.
        Console.WriteLine($"Final objects in pool: {bulletPool.Count()}");
    }
}