LinkedList를 써야 할 때

LinkedList를 공부하면서 이게 배열이나 List와 어떻게 다른가는 복잡하게 익히지만 정작 이걸 언제 쓰는 게 좋은지에 대해서는 모르는 사람들이 많다. LinkedList는 이터래이트를 하면서 컬렉션의 아이템을 추가하고 없앨 때 제격이다. 배열이나 List로는 이를 제대로 구현할 수 없다.

아래는 정수로 이뤄진 컬렉션에서 홀수들을 찾아 없애는 c# 예제다.

LinkedList<int> ints = new();

for (int i = 0; i < 5; i++)
{
    ints.AddLast(i);
}

LinkedListNode<int> linkedListNode = ints.First!;

while (linkedListNode is not null)
{
    LinkedListNode<int> temporaryNode = linkedListNode.Next!;

    if (linkedListNode.Value % 2 == 1)
    {
        ints.Remove(linkedListNode);
    }

    linkedListNode = temporaryNode;
}

여느 컬렉션들의 item을 LinkedList에서는 node라 한다. 노드는 next라는 프라퍼티를 갖기 때문에 이터래이트를 하는 동안 반복을 몇 번 해야하는지에 구애 받지 않는다.

foreach는 블록 안에서 컬렉션의 아이템을 추가하거나 없앨 수 없다. for 블록 안에서 아이템을 없애기만 한다면 이터래이트를 거꾸로 하면 된다. 아이템을 추가하기만 할 거라면 그냥 쓰면 된다. 하지만 이터래이트를 한 방향으로만 하면서 추가하고 제거하는 걸 동시에 하면 아이템 연산을 건너뛰거나 중복하게 된다. LinkedList를 쓰면 이 문제들을 피할 수 있다.