연결 리스트는 배열보다 삽입이 빠른 자료구조가 아니다

연결 리스트를 처음 배우면 각 데이터가 다음 데이터를 가리키는 구조라고 설명한다.

type PlaylistNode = {
  trackId: string;
  next: PlaylistNode | null;
};

새로운 노드를 삽입할 때 뒤쪽 데이터를 옮길 필요가 없으므로 배열보다 삽입이 빠르다는 설명도 함께 배운다. 입문 단계에서는 배열과 연결 리스트의 구조적 차이를 이해하는 데 유용하다.

그러나 음악 서비스에서 플레이리스트를 만든다고 생각해보자. 사용자는 특정 곡을 검색하고, 열 번째 곡을 재생하고, 목록 전체를 화면에 표시하며, 가끔 곡의 순서를 바꾼다. 삽입 한 번의 비용만 보고 연결 리스트를 선택하면 이런 작업이 실제로 어떻게 실행되는지를 놓치게 된다.

새로운 곡을 빠르게 연결할 수 있더라도 삽입할 위치를 찾는 데 오래 걸린다면 정말 효율적일까? 데이터베이스에 저장된 플레이리스트에서도 같은 장점이 유지될까? 사용자가 목록을 읽는 방식과 자료구조의 접근 방식은 잘 맞을까?

실제 서비스에서 연결 리스트를 선택한다는 것은 삽입 속도를 선택하는 일이 아니라, 현재 항목을 기준으로 앞이나 뒤의 항목을 따라가는 접근 방식을 선택하는 일이다.

삽입할 위치를 이미 알고 있을 때만 연결은 빠르다

크리스의 플레이리스트에 새로운 곡을 추가한다고 해보자. 배열에서는 중간에 항목을 삽입하면 뒤에 있는 항목이 한 칸씩 이동한다.

playlist.splice(insertIndex, 0, newTrack);

배열의 길이가 n이라면 최악의 경우 이동 비용은 O(n)이다. 연결 리스트에서는 삽입할 노드를 알고 있을 때 두 연결만 변경하면 된다.

newNode.next = currentNode.next;
currentNode.next = newNode;

이 부분만 보면 연결 리스트의 삽입은 O(1)이다. 하지만 크리스가 “Chris가 추가한 곡 다음에 새 곡을 넣어주세요”라고 요청했다면 먼저 그 곡이 들어 있는 노드를 찾아야 한다.

function findNode(
  head: PlaylistNode | null,
  trackId: string
) {
  let current = head;

  while (current) {
    if (current.trackId === trackId) {
      return current;
    }

    current = current.next;
  }

  return null;
}

찾는 과정에는 최대 O(n)이 걸린다. 이후의 연결 변경이 O(1)이어도 전체 작업은 O(n)이다. “연결 리스트의 삽입은 빠르다”는 설명에는 삽입할 노드를 이미 알고 있다는 조건이 숨어 있다.

이 조건은 서비스 설계에서 중요하다. 대부분의 요청은 메모리 주소나 노드 객체를 전달하지 않는다. 사용자는 곡 ID, 플레이리스트 항목 ID 또는 화면의 위치를 보낸다. 서버는 그 값으로 대상 항목을 먼저 찾아야 한다.

따라서 삽입 비용만 비교해서는 자료구조를 선택할 수 없다. 위치를 찾는 비용과 변경하는 비용을 하나의 작업으로 계산해야 한다.

사용자는 삽입보다 목록을 더 자주 읽는다

플레이리스트에서 발생하는 작업을 생각해보면 곡 삽입만 있는 것이 아니다. 앱은 목록을 처음부터 화면에 표시하고, 특정 위치로 이동하며, 전체 재생 시간을 계산하고, 사용자가 선택한 곡을 바로 찾아야 한다.

배열에서는 열 번째 곡에 인덱스로 접근할 수 있다.

const track = playlist[9];

연결 리스트에는 열 번째 항목의 주소가 따로 없다. 첫 번째 노드부터 next를 아홉 번 따라가야 한다. 특정 위치에 자주 접근하는 플레이리스트라면 이 차이는 삽입 성능보다 더 크게 느껴질 수 있다.

연결 리스트가 자연스러운 경우도 있다. 현재 재생 중인 곡에서 다음 곡으로 이동하는 작업이 대부분이고, 이미 현재 노드를 가지고 있다면 next를 따라가는 방식이 서비스 동작과 잘 맞는다. 반대로 목록 전체 표시, 위치 이동, 범위 선택과 정렬이 많다면 배열이 더 단순하다.

자료구조는 가장 눈에 띄는 한 번의 작업이 아니라 서비스에서 반복되는 주요 작업을 기준으로 선택해야 한다. 크리스가 한 달에 한 번 곡의 순서를 바꾸지만 매일 수십 번 목록을 열어본다면, 드문 삽입을 빠르게 만들기 위해 모든 조회를 불편하게 만드는 선택은 좋은 교환이 아니다.

메모리에서 빠른 구조가 저장소에서도 그대로 빠른 것은 아니다

연결 리스트의 장점은 주로 메모리 안에서 노드 참조를 직접 가지고 있을 때 설명된다. 하지만 실제 플레이리스트는 서버가 종료되어도 남아 있어야 하므로 데이터베이스에 저장된다.

다음과 같이 각 항목이 다음 항목의 ID를 가리키도록 만들 수 있다.

type PlaylistEntry = {
  id: string;
  playlistId: string;
  trackId: string;
  nextEntryId: string | null;
};

세 번째 곡 다음에 새 곡을 삽입하려면 새 항목을 저장하고, 기존 항목의 nextEntryId를 변경하면 된다. 뒤쪽 항목 전체의 위치를 수정하지 않아도 된다는 장점은 남아 있다.

하지만 목록을 읽을 때는 이야기가 달라진다. 첫 항목을 조회한 뒤 nextEntryId로 다음 항목을 계속 조회하면 데이터베이스 요청이 여러 번 발생할 수 있다. 메모리에서는 포인터 하나를 따라가는 일이 저렴하지만, 데이터베이스에서는 매번 조회 비용이 붙는다.

모든 항목을 한 번에 가져온 뒤 서버에서 연결을 복원할 수도 있다. 그러면 별도의 조회 구조가 필요하고, 누락된 연결이나 순환도 검사해야 한다. 예를 들어 마지막 곡이 실수로 앞의 곡을 다시 가리키면 플레이리스트 순회가 끝나지 않는다.

entry-a → entry-b → entry-c
             ↑         ↓
             └─────────┘

이 구조를 사용한다면 서버는 다음 항목이 같은 플레이리스트에 속하는지, 존재하는 항목인지, 이미 방문한 항목인지 확인해야 한다. 클라이언트가 보낸 nextEntryId를 그대로 저장해서도 안 된다. 하나의 잘못된 연결이 목록 전체를 읽을 수 없게 만들기 때문이다.

그래서 일반적인 플레이리스트라면 항목을 행으로 저장하고 position이나 정렬 키를 두는 방식이 더 이해하기 쉽다.

type PlaylistEntry = {
  id: string;
  playlistId: string;
  trackId: string;
  position: number;
};

이 모델에서는 데이터베이스가 position 순서로 항목을 한 번에 조회할 수 있다. 순서를 자주 변경하는 매우 큰 목록이라면 모든 위치를 다시 번호 매기는 비용이 생기지만, 그 문제가 실제로 확인되기 전부터 연결 구조를 선택할 필요는 없다.

대부분의 서비스에서는 단순한 저장 모델로 시작하고, 실제 사용 패턴을 측정한 뒤 순서 변경 방식이나 정렬 키를 개선하는 편이 낫다.

자료구조는 데이터의 모양보다 접근 경로를 결정한다

플레이리스트가 순서대로 연결되어 있다는 이유만으로 연결 리스트가 적합한 것은 아니다. 배열도 순서를 표현할 수 있고, 데이터베이스의 정렬된 행도 같은 결과를 만들 수 있다. 선택을 가르는 것은 데이터를 어떤 모양으로 그릴 수 있는지가 아니라 어떤 경로로 읽고 변경하는지다.

연결 리스트는 다음과 같은 조건에서 의미가 있다.

• 현재 항목을 이미 알고 있고 그 주변을 자주 변경한다.
• 앞에서부터 순서대로 이동하는 작업이 중심이다.
• 중간 삽입과 삭제가 매우 빈번하다.
• 위치 번호를 이용한 임의 접근은 거의 필요하지 않다.

반면 플레이리스트 전체를 자주 보여주고, 사용자가 특정 위치를 선택하며, 정렬과 범위 조회가 많다면 배열이나 정렬 가능한 데이터베이스 행이 더 잘 맞는다. 곡 ID로 반복해서 찾는 작업이 많다면 연결 리스트보다 ID 기반 조회 구조를 함께 두는 것이 효과적이다.

현실의 플레이리스트가 코드로 바뀌는 흐름은 다음과 같이 정리할 수 있다.

입력
곡 ID, 삽입할 기준 항목 ID, 이동 명령

상태
플레이리스트 항목 ID, 곡 ID, 저장된 재생 순서

출력
화면과 재생기에 필요한 순서의 곡 목록

입력에 위치가 포함되더라도 그것은 사용자가 요청한 변경 지점일 뿐이다. 서버는 해당 항목이 실제로 존재하는지 확인하고, 저장된 순서를 안전하게 변경한 뒤, 다시 읽을 수 있는 형태로 결과를 만들어야 한다. 연결 리스트를 사용한다면 이 과정에 연결의 유효성까지 책임져야 한다.

플레이리스트의 저장 구조를 정하기 전에 확인할 질문

1. 가장 자주 실행되는 작업은 전체 목록 조회인가, 현재 항목 주변의 삽입과 삭제인가?
2. 삽입할 노드를 이미 알고 있는가, 아니면 매번 처음부터 찾아야 하는가?
3. 사용자가 특정 위치의 곡으로 바로 이동해야 하는가?
4. 메모리의 참조 구조를 데이터베이스에서도 같은 비용으로 처리할 수 있다고 가정하고 있지는 않은가?
5. 연결이 끊기거나 순환하는 상태를 어떻게 방지하고 복구할 것인가?
6. 더 복잡한 구조가 필요할 만큼 실제 순서 변경 비용을 측정했는가?
7. 서비스의 원본 순서는 어디에 저장되며, API 응답에서는 어떻게 복원되는가?

삽입 속도 하나로 자료구조를 선택할 수는 없다

연결 리스트는 삽입할 위치를 이미 알고 있다면 주변의 연결만 바꿀 수 있다. 그러나 서비스 요청에서는 그 위치를 먼저 찾아야 하는 경우가 많고, 사용자는 삽입보다 목록 조회와 특정 위치 접근을 더 자주 수행할 수 있다. 데이터가 데이터베이스에 저장되면 노드를 따라가는 비용도 메모리에서 배운 것과 달라진다.

플레이리스트의 주요 동작이 현재 곡에서 다음 곡으로 이동하고 주변 항목을 자주 바꾸는 것이라면 연결 리스트가 잘 맞을 수 있다. 전체 목록 조회, 위치 접근과 정렬이 중심이라면 배열이나 순서가 지정된 데이터베이스 행이 더 자연스러운 선택이다.

자료구조를 고를 때는 “어떤 연산의 Big O가 더 좋은가”보다 “서비스가 이 데이터에 어떤 순서로 접근하는가”를 먼저 살펴봐야 한다. 다음 글에서는 해시 테이블이 빠른 검색을 제공하기 위해 어떤 메모리 비용과 충돌 처리 책임을 받아들이는지 살펴본다.