링크드 리스트 (Linked List) 정리

링크드 리스트 (Linked List)

1. 링크드 리스트가 필요한 이유

배열과 List<T>는 데이터를 메모리에 연속적으로 저장한다. 인덱스를 이용해 원하는 위치의 데이터에 바로 접근할 수 있다는 장점이 있다. 이 작업의 시간 복잡도는 O(1)이다.

하지만 중간에 데이터를 삽입하거나 삭제하면 뒤에 있는 원소들을 한 칸씩 이동해야 한다. 따라서 삽입과 삭제에 O(n)의 시간이 걸릴 수 있다.

링크드 리스트는 이러한 데이터 이동을 줄이기 위한 자료구조다. 각 원소가 다음 원소를 참조하도록 연결하므로, 원소 자체를 이동시키지 않고 연결 관계만 변경해 삽입과 삭제를 처리한다.

주요 활용 상황

• 데이터의 삽입과 삭제가 자주 발생하는 경우
• 대기열의 맨 앞에서 데이터를 계속 꺼내는 경우
• 이미 삽입하거나 삭제할 위치를 알고 있는 경우

단, 링크드 리스트가 항상 배열이나 List<T>보다 빠른 것은 아니다. 위치를 찾는 데 시간이 걸릴 수 있기 때문이다.

2. 노드와 링크

링크드 리스트는 여러 개의 노드(Node)가 연결된 자료구조다.

각 노드는 다음 두 가지 요소로 구성된다.

• Value: 노드가 저장하는 데이터
• Next: 다음 노드를 가리키는 참조

링크드 리스트의 주요 구성 요소는 다음과 같다.

• Head: 첫 번째 노드를 가리키는 참조
• Tail: 마지막 노드를 가리키는 참조
• Next: 다음 노드를 가리키는 참조
• null: 다음 노드가 없음을 의미

마지막 노드의 Next는 null이다. 따라서 처음 노드부터 Next를 따라가다가 null을 만나면 순회를 종료한다.

노드는 메모리상 연속된 위치에 있을 필요가 없다. 노드의 순서는 메모리 주소가 아니라 서로 연결된 참조가 결정한다.

C#에서 클래스 인스턴스를 가리키는 것은 참조다. 노드의 참조를 다른 노드에 대입해도 객체 자체가 복사되는 것은 아니다.

3. 단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드만 가리키는 구조다.

앞에 노드 추가

새 노드의 Next가 기존 Head를 가리키도록 한 다음, Head를 새 노드로 변경한다.

기존 노드를 이동시키지 않고 참조만 변경하므로 O(1)이다.

중간 노드 삭제

중간 노드를 삭제하려면 삭제할 노드의 바로 이전 노드가 필요하다.

이전 노드의 Next가 삭제할 노드의 다음 노드를 가리키도록 변경하면 된다. 연결이 끊어진 노드는 더 이상 리스트에서 접근할 수 없으며, 다른 곳에서도 참조하지 않는다면 가비지 컬렉터가 회수할 수 있다.

단일 연결 리스트는 이전 방향으로 이동할 수 없다. 따라서 삭제할 노드를 찾을 때 이전 노드도 함께 기억해야 한다.

마지막 노드 삭제

마지막 노드를 삭제하려면 새로운 마지막 노드가 될 직전 노드를 찾아야 한다.

단일 연결 리스트는 뒤로 이동할 수 없으므로 처음부터 순회해야 한다. 따라서 마지막 노드 삭제는 O(n)이다.

4. 이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조다.

노드에는 다음 요소가 존재한다.

• Value: 저장된 데이터
• Previous: 이전 노드를 가리키는 참조
• Next: 다음 노드를 가리키는 참조

이 구조에서는 앞뒤 양방향으로 이동할 수 있다.

노드를 알고 있을 때 삭제

삭제할 노드를 이미 알고 있다면 Previous와 Next를 이용해 앞뒤 노드를 바로 찾을 수 있다.

앞 노드가 삭제할 노드의 다음 노드를 가리키고, 뒤 노드가 삭제할 노드의 이전 노드를 가리키도록 변경하면 된다.

따라서 노드를 이미 알고 있는 상황에서 삭제하는 작업은 O(1)이다.

단, 삭제 대상이 첫 번째 노드나 마지막 노드라면 Head 또는 Tail도 함께 갱신해야 한다.

이중 연결 리스트의 단점

• 노드마다 참조가 하나 더 필요하므로 메모리 사용량이 증가한다.
• 삽입과 삭제 과정에서 변경해야 하는 연결 정보가 많아진다.
• 연결 하나라도 잘못 변경하면 정방향과 역방향 순회 결과가 달라질 수 있다.

5. 노드를 외부에 공개할 때 주의할 점

이중 연결 리스트에서 노드를 이미 알고 있다면 O(1)로 삭제할 수 있다.

.NET의 LinkedList<T>는 이러한 기능을 제공하기 위해 LinkedListNode<T>를 공개한다. AddFirst, AddLast 등의 메서드는 생성한 노드를 반환한다.

하지만 외부에서 노드를 다룰 수 있으면 잘못된 노드를 전달하는 문제가 발생할 수 있다.

예를 들어 다음과 같은 상황이 있다.

• 다른 리스트에 속한 노드를 전달하는 경우
• 이미 리스트에서 제거된 노드를 전달하는 경우

이러한 노드의 연결 정보를 검증하지 않고 변경하면 리스트 구조가 깨질 수 있다.

이를 방지하기 위해 노드가 자신이 속한 리스트를 기억하도록 설계할 수 있다.

• 노드의 List가 현재 리스트를 가리키도록 한다.
• 리스트는 노드를 전달받으면 해당 노드가 자신의 소속인지 확인한다.
• 노드를 제거하면 노드의 List를 null로 변경한다.

6. 시간 복잡도 비교

• 배열과 List<T>의 끝에 추가하는 작업은 용량이 충분하면 O(1)이며, 용량이 부족하면 배열을 확장하고 데이터를 복사해야 한다. 따라서 List<T>.Add는 평균적으로 O(1)이다.

단일 연결 리스트의 끝에 추가하는 작업은 Tail을 유지하는 경우 O(1)이다. 이중 연결 리스트도 Tail을 유지하면 끝에 추가하는 작업이 O(1)이다.

7. 링크드 리스트가 항상 빠른 것은 아니다

캐시 지역성

배열과 List<T>는 데이터가 연속된 메모리에 저장된다. CPU가 데이터를 읽을 때 주변 데이터도 함께 캐시에 올라올 수 있어 순회에 유리하다.

반면 링크드 리스트는 노드가 메모리 곳곳에 흩어질 수 있다. 다음 노드를 참조할 때마다 새로운 메모리 위치에 접근해야 하므로 순회 성능이 불리할 수 있다.

가비지 컬렉터 부담

링크드 리스트는 노드마다 별도의 객체를 생성한다.

노드를 자주 생성하고 제거하면 가비지 컬렉터가 처리해야 하는 객체가 늘어날 수 있다. 특히 Unity처럼 매 프레임 성능이 중요한 환경에서는 불필요한 노드 생성을 주의해야 한다.

검색 비용

링크드 리스트는 특정 인덱스에 바로 접근할 수 없다. 원하는 값을 찾으려면 처음부터 노드를 하나씩 확인해야 한다.

따라서 검색은 O(n)이다.

링크드 리스트의 핵심 장점은 삽입하거나 삭제할 노드를 이미 알고 있을 때 연결만 변경해 처리할 수 있다는 점이다.

8. C#에서 직접 구현할 자료구조

단일 연결 리스트

먼저 SinglyLinkedList<T>를 구현한다.

주요 구성 요소와 기능은 다음과 같다.

• Count: 노드의 개수
• First: 첫 번째 노드의 값
• Last: 마지막 노드의 값
• AddFirst(): 앞에 노드 추가
• AddLast(): 뒤에 노드 추가
• RemoveFirst(): 첫 번째 노드 제거 및 값 반환
• Remove(): 특정 값의 노드 제거
• Contains(): 특정 값의 존재 여부 확인
• Clear(): 전체 노드 제거

노드 클래스는 리스트 내부에 private 중첩 클래스로 만든다. 사용자는 노드의 연결 구조를 직접 다루지 않고 값 중심으로 리스트를 사용할 수 있다.

이중 연결 리스트

다음으로 DoublyLinkedList<T>를 구현한다.

단일 연결 리스트와 달리 노드를 외부에 공개해 노드를 직접 전달하는 삽입과 삭제 기능을 제공한다.

주요 구성 요소와 기능은 다음과 같다.

• Count: 노드의 개수
• First: 첫 번째 노드
• Last: 마지막 노드
• AddFirst(): 앞에 노드 추가
• AddLast(): 뒤에 노드 추가
• AddBefore(): 지정한 노드 앞에 추가
• AddAfter(): 지정한 노드 뒤에 추가
• Remove(): 지정한 노드 제거
• RemoveFirst(): 첫 번째 노드 제거
• RemoveLast(): 마지막 노드 제거
• Find(): 특정 값의 노드 검색
• Contains(): 특정 값의 존재 여부 확인
• Clear(): 전체 노드 제거
• Backward(): 마지막 노드부터 역방향 순회

노드의 Next, Previous, List 연결 정보는 리스트 내부에서만 변경할 수 있도록 접근 범위를 제한한다.

9. 전체 핵심 정리

링크드 리스트는 배열을 대체하는 자료구조가 아니라, 데이터의 접근 방식과 삽입·삭제 빈도에 따라 선택하는 자료구조다.