[C#] 선형자료구조 실습하기 1 - LinkedList

[확인문제]

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

LinkedList는 데이터를 저장하는 선형 자료 구조이다. 배열과는 달리,  데이터를 담고 있는 노드 단위로 구성되어 있으며, 각 노드는 다음 노드를 가리키는 링크 를 가지고 있다.

따라서 LinkedList의 노드들은 연결되어있는데, 이로 인해 리스트의 순서를 유지할 수 있다.

 

LinkedList는 '단일 연결 리스트'와 '이중 연결 리스트'로 나눌 수 있다.

단일 연결 리스트 : 각 노드는 다음 노드를 가리키는 링크만을 가지고 있다.

이중 연결 리스트 : 각 노드는 다음 노드를 가리키는 링크뿐만 아니라, 이전 노드를 가리키는 링크도 가지고 있다.

 

<작동 방식>

노드(Node) : 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
헤드(Head) : 리스트의 시작 노드를 가리킵니다.
추가(Add) : 새로운 노드를 리스트의 시작이나 특정 위치에 추가합니다.
삭제(Remove) : 리스트의 시작이나 특정 위치에서 노드를 제거합니다.
탐색(Search) : 특정 값을 찾거나 리스트의 특정 위치에 접근합니다.

 

<작동 방식>

삽입 : 새로운 노드를 리스트에 삽입

삭제 : 리스트에서 노드를 삭제

검색 : 리스트에서 특정 값을 가진 노드를 검색

 

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

 

💡 LinkedList 클래스를 직접 구현해보세요.

클래스 및 주요 멤버 변수

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

함수

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

public bool IsEmpty()
{
	// 리스트가 비어있는지 확인
    return head == null;
}

public void AddFirst(T item)
{
	// 리스트의 맨 앞에 새로운 노드 추가
    Node newNode = new Node(item);
    newNode.Next = head;
    head = newNode;
    count++;
}

public void Insert(int n, T item)
{
	// 리스트의 n번째 위치에 새로운 노드 삽입
     if (n == 0)
        {
            AddFirst(item);
            return;
        }

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

        if (current == null)
        {
            throw new IndexOutOfRangeException("Index out of range.");
        }

        Node newNode = new Node(item);
        newNode.Next = current;
        if (previous != null)
        {
            previous.Next = newNode;
        }
        else
        {
            head = newNode;
        }
        count++;
}

public T RemoveFirst()
{
	// 리스트의 첫 번째 노드를 제거하고 그 데이터를 반환
    if (IsEmpty())
    {
        throw new InvalidOperationException("List is empty");
    }

    T data = head.Data;
    head = head.Next;
    count--;
    return data;
}

public T Remove(int n)
{
	// 리스트의 n번째 노드를 제거하고 그 데이터를 반환
    if (n < 0 || n >= count)
    {
        throw new ArgumentOutOfRangeException(nameof(n), "Index out of range");
    }

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

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

    Node toRemove = current.Next;
    current.Next = toRemove.Next;
    count--;
    return toRemove.Data;
}

public int Count()
{
	// 리스트의 노드 개수를 반환
    return count;
}

 

* return head == null 의 의미

head 포인터를 사용하여 리스트에 노드가 없는지 확인

LinkedList에서 head 포인터는 중요한 역할을 한다. 이는 리스트의 첫번째 노드를 가리키는 참조 역할을 하는데 만약 head 포인터가 null 이라면 이는 리스트가 비어있다는 의미로 return head is null; 로 대체 가능하다.

 

* 포인터는 메모리의 위치를 직접 참조하는 데 사용되는 도구로, 마치 집 주소처럼 특정 데이터가 저장된 메모리 위치를 가리키는 역할을 한다. 포인터를 사용하면 메모리에 직접 접근하여 데이터를 효율적으로 조작할 수 있다.

 

[설명문제]

 

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

LinkedList는 데이터 요소를 노드라는 구조로 연결하여 구성된 선형 데이터 구조이며, 각 노드에는 데이터 값과 다음 노드를 가리키는 포인터를 포함한다. 이러한 연결 방식은 데이터 삽입 및 삭제 작업에 효율성을 제공하지만, 임의 접근에는 비효율적이다.

 

LinkedList 특성:

순서 유지 : 데이터는 삽입된 순서대로 유지

동적 크기 : 필요에 따라 노드를 추가하거나 제거하여 크기를 조정

삽입/삭제 효율성 : 중간 위치에 데이터 삽입/삭제 작업이 빠름 (O(1) 시간 복잡도)

임의 접근 비효율성 : 특정 인덱스의 데이터에 직접 접근하는 데 느림 (O(n) 시간 복잡도)

추가 메모리 사용 : 각 노드는 데이터와 다음 노드를 가리키는 포인터를 저장하기 때문에 메모리 사용량이 증가

 

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

LinkedList 사용 적합 사례

데이터 순서가 중요한 경우 : 데이터 삽입/삭제 순서를 유지해야 하는 경우

중간 삽입/삭제 빈도가 높은 경우 : 데이터 목록의 중간 부분에서 자주 삽입/삭제 작업을 수행해야 하는 경우

동적 크기 조정 필요한 경우 : 데이터 목록의 크기가 미리 정해지지 않고 필요에 따라 변동될 가능성이 있는 경우

 

LinkedList 사용 불리한 사례

임의 접근 빈도가 높은 경우 : 특정 인덱스의 데이터에 자주 접근해야 하는 경우 성능 저하를 초래할 수 있음

메모리 제약이 있는 경우 : 추가적인 메모리 사용량이 제약이 되는 환경에서는 다른 자료구조가 더 적합할 수 있음

캐시 성능 중요한 경우 : 연속된 메모리 공간에 저장되지 않기 때문에 캐시 성능에 영향을 미칠 수 있음

 

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

댓글 목록을 관리하는 데 LinkedList를 활용했습니다. 댓글 목록은 순서대로 유지되어야 했고, 중간 댓글 추가/삭제 작업이 빈번하게 발생했습니다. 또한, 댓글 목록의 크기는 동적으로 변동될 수 있었습니다. 이러한 특징들은 LinkedList를 사용하기에 적합했고, 실제로 효율적인 성능을 보여주었습니다.

하지만, 다른 프로젝트에서는 데이터 순서가 중요하지 않거나 임의 접근 빈도가 높은 경우에는 배열, 해시 테이블과 같은 다른 자료구조를 사용했습니다.

LinkedList는 데이터 순서 유지, 중간 삽입/삭제 효율성, 동적 크기 조정 등의 장점을 가지고 있습니다. 하지만, 임의 접근 비효율성, 추가 메모리 사용 등의 단점도 존재합니다. 따라서 프로젝트의 특성을 꼼꼼히 분석하여 적절한 자료구조를 선택하는 것이 중요합니다.

 

 

[실습문제]

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

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

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

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

주요 멤버 변수

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

함수 명세

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

public T GetObject()
{
    if (pool.Count == 0)
    {
        // 사용 가능한 객체가 없으면 새로 생성
        return createFunc();
    }
    else
    {
        // 사용 가능한 객체를 풀에서 가져옴
        T obj = pool.First.Value;
        pool.RemoveFirst();

        // 객체 초기화
        if (resetAction != null)
            resetAction(obj);

        return obj;
    }
}

public void ReleaseObject(T obj)
{
    if (obj != null)
    {
        // 반환된 객체를 풀에 추가
        pool.AddFirst(obj);
    }
}