핵심 정리

var list = new LinkedList<int>();
var node = list.AddLast(10);
list.AddAfter(node, 20);
list.Remove(node);

구조

연결 리스트는 값과 다음 노드의 참조를 가진 노드들이 이어진 구조입니다. 배열처럼 i번째 위치를 바로 계산할 수 없어서 임의 접근은 O(n)입니다.

[value | next] -> [value | next] -> [value | null]

단방향 연결 리스트는 다음 노드만 알고, 양방향 연결 리스트는 이전 노드와 다음 노드를 모두 압니다.

class Node
{
    public int Value;
    public Node? Next;
}

삽입·삭제가 빠른 조건

연결 리스트의 삽입·삭제가 O(1)이라는 말은 삽입·삭제할 위치의 노드를 이미 알고 있을 때만 맞습니다. 위치를 찾기 위해 처음부터 순회해야 한다면 탐색 O(n)이 먼저 듭니다.

찾기 O(n) + 삭제 O(1) = 전체 O(n)

그래서 코테에서는 연결 리스트 자체보다 스택, 큐, 덱처럼 목적이 뚜렷한 구조를 더 자주 씁니다.

선택 기준

연결 리스트 문제는 포인터 연결을 끊고 다시 잇는 순서가 핵심입니다.

// current 다음 노드 삭제
if (current.Next != null)
{
    current.Next = current.Next.Next;
}

주의할 점