내일배움캠프 59일차 TIL - 선형 자료구조 - LinkedList

권태하·2024년 7월 10일

C#TIL Unity 꾸준실습 내일배움캠프TIL 선형 자료구조 - LinkedList 스파르타내일배움캠프 스파르타내일배움캠프TIL

확인 문제

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

내 답:
LinkedList는 연결 리스트(linked list)의 일종으로, 데이터 항목들이 노드(node) 형태로 저장되며, 각 노드가 다음 노드를 가리키는 참조(또는 포인터)를 포함하는 자료 구조입니다. 연결 리스트는 배열과 달리, 노드들이 메모리 상에서 연속적으로 위치할 필요가 없으며, 각 노드는 다음 노드의 위치 정보를 포함합니다. 이러한 특성 때문에 연결 리스트는 동적으로 데이터를 추가하거나 삭제할 때 유연하게 대응할 수 있습니다.
LinkedList의 작동 방식
• 노드(Node): 연결 리스트의 각 요소는 노드로 표현됩니다. 각 노드는 데이터를 저장하는 부분과 하나 또는 그 이상의 다음 노드를 가리키는 참조(링크)를 포함합니다.
• 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드만을 가리키는 참조를 포함합니다. 따라서 리스트를 순방향으로만 탐색할 수 있습니다.
• 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 참조를 포함합니다. 이를 통해 리스트를 순방향과 역방향 모두로 탐색할 수 있습니다.
• 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 참조를 포함하여, 리스트가 원형으로 연결되어 있습니다.

모범 답:

선택 - 2. LinkedList를 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다. 💡 **LinkedList 클래스**를 직접 구현해보세요.

클래스 및 주요 멤버 변수

Node: 데이터와 다음 노드를 저장하는 내부 클래스.
- Data: 노드가 저장하는 데이터.
- Next: 다음 노드를 가리키는 포인터.
My_LinkedList<T>: LinkedList를 구현하는 클래스.
- head: 리스트의 첫 번째 노드를 가리키는 포인터.
- count: 리스트의 노드 개수를 저장하는 정수.

함수

IsEmpty: 리스트가 비어있는지 확인하는 함수.
- 입력: 없음.
- 출력: 리스트가 비어있으면 true, 아니면 false.
AddFirst: 리스트의 맨 앞에 노드를 추가하는 함수.
- 입력: 추가할 데이터 item.
- 출력: 없음.
Insert: 리스트의 n번째 노드 뒤에 새로운 노드를 삽입하는 함수.
- 입력: 삽입할 위치 n (0-based index)와 추가할 데이터 item.
- 출력: 없음.
- 동작:
  - n이 0이면 AddFirst를 호출하여 맨 앞에 노드를 추가합니다.
  - n이 0보다 큰 경우:
    - 현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
    - 각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
    - 반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
    - 새로운 노드를 생성하고, 그 노드의 Data 필드에 item을 저장합니다.
    - 새로운 노드의 Next 필드를 현재 노드의 Next로 설정합니다.
    - 현재 노드의 Next를 새로운 노드로 설정합니다.
    - count를 1 증가시킵니다.
RemoveFirst: 리스트의 첫 번째 노드를 제거하고 그 데이터를 반환하는 함수.
- 입력: 없음.
- 출력: 제거된 노드의 데이터.
Remove: 리스트의 n번째 노드를 제거하고 그 데이터를 반환하는 함수.
- 입력: 제거할 노드의 위치 n (0-based index).
- 출력: 제거된 노드의 데이터.
- 동작:
  - n이 0이면 RemoveFirst를 호출하여 첫 번째 노드를 제거합니다.
  - n이 0보다 큰 경우:
    - 현재 노드를 head로 설정하고, 현재 노드가 null일 때까지 또는 n-1 번 반복합니다.
    - 각 반복에서 현재 노드를 다음 노드로 업데이트합니다.
    - 반복 후의 현재 노드가 null이면 예외를 발생시킵니다.
    - 제거할 노드를 현재 노드의 Next로 설정합니다.
    - 현재 노드의 Next를 제거할 노드의 Next로 설정합니다.
    - 제거할 노드의 데이터를 임시 변수에 저장합니다.
    - count를 1 감소시킵니다.
    - 임시 변수에 저장된 데이터를 반환합니다.
Count: 리스트의 노드 개수를 반환하는 함수.
- 입력: 없음.
- 출력: 리스트의 노드 개수.
PrintAllNodes: 리스트의 모든 노드를 출력하는 함수.
- 입력: 없음.
- 출력: 없음.

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 ******

        // ***********************
    }

    public void AddFirst(T item)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public void Insert(int n, T item)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public T RemoveFirst()
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public T Remove(int n)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******

        // ***********************
    }

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

직접 구현 답안

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 head == null;
        // ***********************
    }

    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)
    {
        // ****** CODE HERE ******
				if (n < 0 || n > count)
        {
            throw new ArgumentOutOfRangeException(nameof(n), "Index is out of range");
        }

        if (n == 0)
        {
            AddFirst(item);
            return;
        }

        Node newNode = new Node(item);
        Node current = head;
        for (int i = 0; i < n - 1; 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 temp = head;
        head = head.Next;
        count--;
        return temp.Data;
        // ***********************
    }

    public T Remove(int n)
    {
        // ****** CODE HERE ******
				if (n < 0 || n >= count)
        {
            throw new ArgumentOutOfRangeException(nameof(n), "Index is out of range");
        }

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

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

        Node temp = current.Next;
        current.Next = temp.Next;
        count--;
        return temp.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());
    }
}

설명 문제

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

내 답:

동적 할당
• LinkedList는 노드를 추가하거나 제거함으로써 크기를 동적으로 조정할 수 있습니다. 이는 고정 크기를 가진 배열과 대비되는 특징으로, 런타임에 데이터의 개수에 따라 메모리 사용량을 조절할 수 있습니다.
효율적인 삽입 및 삭제
• 리스트의 시작, 중간, 끝 어디에나 새로운 노드를 삽입하거나 기존 노드를 삭제하는 작업이 배열에 비해 효율적입니다. 배열에서는 삽입 또는 삭제 시 다른 요소들을 이동시켜야 하지만, LinkedList에서는 단순히 노드의 참조를 변경함으로써 이를 수행할 수 있습니다.
순차 접근
• LinkedList는 인덱스를 통한 직접 접근(direct access)이 불가능하며, 특정 요소에 접근하기 위해서는 처음부터 순차적으로 탐색해야 합니다. 이는 탐색 작업에서 배열에 비해 성능이 떨어지는 원인이 됩니다.
추가 메모리 사용
• 각 노드가 데이터와 함께 다음 노드를 가리키는 참조 정보를 포함하므로, 배열에 비해 상대적으로 더 많은 메모리를 사용합니다. 특히, 이중 연결 리스트(doubly linked list)의 경우 이전 노드를 가리키는 참조도 추가로 포함하기 때문에 더 많은 메모리를 필요로 합니다.
다양한 형태
• 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List) 등 다양한 형태로 구현될 수 있습니다. 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 참조를 모두 포함하여 양방향 탐색이 가능하고, 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 형태로 연결됩니다.
LinkedList는 유연한 크기 조정과 효율적인 삽입 및 삭제가 필요할 때 유용하게 사용될 수 있으나, 탐색 성능이나 메모리 효율성 측면에서는 배열이나 다른 자료 구조에 비해 불리할 수 있습니다.

모범 답:

순서 유지 : 데이터는 삽입된 순서대로 유지
동적 크기 : 필요에 따라 노드를 추가하거나 제거하여 크기를 조정
삽입/삭제 효율성 : 중간 위치에 데이터 삽입/삭제 작업이 빠름 (O(1) 시간 복잡도)
임의 접근 비효율성 : 특정 인덱스의 데이터에 직접 접근하는 데 느림 (O(n) 시간 복잡도)
추가 메모리 사용 : 각 노드는 데이터와 다음 노드를 가리키는 포인터를 저장하기 때문에 메모리 사용량이 증가

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

내 답:

LinkedList 사용이 유리한 경우
1. 동적 데이터: 데이터의 개수가 런타임에 변할 수 있고, 컬렉션의 크기를 동적으로 조정해야 하는 경우 LinkedList는 유연한 크기 조정이 가능하여 유리합니다.
2. 빈번한 삽입 및 삭제: 리스트의 시작, 중간, 끝 어디에나 데이터를 삽입하거나 삭제하는 작업이 빈번하게 발생하는 경우, LinkedList는 노드의 참조만 변경하면 되므로 배열에 비해 효율적입니다.
3. 메모리 할당 제약: 고정된 크기의 메모리 할당이 어려운 경우, LinkedList는 필요할 때마다 노드를 할당하여 메모리를 효율적으로 사용할 수 있습니다.
LinkedList 사용이 불리한 경우
1. 빠른 임의 접근이 필요한 경우: LinkedList는 순차 접근만 가능하므로, 특정 인덱스의 요소에 빠르게 접근해야 하는 경우 배열이나 ArrayList와 같은 자료 구조가 더 효율적입니다.
2. 메모리 사용량: 각 노드가 데이터 외에 참조(링크) 정보를 추가로 포함하기 때문에, LinkedList는 배열에 비해 상대적으로 더 많은 메모리를 사용합니다. 메모리 사용량이 중요한 애플리케이션에서는 이를 고려해야 합니다.
3. 탐색 성능: 리스트를 순회하며 특정 요소를 찾는 작업이 자주 발생하는 경우, LinkedList의 순차 접근 방식은 배열이나 해시 테이블에 비해 성능이 떨어집니다.
결론적으로, 데이터의 삽입과 삭제가 빈번하게 발생하고, 크기 조정의 유연성이 필요한 경우 LinkedList를 사용하는 것이 좋습니다. 반면, 빠른 임의 접근이 필요하거나 메모리 사용량과 탐색 성능이 중요한 경우에는 다른 자료 구조를 고려하는 것이 더 적합할 수 있습니다.

모범 답:

데이터 순서가 중요한 경우 : 데이터 삽입/삭제 순서를 유지해야 하는 경우
중간 삽입/삭제 빈도가 높은 경우 : 데이터 목록의 중간 부분에서 자주 삽입/삭제 작업을 수행해야 하는 경우
동적 크기 조정 필요한 경우 : 데이터 목록의 크기가 미리 정해지지 않고 필요에 따라 변동될 가능성이 있는 경우

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

내 답:

모범 답:

실습 문제

💡 **[LinkedList를 이용한 ObjectPool 만들기]**

Object Pool은 객체를 미리 생성해두고 필요할 때마다 재사용하는 디자인 패턴입니다.

이는 객체 생성과 소멸에 드는 비용을 줄여 성능을 향상시킬 수 있습니다.

이 문제에서는 LinkedList를 이용하여 수정 및 삽입의 시간 복잡도가 O(1)인 Object Pool을 구현해야 합니다.

주요 멤버 변수

pool: 사용 가능한 객체를 저장하는 LinkedList<T>.
createFunc: 새로운 객체를 생성하는 데 사용하는 함수.
resetAction: 객체를 재사용하기 전에 초기화하는 함수.

함수 명세

GetObject
- 기능: 풀에서 객체를 가져옵니다. 만약 풀에 사용 가능한 객체가 없다면 새로운 객체를 생성합니다.
- 입력: 없음.
- 출력: 풀에서 가져온 객체 T.
ReleaseObject
- 기능: 객체를 풀에 반환합니다.
- 입력: 반환할 객체 obj (제네릭 타입 T).
- 출력: 없음.
Count
- 기능: 현재 풀에 있는 객체의 수를 반환합니다.
- 입력: 없음.
- 출력: 현재 풀에 있는 객체의 수 (int 값).

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 ******

        // ***********************
    }

    public void ReleaseObject(T obj)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    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()}");
    }
}

예제 답

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

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

권태하

스터디 로그

이전 포스트

내일배움캠프 58일자 TIL - C# 심화 문법

다음 포스트

내일배움캠프 59일차 TIL - 선형 자료구조 - LinkedList

확인 문제

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

클래스 및 주요 멤버 변수

함수

설명 문제

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

내 답:

모범 답:

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

내 답:

모범 답:

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

내 답:

모범 답:

실습 문제

주요 멤버 변수

함수 명세

내일배움캠프 58일자 TIL - C# 심화 문법

내일배움캠프 60일차 TIL - 선형 자료구조 - Stack

0개의 댓글

관련 채용 정보