LinkedList
LinkedList<T>는 .NET에서 제공하는 제네릭 연결 리스트 구현으로, 이중 연결 리스트의 형태로 데이터를 관리합니다. System.Collections.Generic 네임스페이스에 포함되어 있으며, 노드 간의 포인터를 통해 리스트의 앞뒤로 자유롭게 이동할 수 있어 특정 시나리오에서 효율적인 성능을 제공합니다.
LinkedList의 기본 사용법
LinkedList<T>를 사용하여 데이터를 순차적으로 추가하고 삭제할 수 있습니다. LinkedList는 양방향 연결 리스트로, 각 노드가 이전 및 다음 노드를 가리킵니다. 다음은 LinkedList<int>의 기본적인 사용 예제입니다:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
LinkedList<int> numbers = new LinkedList<int>();
numbers.AddLast(1);
numbers.AddLast(2);
numbers.AddLast(3);
// 요소 출력
foreach (int number in numbers)
{
Console.WriteLine(number);
}
// 출력:
// 1
// 2
// 3
}
}LinkedList<T>의 특징
- 이중 연결 리스트: 각 노드는 이전 노드와 다음 노드에 대한 참조를 가지고 있어 리스트의 양방향 탐색이 가능합니다.
- 유연한 삽입/삭제: 임의의 위치에 노드를 추가하거나 삭제하는 작업이 용이하며, 특정 노드에서의 삽입/삭제는 O(1)의 시간 복잡도를 가집니다.
- 노드 순회: 노드 간 포인터를 사용하여 리스트를 순회할 수 있습니다.
장점
- 빠른 삽입 및 삭제: 리스트의 중간에서 요소를 삽입하거나 삭제하는 경우, 연결된 노드의 포인터만 변경하면 되므로 매우 효율적입니다.
- 유연성: 리스트의 처음이나 끝, 중간 어디에든 요소를 손쉽게 추가하거나 삭제할 수 있습니다.
- 타입 안전성: 제네릭 타입을 사용하여 타입 안전성을 보장합니다.
단점
- 순차 접근만 가능: 인덱스를 통한 임의 접근이 불가능하며, 특정 위치에 접근하기 위해서는 노드를 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도를 가집니다.
- 메모리 오버헤드: 각 노드가 이전 및 다음 노드를 가리키기 위한 포인터를 포함하고 있어, 배열과 비교했을 때 메모리 사용량이 높습니다.
주요 메서드와 속성
생성자와 초기화
기본 생성자
빈 LinkedList를 생성합니다.
LinkedList<int> numbers = new LinkedList<int>();초기 데이터 지정
기존의 컬렉션을 사용하여 LinkedList를 초기화할 수 있습니다.
int[] initialData = { 1, 2, 3 };
LinkedList<int> numbers = new LinkedList<int>(initialData);- 배열 또는 다른 컬렉션으로
LinkedList를 초기화할 수 있습니다.
요소 추가
AddFirst
리스트의 맨 앞에 요소를 추가합니다.
numbers.AddFirst(0);AddLast
리스트의 맨 뒤에 요소를 추가합니다.
numbers.AddLast(4);AddBefore 및 AddAfter
특정 노드의 앞이나 뒤에 요소를 추가합니다.
LinkedListNode<int> node = numbers.Find(2);
numbers.AddBefore(node, 1);
numbers.AddAfter(node, 3);- 특정 노드를 기준으로 삽입 위치를 유연하게 지정할 수 있습니다.
요소 제거
Remove
특정 값을 가진 첫 번째 노드를 제거합니다.
numbers.Remove(2);- 값이 여러 개 있는 경우, 첫 번째로 일치하는 값만 제거됩니다.
RemoveFirst 및 RemoveLast
리스트의 첫 번째 또는 마지막 요소를 제거합니다.
numbers.RemoveFirst();
numbers.RemoveLast();요소 탐색 및 접근
Find
특정 값을 가진 첫 번째 노드를 찾습니다.
LinkedListNode<int> foundNode = numbers.Find(3);
if (foundNode != null)
{
Console.WriteLine($"찾은 값: {foundNode.Value}");
}- 값을 찾으면 해당 노드를 반환하고, 없으면
null을 반환합니다.
기타 유용한 메서드와 속성
Count
리스트에 포함된 노드의 개수를 반환합니다.
int count = numbers.Count;First 및 Last
리스트의 첫 번째 및 마지막 노드를 가져옵니다.
LinkedListNode<int> firstNode = numbers.First;
LinkedListNode<int> lastNode = numbers.Last;First와Last를 사용하여 리스트의 시작과 끝을 쉽게 참조할 수 있습니다.
LinkedList<T>의 활용
양방향 탐색이 필요한 시나리오
LinkedList는 양방향 탐색이 가능하므로, 리스트의 양 끝에서부터 데이터를 탐색해야 하는 시나리오에 적합합니다. 예를 들어, 최근 사용된 데이터나 방문 기록을 관리하는 경우 유용하게 사용할 수 있습니다.
복잡한 삽입 및 삭제가 필요한 경우
리스트의 중간에 빈번하게 요소를 삽입하거나 삭제해야 하는 경우, 배열보다 LinkedList가 더 효율적입니다. 배열은 중간에 요소를 삽입하거나 삭제할 때 다른 요소들을 이동해야 하지만, LinkedList는 노드의 참조만 변경하면 되므로 성능 상 이점이 있습니다.
LinkedList<T>와 다른 자료 구조의 비교
- 배열Array: 배열은 인덱스를 사용하여 O(1)로 요소에 접근할 수 있지만, 크기가 고정되어 있고 중간에 삽입/삭제 시 많은 요소를 이동해야 합니다. 반면,
LinkedList는 삽입/삭제가 O(1)이지만, 임의 접근이 O(n)입니다. List<T>:List<T>는 동적 배열로 구현되어 있어 인덱스를 통한 접근이 빠르지만, 중간에서의 삽입/삭제에는 비용이 많이 듭니다.LinkedList는 삽입/삭제가 빠르지만, 인덱스 접근이 불가능합니다.LinkedList는 삽입과 삭제가 빈번한 시나리오에서 유리하며, 양방향 탐색이 필요할 때 적합한 자료 구조입니다. 다만, 메모리 사용량과 순차 접근만 가능하다는 점을 고려하여 적절한 상황에서 사용해야 합니다.
LRU 캐시 구현
LinkedList<T>는 특정 응용 시나리오에서 매우 유용하게 사용될 수 있습니다. 특히 LRU Least Recently Used 캐시와 같은 데이터 구조의 구현에서 자주 사용됩니다. LRU 캐시는 최근에 사용된 데이터를 빠르게 찾고, 오래된 데이터를 제거하는 방식으로 자주 사용되는 데이터를 빠르게 접근할 수 있도록 합니다. 이와 같은 기능은 LinkedList와 해시테이블의 조합으로 쉽게 구현할 수 있습니다.
LRU 캐시는 다음과 같은 방식으로 동작합니다:
- 최근에 사용된 데이터는 리스트의 앞부분으로 이동하고, 가장 오래된 데이터는 리스트의 끝부분에 위치합니다.
- 새로운 데이터가 들어오면, 데이터가 이미 존재하는지 해시 테이블을 통해 빠르게 확인합니다.
- 존재한다면 해당 노드를 리스트의 앞부분으로 이동시켜 가장 최근 사용된 것으로 표시합니다.
- 존재하지 않는다면 새로운 노드를 리스트의 앞부분에 추가합니다.
- 캐시 용량을 초과할 경우 가장 오래된 데이터(리스트의 끝부분에 있는 데이터)를 제거합니다. 이러한 구조는 LinkedList의 노드 추가, 삭제 시 효율적인 시간 복잡도(O(1))와 해시 테이블의 빠른 검색(O(1))을 결합한 것입니다. 이를 통해 다음과 같은 이점들을 얻을 수 있습니다:
- 효율적인 삽입 및 삭제:
LinkedList는 삽입 및 삭제 시 노드 간의 연결만 변경하면 되므로 매우 효율적입니다. - 빠른 검색: 데이터가 리스트에 존재하는지를 확인하는 과정에서 해시 테이블을 사용하여 O(1)의 시간 복잡도를 유지할 수 있습니다.
using System;
using System.Collections.Generic;
public class LRUCache<K, V>
{
private readonly int capacity;
private LinkedList<KeyValuePair<K, V>> cacheList;
private Dictionary<K, LinkedListNode<KeyValuePair<K, V>>> cacheMap;
public LRUCache(int capacity)
{
this.capacity = capacity;
this.cacheList = new LinkedList<KeyValuePair<K, V>>();
this.cacheMap = new Dictionary<K, LinkedListNode<KeyValuePair<K, V>>>(capacity);
}
public V Get(K key)
{
if (cacheMap.TryGetValue(key, out LinkedListNode<KeyValuePair<K, V>> node))
{
// 사용된 노드를 리스트의 앞부분으로 이동
cacheList.Remove(node);
cacheList.AddFirst(node);
return node.Value.Value;
}
throw new KeyNotFoundException("해당 키가 캐시에 존재하지 않습니다.");
}
public void Put(K key, V value)
{
if (cacheMap.TryGetValue(key, out LinkedListNode<KeyValuePair<K, V>> node))
{
// 기존 키가 존재할 경우, 값을 업데이트하고 리스트의 앞부분으로 이동
node.Value = new KeyValuePair<K, V>(key, value);
cacheList.Remove(node);
cacheList.AddFirst(node);
}
else
{
if (cacheList.Count >= capacity)
{
// 캐시 용량 초과 시, 마지막 노드를 제거
var lastNode = cacheList.Last;
cacheMap.Remove(lastNode.Value.Key);
cacheList.RemoveLast();
}
// 새로운 노드를 리스트의 앞부분에 추가
var newNode = new LinkedListNode<KeyValuePair<K, V>>(new KeyValuePair<K, V>(key, value));
cacheList.AddFirst(newNode);
cacheMap[key] = newNode;
}
}
}이 예제에서 LRUCache 클래스는 다음과 같은 역할을 수행합니다:
LinkedList: 노드 순서를 유지하며 가장 최근에 사용된 노드를 리스트의 앞부분으로 이동시킵니다.Dictionary: 키-값 쌍을 유지하여 특정 키에 해당하는 노드를 빠르게 찾습니다. 이 구조는 LinkedList의 효율적인 노드 삽입/삭제와 Dictionary의 빠른 검색 기능을 결합하여, 캐시의 적재 및 조회가 모두 O(1)의 시간 복잡도로 이루어지게 만듭니다. 이는 고성능이 요구되는 캐시 시스템에서 매우 중요한 장점입니다. 따라서LinkedList<T>는 이러한 복합 자료 구조를 구현하는 데 적합하며, 단순 삽입 및 삭제 이외에도 데이터 사용 패턴을 효율적으로 관리할 수 있도록 돕는다는 점에서 매우 유용합니다.
LinkedList<T>의 메모리 관리 및 가비지 컬렉션 관련 문제
LinkedList<T>는 이중 연결 리스트로 구현되어 있어 각 노드는 다음 및 이전 노드에 대한 참조를 가지고 있습니다. 이러한 연결 구조 때문에 메모리 관리와 관련된 몇 가지 중요한 이슈가 존재합니다. 이를 이해하면 LinkedList 사용 시 메모리 효율성을 높이고 잠재적인 문제를 예방할 수 있습니다.
메모리 오버헤드
LinkedList<T>의 각 노드는 값뿐만 아니라 다음 노드와 이전 노드에 대한 참조를 저장하기 위해 추가 메모리 공간을 사용합니다. 이 때문에 배열Array이나 List<T>와 비교했을 때 메모리 사용량이 상대적으로 많습니다. 각 노드가 두 개의 참조를 저장하기 때문에 노드 수가 많아질수록 이러한 오버헤드가 크게 누적될 수 있습니다.
가비지 컬렉션GC과의 상호작용
LinkedList<T>의 각 노드는 동적으로 메모리에 할당되며, 특정 노드를 제거할 때 해당 노드는 더 이상LinkedList의 일부가 아니기 때문에 가비지 컬렉션에 의해 회수될 수 있습니다.- 그러나, 노드 간의 참조가 여전히 남아 있는 경우, 예를 들어, 다른 노드가 삭제된 노드를 참조하고 있거나, 외부에서 삭제된 노드를 참조하고 있을 때 가비지 수집이 지연될 수 있습니다. 이러한 상황에서는 불필요한 메모리가 회수되지 않아 메모리 누수가 발생할 가능성이 있습니다.
메모리 누수 방지 방법
- 노드 참조를 명시적으로 해제: 노드를 삭제할 때, 해당 노드를 참조하고 있는 변수를 명시적으로
null로 설정하여 참조를 해제하는 것이 좋습니다. 이렇게 하면 가비지 컬렉터가 노드를 더 빨리 회수할 수 있습니다. Remove메서드 사용:LinkedList<T>의Remove,RemoveFirst,RemoveLast등의 메서드를 사용하여 노드를 삭제할 때, 이러한 메서드들은 노드 간의 연결을 적절히 해제하므로(참조 정보 제거), 노드가 가비지 컬렉션 대상이 될 수 있도록 합니다.
많은 노드를 가진 LinkedList의 GC 영향
LinkedList에 많은 노드가 있을 경우, 가비지 컬렉터는 더 많은 개별 노드들을 추적하고 회수해야 합니다. 이는 GC의 성능에 부정적인 영향을 미칠 수 있으며, 특히 큰 리스트에서 대량의 삭제 작업을 수행한 후 GC가 많은 양의 노드를 회수해야 할 때 GC의 부하가 증가할 수 있습니다.- 또한, Generation 0/1/2 단계에서, 많은 노드가 회수 대상이 되면 GC가 Generation 2까지 도달해야 할 가능성이 커지며, 이는 애플리케이션의 일시적인 멈춤(Pause)을 야기하여 응답성을 저하시킬 수 있습니다.
효율적인 사용 방안
- 불필요한 노드 삭제: 필요하지 않은 노드는 바로 제거하여 가비지 컬렉션이 더 효율적으로 동작하도록 돕습니다.
- 대체 자료 구조 고려: 만약 삽입과 삭제 작업이 빈번하지 않고, 임의 접근이 더 중요하다면
List<T>나 배열과 같은 다른 자료 구조가 더 적합할 수 있습니다. 이러한 구조는 연속적인 메모리 블록을 사용하여 메모리 할당 및 GC 부하를 줄일 수 있습니다.
Weak Reference 사용
- 가비지 컬렉션의 영향을 줄이기 위해,
WeakReference를 사용하는 것도 하나의 방법입니다. 이는 특정 객체를 약한 참조로 유지하여, 해당 객체가 다른 강한 참조가 없는 경우 가비지 컬렉터가 자유롭게 회수할 수 있도록 합니다. 다만, 이 방법은 더 복잡한 메모리 관리가 필요하기 때문에 신중하게 적용해야 합니다. 이와 같이LinkedList<T>를 사용할 때는 메모리 관리와 가비지 컬렉션에 대한 이해가 중요하며, 적절한 상황에서 신중하게 사용해야 합니다. 특히 많은 노드를 가진LinkedList를 사용할 경우에는 메모리 오버헤드와 가비지 컬렉션의 부하를 고려하여 사용해야 하며, 필요할 경우 적절한 삭제 및 참조 해제를 통해 메모리 효율성을 높일 수 있습니다.
Buy me a coffee