Basic Data Structures

분류: Layer 10 - 자료구조 & 알고리즘

기본 자료구조 (Basic Data Structures)

1. 이 문서의 목표

자료구조는 데이터를 어디에 놓고, 어떤 순서로 접근하며, 어떤 연산을 빠르게 만들지 정하는 설계다. 같은 데이터라도 배열에 두는지, 해시 테이블에 두는지, 큐에 두는지에 따라 코드의 시간 비용과 메모리 비용이 달라진다.

이 문서는 L10의 첫 문서다. 따라서 CPU 캐시, 포인터, V8 내부 구현을 이미 안다고 가정하지 않는다. 그런 용어는 본문에서 짧게 풀고, 처음 읽을 때 꼭 몰라도 되는 내용은 “선택 심화”로 표시한다.

1-1. 코드 읽기 계약: 알고리즘과 JavaScript를 분리해서 보기

JavaScript는 이 문서의 선택 구현 언어이지 선수지식이 아니다. 코드의 목적은 문법 시험이 아니라 “어떤 값을 저장하고, 어떤 연산을 몇 번 반복하는가”를 눈으로 보여주는 데 있다. 따라서 JavaScript 문법을 몰라도 자료구조의 불변식과 복잡도를 먼저 읽을 수 있다.

이 문서의 코드는 다음 네 층으로 구분한다.

코드의 층	무엇을 읽는가	계약과 성능 해석의 경계
알고리즘 의사코드	`push`, `pop`, `enqueue`, `dequeue`, `node.next` 흐름	추상 자료구조의 연산 계약을 표현한다. 같은 철자의 실제 언어 메서드를 뜻하지 않는다.
JavaScript/TypeScript 예시	`Array`, `Map`, `Set`, 함수와 반복문	실행하거나 변형하기 쉬운 선택 구현이다. 표기만으로 특정 시간 복잡도가 보장되지는 않는다.
JavaScript 언어 계약	`Map`의 키 동일성, `Object`의 문자열 키 변환, `WeakMap` 키의 도달 가능성	JavaScript가 정한 값의 의미다. `WeakMap`은 객체와 전역 registry에 등록되지 않은 Symbol만 키로 허용하며 키를 살려 두지 않지만, GC가 언제 회수할지는 보장하지 않는다.
V8 구현 관찰	hidden class, elements kind, sparse array 전환, 실측 성능·메모리	특정 엔진·버전·장비에서 생기는 구현 차이다. JavaScript 언어와 추상 자료구조의 보편 계약이 아니므로 측정 환경과 함께 읽는다.

pseudocode로 표시했거나 언어 표기 없이 연산 순서·메모리 모양만 보여주는 짧은 블록은 의사코드·개념도이고, javascript 또는 typescript로 표시된 블록은 선택 구현 예시다. 다만 구현 예시 안에서도 본문이 “추상 연산”이라고 따로 밝힌 줄은 해당 언어의 성능 보장이 아니라 알고리즘 역할을 표현한다.

문법은 아래 정도만 알면 첫 회독에 충분하다.

const x = 값은 이름을 값에 연결하고, let x = 값은 이후 다른 값으로 바꿀 수 있음을 나타낸다.
[]는 순서가 있는 값 모음, { key: value }는 이름으로 찾는 필드 모음이다. new Map()과 new Set()은 각각 키-값 저장소와 중복 없는 값 모음을 만든다.
for (const x of xs)와 while (조건)은 반복, if (조건)은 분기, return은 결과 반환이다. 반복문 안에서 자료를 몇 번 방문하는지가 복잡도 판단의 핵심이다.
x.method(y)는 x에 연산을 적용한다는 뜻이다. value => 결과는 값을 받아 결과를 만드는 짧은 함수 표기다.
TypeScript 예시의 User[], name: string, Map<string, User> 같은 표기는 값의 종류를 설명하는 타입 힌트다. 알고리즘 흐름을 읽을 때는 건너뛰어도 된다.

복잡도 표시는 코드 철자가 아니라 본문이 선언한 연산 모델에 붙는다. 예를 들어 추상 Deque의 왼쪽 삭제 O(1)은 popLeft() 같은 추상 연산의 계약이며, JavaScript Array.prototype.shift()의 성능을 뜻하지 않는다. Map과 Object의 키 의미론, WeakMap의 도달 가능성은 JavaScript 언어 계약으로 읽고, V8 배열 최적화와 GC·메모리 실측치는 구현 관찰로 읽어 추상 자료구조의 보장과 섞지 않는다.

첫 회독에서는 각 코드에서 입력, 저장 구조, 반복되는 연산만 표시하고 복잡도를 먼저 추론한다. 문법이 막히면 코드 아래 해설로 넘어가도 흐름이 끊기지 않는다. 실제 실행과 V8 세부 비교는 10절 실습과 “선택 심화”를 두 번째 회독에서 확인하면 된다.

첫 회독의 목표는 네 가지다.

Big-O가 “실행 시간이 몇 ms인가”가 아니라 “입력이 커질 때 연산 수가 어떻게 자라는가”를 설명할 수 있다.
Array, Linked List, Stack, Queue, Hash Table이 각각 어떤 접근 패턴을 빠르게 만들기 위해 생겼는지 설명할 수 있다.
Array.shift(), Array.includes(), 객체 키 변환처럼 흔한 실수의 비용을 작은 예제로 확인할 수 있다.
자료구조 선택이 실패했을 때 보이는 증상을 “느리다”가 아니라 “어떤 연산이 반복되어 비용이 커졌는가”로 해석할 수 있다.

2. 자료구조란 무엇인가

자료구조는 값의 모음이 아니다. 값의 모음에 다음 네 가지 계약을 붙인 것이다.

계약	질문	예
배치	값이 메모리에서 어떤 모양으로 놓이는가	연속 배열, 노드 연결, 버킷 배열
접근	값을 어떤 방식으로 찾는가	인덱스, 키, 앞/뒤 포인터
불변식	구조가 유지해야 하는 규칙은 무엇인가	Stack은 마지막 값만 먼저 꺼낸다
비용	각 연산의 시간·공간 비용은 어떻게 자라는가	조회 O(1), 탐색 O(n), 삽입 O(log n)

자료구조가 필요한 이유는 모든 연산을 동시에 빠르게 만들 수 없기 때문이다. 배열은 arr[10]처럼 위치를 알고 있는 접근에 강하지만, 맨 앞에 값을 넣을 때는 기존 값을 한 칸씩 밀어야 한다. 해시 테이블은 키로 값을 찾는 데 강하지만, 정렬된 범위 조회에는 약하다. 큐는 먼저 들어온 것을 먼저 처리하는 데 강하지만, 중간 원소를 임의로 꺼내는 구조가 아니다.

자료구조를 공부할 때는 이름보다 질문이 먼저다.

지금 자주 하는 연산은 조회, 삽입, 삭제, 순회 중 무엇인가?
접근 기준은 위치인가, 키인가, 시간 순서인가, 우선순위인가?
데이터가 얼마나 커지며, 요청당 같은 연산이 몇 번 반복되는가?
평균은 빨라도 최악의 경우가 장애로 이어질 수 있는가?
빠른 시간 대신 더 많은 메모리를 써도 되는가?

2.5. 선행 한계 -> 등장 -> 해결: 단순 배열만으로는 부족했다

가장 단순한 출발점은 “값을 연속된 칸에 일렬로 놓는다”는 배열이다. 배열은 인덱스 접근이 빠르고 메모리도 효율적이다. 하지만 실제 문제는 항상 “몇 번째 값 하나를 바로 꺼내기”만 요구하지 않는다. 맨 앞에 계속 넣어야 할 때, 최근 값을 되돌려야 할 때, 먼저 들어온 작업을 순서대로 처리해야 할 때, 키로 즉시 찾아야 할 때는 배열 하나로 모든 비용을 감당하기 어렵다.

자료구조가 분화한 이유

맨 앞 삽입이 반복된다

배열은 기존 n개를 한 칸씩 뒤로 밀어야 하므로 삽입 1회가 O(n)이다. n=1,000,000이면 한 번에 백만 칸 이동이 필요하다.

Linked List 또는 Deque는 앞쪽 연결만 바꾸는 방식으로 삽입 자체를 O(1)에 가깝게 만든다. 대신 인덱스 접근을 포기한다.

방금 본 것을 다시 꺼내야 한다

함수 호출, 괄호 매칭, Undo처럼 마지막 상태가 가장 먼저 필요하다면 매번 전체를 탐색할 이유가 없다.

Stack은 접근 패턴을 LIFO(Last In, First Out)로 제한해 push/pop을 O(1)로 만든다.

먼저 들어온 작업을 먼저 처리해야 한다

배열에서 `shift()`로 앞 원소를 꺼내면 나머지 원소를 매번 앞으로 당긴다. BFS에서 반복하면 전체가 O(n^2)로 커질 수 있다.

Queue는 head/tail 위치를 따로 관리해 enqueue/dequeue를 O(1)로 만든다.

값으로 위치를 찾아야 한다

배열에서 `includes`나 `find`는 앞에서부터 비교한다. n=100,000인 배열의 끝 값을 반복해서 찾으면 비용이 바로 드러난다.

Hash Table은 키를 버킷 인덱스로 바꿔 평균 O(1) 조회를 제공한다. 충돌과 메모리 비용은 새로 생기는 대가다.

정렬된 범위를 조회해야 한다

해시 테이블은 `id = 42` 같은 동등 조건에는 강하지만 `id BETWEEN 10 AND 50` 같은 범위에는 정렬 정보가 없다.

Tree 계열 구조는 정렬 불변식을 유지해 점 조회와 범위 조회를 O(log n) 수준으로 다룬다. 자세한 트리·그래프는 L10 후속 문서에서 다룬다.

이 문서의 핵심 흐름은 이 표와 같다. 각 자료구조는 암기할 이름이 아니라, 특정 접근 패턴의 비용을 줄이기 위해 등장한 선택지다.

3. Big-O: 비용을 입력 크기의 성장으로 읽기

3-1. 정의

Big-O 표기법은 입력 크기 n이 커질 때 연산 횟수나 메모리 사용량이 어떤 속도로 증가하는지 표현한다. 정확한 실행 시간을 예측하는 도구가 아니라, 성장률을 비교하는 언어다.

예를 들어 n = 10일 때는 중첩 루프가 눈에 띄지 않을 수 있다. 하지만 n = 100,000이 되면 O(n)과 O(n^2)는 같은 범주의 코드가 아니다. 하나는 100,000번 근처에서 끝나고, 다른 하나는 10,000,000,000번 수준으로 커진다.

복잡도	직관	n=10	n=1,000	n=1,000,000	대표 예
O(1)	입력 크기와 무관	1	1	1	배열 인덱스 접근, 해시 평균 조회
O(log n)	매번 절반씩 줄임	4	10	20	이진 탐색, 균형 트리 조회
O(n)	한 번 훑음	10	1,000	1,000,000	배열 순회
O(n log n)	나누고 각 단계에서 훑음	33	9,966	19,931,569	효율적인 비교 정렬
O(n^2)	모든 쌍을 비교	100	1,000,000	1,000,000,000,000	중첩 루프, 모든 쌍 검사

Big-O는 보통 최악의 경우를 말한다. 다만 해시 테이블처럼 “평균 O(1), 최악 O(n)“인 구조도 있으므로 평균·최악·분할 상환 비용을 구분해야 한다.

용어	의미	자료구조에서 자주 만나는 예
최악 시간	가장 나쁜 입력에서 드는 비용	해시 충돌이 모두 한 버킷에 몰리면 조회 O(n)
평균 시간	일반적인 분포에서 기대되는 비용	좋은 해시 함수와 낮은 부하율의 조회 평균 O(1)
분할 상환 시간	가끔 비싼 연산을 여러 번의 싼 연산에 나눠 평균낸 비용	동적 배열 `push`는 가끔 재할당 O(n), 전체 평균 O(1)
공간 복잡도	입력 크기 증가에 따른 추가 메모리	중복 체크용 `Set`은 시간 O(n)을 얻는 대신 공간 O(n)을 쓴다

3-2. 상수를 무시한다는 말의 경계

Big-O가 상수를 무시하는 이유는 충분히 큰 입력에서 성장률이 더 중요하기 때문이다. 3n^2과 100n^2은 둘 다 n이 2배가 되면 약 4배 커진다. 반면 100n은 계수가 커도 n이 2배가 되면 2배만 커진다.

하지만 실제 시스템에서는 상수도 사라지지 않는다. 같은 O(n) 순회라도 연속 배열은 CPU가 가까운 메모리를 한 번에 가져와 빠르게 훑고, 연결 리스트는 다음 노드 주소를 따라가며 메모리 여기저기를 방문해 느릴 수 있다. 그래서 Big-O는 “후보를 걸러내는 1차 언어”이고, 실제 성능 판단은 데이터 크기, 메모리 배치, I/O, 런타임 최적화를 함께 본다.

첫 회독에서는 이렇게 잡으면 충분하다.

Big-O는 입력이 커질 때의 위험을 보여준다.
같은 Big-O 안에서는 상수, 메모리 접근 패턴, 런타임 구현이 차이를 만든다.
O(1)이라고 해도 최악 조건과 메모리 비용이 숨어 있을 수 있다.

3-3. 손으로 보는 복잡도 예제

// O(1) - 입력 크기와 무관하게 한 번 접근
function getFirst(arr) {
  return arr[0];
}

// O(n) - 배열을 한 번 훑음
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n^2) - 모든 쌍을 비교
function hasDuplicatesSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(n) 시간, O(n) 공간 - Set으로 이미 본 값을 기억
function hasDuplicatesFast(arr) {
  const seen = new Set();
  for (const value of arr) {
    if (seen.has(value)) return true;
    seen.add(value);
  }
  return false;
}

hasDuplicatesFast가 더 빠른 이유는 비교 횟수를 줄였기 때문이다. 느린 버전은 n개 중 가능한 쌍을 모두 비교한다. 빠른 버전은 “이미 본 값인가?”를 Set에 물어보고 다음 원소로 넘어간다. 대신 seen이라는 추가 메모리를 n개까지 쓴다. 자료구조 선택은 대부분 이런 교환이다.

3-4. 이진 탐색이 O(log n)인 이유

정렬된 배열에서 값을 찾을 때 가운데를 보고 절반을 버리면 탐색 공간이 계속 반으로 줄어든다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 4)); // -1

n = 1,000,000이어도 절반 제거를 20번 정도 반복하면 하나의 위치까지 좁혀진다. 다만 정렬되어 있지 않은 배열에는 쓸 수 없다. O(log n)이라는 장점은 “정렬 불변식이 유지된다”는 조건 위에 있다.

3-5. 비용 예산으로 보는 Big-O

Big-O는 추상 표기지만, 코드 리뷰에서는 대략적인 비용 예산으로 바뀐다. 정확한 CPU cycle을 계산하려는 것이 아니라 “이 로직이 요청당 반복돼도 되는가”를 빠르게 가늠하는 것이다.

예를 들어 요청 하나가 사용자 10,000명을 처리한다고 하자.

접근 방식	대략적 연산 수	해석
인덱스 접근 1회	1	병목이 될 가능성이 낮다
한 번 순회	10,000	요청당 1회라면 보통 감당 가능, 중첩되면 주의
모든 쌍 비교	약 100,000,000	요청 경로에서는 위험하다
정렬	약 132,877	한 번이면 가능할 수 있지만 반복 정렬은 위험하다
Map으로 membership test	약 10,000	공간 O(n)을 쓰고 시간 폭발을 피한다

이 표에서 중요한 질문은 “어느 숫자가 절대적으로 빠른가”가 아니다. 같은 요청 경로 안에서 100,000,000번에 가까운 비교가 반복된다면 데이터가 조금만 커져도 병목이 된다. 반면 Map이나 Set은 메모리를 더 쓰지만 반복 비교를 줄인다.

3-6. 시간과 공간은 함께 읽는다

빠른 자료구조는 공짜가 아니다. Set으로 중복 검사를 빠르게 만들면, 이미 본 값을 저장하는 공간이 필요하다. Map으로 캐시를 만들면 조회는 빨라지지만 캐시 항목을 지우지 않으면 메모리가 계속 증가한다. Heap은 최소값이나 최대값을 반복해서 꺼내는 후속 구조이며, 값을 넣고 뺄 때 우선순위 불변식을 유지하는 비용이 든다.

작은 판단 기준은 다음과 같다.

상황	시간 우선 선택	공간 비용	주의점
중복 검사	`Set`	O(n)	n이 매우 작으면 배열도 충분할 수 있다
키 기반 조회	`Map`	O(n)	키 정규화와 삭제 정책이 필요하다
최근 N개만 유지	Ring Buffer/Deque	O(N)	오래된 값을 반드시 제거해야 한다
정렬된 범위 조회	Tree/정렬 배열	구조 유지 비용	삽입이 잦으면 정렬 유지가 비싸다

공간을 아끼기 위해 배열 선형 탐색을 유지할 수 있는 경우도 있다. 예를 들어 원소가 10개 이하이고 요청당 한두 번만 탐색한다면 Map을 만들 필요가 없다. 하지만 원소가 커지거나 같은 탐색이 반복되면 저장 공간을 쓰고 탐색 비용을 줄이는 선택이 낫다.

4. Array와 Dynamic Array

4-1. 정의

Array(배열)는 같은 종류의 값을 연속된 칸에 배치하고, 인덱스로 접근하는 자료구조다. arr[2]처럼 위치를 알고 있으면 시작 위치에서 2 * 원소 크기만큼 이동해 바로 접근할 수 있다.

인덱스:      0    1    2    3    4
값:        [10] [20] [30] [40] [50]
주소 예시: 100  104  108  112  116

arr[2] = 시작 주소 100 + 2 * 4바이트 = 주소 108

JavaScript의 Array는 고정 길이 배열이 아니라 동적 배열에 가깝다. 뒤에 값을 계속 push할 수 있고, 내부 공간이 부족하면 더 큰 공간을 확보해 기존 값을 옮긴다.

4-2. 등장한 문제와 핵심 철학

배열은 “위치를 아는 접근”을 빠르게 만들기 위해 가장 단순한 구조를 택한다. 값들을 붙여 놓으면 인덱스 접근과 순차 순회가 빠르고, 메모리 오버헤드도 낮다.

이 철학의 대가는 중간이나 앞쪽 수정이다. 맨 앞에 값을 넣으면 기존 모든 값을 뒤로 밀어야 한다.

const arr = [10, 20, 30, 40, 50];

console.log(arr[2]); // 30, O(1)

arr.unshift(5);
console.log(arr); // [5, 10, 20, 30, 40, 50], O(n)

arr.push(60);
console.log(arr); // [5, 10, 20, 30, 40, 50, 60], amortized O(1)

4-3. 동적 배열의 분할 상환 비용

동적 배열의 push는 보통 O(1)이지만, 내부 용량이 꽉 찬 순간에는 더 큰 배열을 만들고 기존 값을 옮겨야 한다. 그 한 번은 O(n)이다. 그래도 여러 번의 push를 평균 내면 O(1)로 본다.

작은 예로 보자.

push 횟수	내부 용량	일이 일어나는 방식
1	1	빈 공간에 값 하나 저장
2	2	용량 부족, 2칸으로 확장 후 복사
3	4	용량 부족, 4칸으로 확장 후 복사
4	4	빈 공간에 저장
5	8	용량 부족, 8칸으로 확장 후 복사

비싼 복사는 가끔만 발생한다. 그래서 뒤쪽 추가가 많은 경우 배열은 여전히 좋은 기본 선택이다.

4-4. 선택 심화: CPU 캐시가 배열을 더 빠르게 만드는 이유

CPU 캐시는 프로세서가 메모리보다 훨씬 빠르게 접근할 수 있는 작은 저장 공간이다. 캐시 라인은 CPU가 메모리에서 가져오는 최소 덩어리다. 흔한 x86-64 환경에서는 64바이트 단위로 가져오므로, 4바이트 정수라면 한 번에 16개가 같이 올라올 수 있다.

배열은 값이 연속되어 있어 순회할 때 다음 값이 이미 캐시에 들어와 있을 가능성이 높다. 반면 연결 리스트는 각 노드가 메모리 여러 곳에 흩어져 있을 수 있어 다음 노드로 갈 때마다 새 주소를 따라가야 한다.

접근 위치	대략적 지연	직관
L1 캐시 hit	약 1ns	CPU 바로 옆에서 찾음
L2 캐시 hit	약 5ns	조금 더 먼 캐시에서 찾음
L3 캐시 hit	약 17ns	여러 코어가 공유하는 캐시
DRAM 접근	약 60~100ns	메인 메모리까지 내려감

이 수치는 장비마다 다르지만 방향은 중요하다. 같은 O(n) 순회라도 배열이 연결 리스트보다 훨씬 빠를 수 있다. 그래서 “Linked List는 앞 삽입 O(1)이므로 배열보다 항상 빠르다”는 결론은 틀리다.

처음 읽을 때는 숫자를 외우지 않아도 된다. 핵심은 연속 배치는 순회에 유리하고, 흩어진 노드는 포인터를 따라가느라 실제 시간이 커질 수 있다는 점이다.

4-5. JavaScript 배열의 실패 신호

JavaScript 배열은 V8 같은 런타임이 내부 표현을 최적화한다. 처음부터 촘촘한 숫자 배열이면 빠른 경로를 타지만, 중간에 큰 구멍을 만들거나 타입을 섞으면 최적화가 약해질 수 있다.

const fast = [1, 2, 3, 4, 5];

const sparse = [];
sparse[0] = 1;
sparse[9999] = 2; // 중간이 비어 있는 sparse array

const mixed = [1, "hello", true]; // 타입 혼합

실패 신호는 다음과 같다.

같은 길이의 배열인데 순회 시간이 갑자기 늘어난다.
delete arr[i]나 큰 인덱스 점프가 많다.
shift, unshift, splice(0, ...)가 루프 안에서 반복된다.
숫자 계산용 배열인데 문자열, 객체, undefined가 섞인다.

이런 신호가 보이면 먼저 “배열이 맞는가”보다 “어떤 배열 연산이 반복되는가”를 본다.

4-6. worked example: 최신순 로그를 앞에 쌓고 싶을 때

이벤트를 최신순으로 보여주고 싶다고 해서 항상 앞에 삽입해야 하는 것은 아니다.

// 나쁜 선택: 이벤트가 올 때마다 앞에 삽입
const log = [];
for (const event of events) {
  log.unshift(event); // 매번 기존 원소 이동
}

events가 10,000개라면 첫 삽입은 싸지만 뒤로 갈수록 이동해야 할 원소 수가 늘어난다. 전체 비용은 O(n^2)에 가까워진다.

대안은 “저장 순서”와 “표시 순서”를 분리하는 것이다.

// 더 나은 선택: 저장은 뒤에 추가하고, 출력할 때만 역순으로 읽기
const log = [];
for (const event of events) {
  log.push(event); // amortized O(1)
}

const latestFirst = [...log].reverse(); // 필요할 때 한 번 O(n)

이 방식은 전체 삽입을 O(n)으로 유지한다. 최신순 조회가 매우 자주 필요하고 크기가 제한되어 있다면 Ring Buffer나 Deque를 검토한다. 핵심은 “앞 삽입이 필요하다”가 아니라 “최신순으로 보여야 한다”는 요구를 다시 읽는 것이다.

4-7. Ring Buffer를 떠올릴 신호

Ring Buffer는 고정 크기 배열을 원처럼 쓰는 구조다. 새 값이 들어오면 head/tail 위치만 움직이고, 오래된 칸을 덮어쓴다. 최근 N개의 로그, 최근 N초의 요청 수, 고정 크기 샘플링처럼 “전체 히스토리”가 아니라 “최근 구간”만 필요한 경우에 적합하다.

capacity = 5

push A -> [A, _, _, _, _]
push B -> [A, B, _, _, _]
push C -> [A, B, C, _, _]
push D -> [A, B, C, D, _]
push E -> [A, B, C, D, E]
push F -> [F, B, C, D, E]  // 가장 오래된 A를 덮어씀

Ring Buffer는 이 문서의 핵심 구현 대상은 아니지만, Array와 Queue 사이의 중요한 사고방식이다. “삭제”를 실제 메모리 이동으로 하지 않고, 논리적 시작 위치를 바꿔 비용을 줄인다.

5. Linked List

5-1. 정의

Linked List(연결 리스트)는 각 값이 노드에 들어 있고, 노드가 다음 노드의 위치를 가리키는 구조다. 포인터는 “다음 노드가 어디 있는지 알려주는 참조”라고 이해하면 된다.

[data:10 | next] -> [data:20 | next] -> [data:30 | null]
   주소 100           주소 305           주소 728

배열처럼 2번 인덱스로 바로 점프할 수 없다. 세 번째 값을 보려면 첫 노드에서 시작해 다음 링크를 두 번 따라가야 한다.

5-2. 등장한 문제와 핵심 철학

연결 리스트는 “값들이 꼭 연속된 칸에 있어야 하는가?”라는 질문에서 출발한다. 연속 배치를 포기하면 중간에 새 노드를 끼워 넣을 때 기존 값을 대량으로 이동하지 않아도 된다. 이미 삽입 위치의 노드를 알고 있다면 링크 몇 개만 바꾸면 된다.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  prepend(data) {
    const node = new Node(data);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  get(index) {
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current?.next;
    }
    return current?.data;
  }

  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    return result;
  }
}

const list = new LinkedList();
list.prepend(30);
list.prepend(20);
list.prepend(10);

console.log(list.toArray()); // [10, 20, 30]
console.log(list.get(1)); // 20

5-3. 비용 표와 경계

연산	Array	Linked List	해석
인덱스 접근	O(1)	O(n)	배열은 주소 계산, 리스트는 링크 추적
맨 앞 삽입	O(n)	O(1)	배열은 전체 이동, 리스트는 head 교체
맨 뒤 삽입	amortized O(1)	O(n) 또는 O(1)	tail 포인터가 있으면 리스트도 O(1)
중간 삽입	O(n)	O(n)	위치를 찾는 탐색이 필요하다
삭제	O(n)	O(n)	삭제 대상이나 직전 노드를 찾아야 한다
순회	O(n)	O(n)	둘 다 n개를 본다. 실제 시간은 배열이 유리한 경우가 많다

중간 삽입이 리스트의 장점이라는 말에는 조건이 붙는다. 삽입할 위치를 이미 알고 있을 때 삽입 자체가 O(1)이다. 위치를 찾기 위해 처음부터 걸어가면 탐색 O(n)이 먼저 든다.

5-4. 배열보다 연결 리스트가 나은 경우

연결 리스트가 적합한 경우는 생각보다 좁다.

맨 앞 삽입/삭제가 매우 빈번하다.
랜덤 인덱스 접근이 거의 없다.
노드를 이미 들고 있어서 중간 삽입 위치 탐색 비용이 없다.
데이터 이동 비용이 매우 크고, 포인터 오버헤드를 감당할 수 있다.

그렇지 않다면 배열 또는 Deque가 더 단순하고 빠를 가능성이 높다. 특히 JavaScript에서는 객체 노드의 오버헤드와 GC 비용까지 붙기 때문에 직접 연결 리스트를 구현하는 일이 많지 않다.

5-5. 반례: “앞 삽입 O(1)“만 보고 선택하면 실패한다

다음 요구사항을 보자.

이벤트를 최신순으로 앞에 넣는다.
화면에는 100번째, 1,000번째 이벤트를 자주 보여준다.
전체 이벤트를 자주 순회한다.

연결 리스트는 1번만 보면 좋아 보인다. 하지만 2번과 3번에서 매번 링크를 따라가야 한다. 이 경우에는 배열에 push한 뒤 출력 시 역순으로 읽거나, 고정 크기 링 버퍼를 쓰는 편이 나을 수 있다.

실패 신호는 다음과 같다.

“O(1) 삽입”을 기대했는데 실제로는 삽입 위치를 찾느라 O(n)이 든다.
순회가 많은데 노드 객체가 흩어져 캐시 미스와 GC 비용이 커진다.
리스트 중간 삭제 후 이전/다음 링크가 깨져 값이 사라지거나 순환한다.
크기 추적을 따로 하지 않아 size 계산이 매번 O(n)이 된다.

6. Stack, Queue, Deque

6-1. Stack: 마지막에 들어온 것이 먼저 나간다

Stack은 LIFO(Last In, First Out) 구조다. 마지막에 넣은 값을 가장 먼저 꺼낸다.

push(A) -> [A]
push(B) -> [A, B]
push(C) -> [A, B, C]
pop()   -> C, 남은 값 [A, B]

Stack은 접근 범위를 맨 끝으로 좁힌다. 그래서 push, pop, peek가 모두 O(1)에 가능하다. 대신 중간 값을 마음대로 꺼내는 구조가 아니다.

대표 문제는 괄호 매칭이다. 여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 가장 최근 여는 괄호와 맞는지 확인한다.

function isValidBrackets(s) {
  const stack = [];
  const pair = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
      continue;
    }

    const expectedOpen = pair[char];
    if (stack.pop() !== expectedOpen) return false;
  }

  return stack.length === 0;
}

console.log(isValidBrackets("({[]})")); // true
console.log(isValidBrackets("({[})")); // false

왜 Stack이 맞는가? 닫는 괄호는 항상 가장 최근에 열린 괄호와 짝을 이뤄야 한다. “가장 최근”이라는 말이 곧 LIFO다.

6-2. Queue: 먼저 들어온 것이 먼저 나간다

Queue는 FIFO(First In, First Out) 구조다. 먼저 넣은 값을 먼저 꺼낸다.

enqueue(A) -> [A]
enqueue(B) -> [A, B]
enqueue(C) -> [A, B, C]
dequeue()  -> A, 남은 값 [B, C]

작업 큐, 메시지 큐, BFS(너비 우선 탐색)는 모두 “먼저 발견한 것부터 처리”라는 규칙을 가진다.

JavaScript 배열에서 shift()로 큐를 만들면 작게는 동작한다. 하지만 shift()는 앞 값을 제거한 뒤 나머지를 앞으로 당길 수 있어 O(n)이다. 반복하면 전체가 O(n^2)로 커진다.

class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.head];
    this.head++;
    return item;
  }

  isEmpty() {
    return this.head >= this.items.length;
  }

  size() {
    return this.items.length - this.head;
  }
}

간단한 BFS 예제다.

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = new Queue();
  const result = [];

  queue.enqueue(start);

  while (!queue.isEmpty()) {
    const node = queue.dequeue();
    result.push(node);

    for (const next of graph[node] ?? []) {
      if (visited.has(next)) continue;
      visited.add(next);
      queue.enqueue(next);
    }
  }

  return result;
}

const graph = {
  A: ["B", "C"],
  B: ["D"],
  C: ["D", "E"],
  D: [],
  E: [],
};

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E"]

6-3. Deque: 양쪽에서 넣고 뺀다

Deque(Double-ended Queue)는 양쪽 끝에서 삽입과 삭제가 가능한 큐다. Stack처럼도, Queue처럼도 사용할 수 있다.

기본 자료구조 문서에서는 Deque를 “양쪽 끝만 빠른 구조”로 이해하면 충분하다. L10 후속 알고리즘에서 슬라이딩 윈도우 최대값처럼 Deque가 필요한 문제를 더 자세히 다룬다.

아래 예제는 첫 회독에서는 선택 확장이다. 핵심은 코드를 외우는 것이 아니라 “윈도우 안에서 다시 후보가 될 수 없는 값은 즉시 버린다”는 Deque의 역할을 보는 것이다.

작은 예로, 고정 크기 윈도우의 최대값을 구할 때 Deque에는 “현재 후보가 될 수 있는 인덱스”만 남긴다.

function maxSlidingWindow(nums, k):
  deque = new Deque()  // 최대값 후보의 인덱스를 저장
  result = []

  for i from 0 to nums.length - 1:
    if not deque.isEmpty() and deque.peekLeft() <= i - k:
      deque.popLeft()

    while not deque.isEmpty() and nums[deque.peekRight()] < nums[i]:
      deque.popRight()

    deque.pushRight(i)
    if i >= k - 1:
      result.append(nums[deque.peekLeft()])

  return result

maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
=> [3, 3, 5, 5, 6, 7]

이 블록의 peekLeft(), popLeft(), peekRight(), popRight(), pushRight()는 모두 양쪽 끝 연산이 O(1)인 추상 Deque 연산이다. 각 인덱스는 한 번 들어가고 왼쪽이나 오른쪽 중 한쪽 끝에서 총 한 번만 제거되므로 Deque 연산 전체는 O(n)이다. Deque가 보관하는 인덱스는 최대 k개이므로 보조 공간은 O(k)이고, 최대 n - k + 1개의 값을 담는 result까지 포함한 전체 공간은 O(n)이다. JavaScript로 옮길 때도 같은 복잡도를 유지하려면 Array.shift()로 흉내 내지 말고 head index, ring buffer, 또는 O(1) 양끝 연산을 제공하는 Deque 구현을 써야 한다.

6-4. Stack/Queue 선택 기준

필요 패턴	맞는 구조	이유
가장 최근 상태를 되돌림	Stack	마지막 상태가 먼저 필요하다
먼저 들어온 작업을 순서대로 처리	Queue	대기 순서가 의미 있다
양쪽 끝에서 넣고 빼야 함	Deque	Stack/Queue 양쪽 패턴을 모두 쓴다
중간 임의 접근이 많음	Array	Stack/Queue는 중간 접근용 구조가 아니다

실패 신호는 다음과 같다.

BFS나 작업 큐가 shift() 때문에 입력이 커질수록 비선형적으로 느려진다.
Stack으로 해결해야 할 “최근 상태” 문제를 배열 전체 탐색으로 풀고 있다.
Queue가 필요한 작업 처리에서 순서 보장이 깨져 먼저 들어온 작업이 뒤로 밀린다.
Deque가 필요한 윈도우 문제를 매번 전체 윈도우 재계산으로 풀어 O(nk)가 된다.

6-5. Queue head index의 숨은 경계

head index Queue는 shift() 비용을 없애지만, 구현에 따라 이미 처리한 값이 배열 앞쪽에 남아 있을 수 있다. head만 증가시키면 논리적으로는 비었어도 실제 배열은 계속 커진다.

class CompactingQueue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.head >= this.items.length) return null;
    const item = this.items[this.head++];

    if (this.head > 1024 && this.head * 2 > this.items.length) {
      this.items = this.items.slice(this.head);
      this.head = 0;
    }

    return item;
  }
}

이 코드는 일정 수준 이상 앞쪽이 비었을 때만 배열을 압축한다. 매번 slice하면 다시 O(n) 비용이 반복되므로, 가끔만 정리한다. 여기에도 분할 상환 사고가 들어 있다.

실패 신호는 “shift를 없앴는데도 메모리가 계속 증가한다”다. 그때는 큐가 실제로 비워지는지, 처리한 항목에 대한 참조가 배열에 남아 있는지, 압축이나 ring buffer가 필요한지 확인한다.

7. Hash Table

7-1. 정의

Hash Table은 키를 해시 함수에 넣어 버킷 인덱스로 바꾸고, 그 위치에 값을 저장하는 자료구조다.

key      -> hash function -> hash value -> bucket index
"name"   -> hash("name")  -> 12345      -> 45

해시 함수는 임의의 입력을 숫자처럼 비교 가능한 값으로 바꾸는 함수다. 버킷은 실제 값이 들어가는 칸이다. Load Factor(부하율)는 전체 버킷 수 대비 저장된 항목 수의 비율이다. 부하율이 높아지면 충돌 가능성이 커진다.

Hash Table의 철학은 “정렬이나 순서를 포기하고 키 조회를 빠르게 하자”다. 그래서 평균 조회·삽입·삭제가 O(1)에 가깝다. 대신 충돌, 메모리 오버헤드, 순서/범위 조회의 약점을 감당한다.

7-2. 작은 해시 테이블 구현

아래 예제는 실제 런타임의 해시 테이블보다 훨씬 단순하지만, “키 -> 버킷 -> 충돌 처리” 흐름을 손으로 확인하기 좋다.

class HashTableChaining {
  constructor(size = 10) {
    this.table = Array.from({ length: size }, () => []);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (const char of key) {
      hash = (hash + char.charCodeAt(0)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.table[index];
    const existing = bucket.find(([savedKey]) => savedKey === key);

    if (existing) existing[1] = value;
    else bucket.push([key, value]);
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    return bucket.find(([savedKey]) => savedKey === key)?.[1] ?? null;
  }
}

const table = new HashTableChaining();
table.set("name", "Alice");
table.set("age", 30);
table.set("name", "Bob");

console.log(table.get("name")); // "Bob"
console.log(table.get("age")); // 30
console.log(table.get("city")); // null

7-3. 충돌: 평균 O(1)이 최악 O(n)이 되는 순간

두 키가 같은 버킷으로 매핑되면 충돌(Collision)이 발생한다.

function simpleHash(key, size) {
  let hash = 0;
  for (const char of key) {
    hash = (hash + char.charCodeAt(0)) % size;
  }
  return hash;
}

const tableSize = 5;
const keys = ["name", "mane", "amen", "age", "gap"];
const buckets = {};

for (const key of keys) {
  const index = simpleHash(key, tableSize);
  buckets[index] ??= [];
  buckets[index].push(key);
}

console.log(buckets);
// { "0": ["name", "mane", "amen"], "3": ["age", "gap"] }

위처럼 한 버킷에 여러 값이 몰리면 그 안에서는 다시 순차 탐색이 필요하다. 모든 키가 한 버킷으로 몰리면 조회는 O(n)이 된다.

충돌 해결 방식은 크게 두 가지다.

방식	메커니즘	장점	약점
Chaining	한 버킷에 여러 항목을 리스트처럼 연결	구현이 비교적 단순하고 삭제가 쉽다	포인터/객체 오버헤드가 있고 캐시에 불리하다
Open Addressing	충돌하면 다음 빈 슬롯을 찾는다	배열 안에서 해결해 캐시에 유리하다	삭제 처리와 높은 부하율 관리가 어렵다

class HashTableOpenAddressing {
  constructor(size = 10) {
    this.table = new Array(size).fill(null);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (const char of key) {
      hash = (hash + char.charCodeAt(0)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    let index = this.hash(key);

    while (this.table[index] !== null && this.table[index][0] !== key) {
      index = (index + 1) % this.size;
    }

    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);

    while (this.table[index] !== null) {
      if (this.table[index][0] === key) return this.table[index][1];
      index = (index + 1) % this.size;
    }

    return null;
  }
}

7-3-1. Load Factor와 resize

Load Factor는 저장된 항목 수 / 버킷 수다. Open Addressing 방식에서는 부하율이 높아질수록 빈 슬롯을 찾기 어려워진다. 그래서 해시 테이블은 보통 일정 부하율을 넘으면 더 큰 테이블로 확장하고 기존 항목을 다시 배치한다.

예를 들어 버킷이 8개이고 항목이 6개라면 부하율은 0.75다.

버킷 수	항목 수	부하율	해석
8	2	0.25	여유가 많아 충돌 가능성이 낮다
8	6	0.75	충돌과 탐사 길이가 늘기 시작한다
8	8	1.00	Open Addressing에서는 빈 슬롯이 없다
16	6	0.375	resize 후 탐사 비용이 낮아진다

resize는 그 순간 O(n)이다. 하지만 매 삽입마다 일어나지 않으므로, 동적 배열과 비슷하게 여러 삽입에 나눠 보면 평균 삽입 비용을 낮게 유지할 수 있다. 이 역시 분할 상환 분석의 예다.

7-3-2. 반례: 나쁜 해시 함수

아래 해시 함수는 글자 코드를 더해 버킷 수로 나눈다. 학습용으로는 좋지만 실제로는 약하다. 글자 순서가 달라도 합이 같으면 같은 버킷으로 간다.

function weakHash(key, size) {
  let hash = 0;
  for (const char of key) {
    hash += char.charCodeAt(0);
  }
  return hash % size;
}

console.log(weakHash("name", 5));
console.log(weakHash("mane", 5));
console.log(weakHash("amen", 5));

"name", "mane", "amen"은 글자 순서만 다르고 같은 문자들을 포함한다. 이런 입력이 많이 들어오면 한 버킷에 몰릴 수 있다. 좋은 해시 함수는 비슷한 입력도 가능한 한 고르게 흩어야 한다.

7-4. Hash Table의 경계와 보안적 실패

Hash Table의 평균 O(1)은 좋은 해시 함수, 충분한 버킷, 균등한 입력 분포에 기대고 있다. 입력이 특정 버킷에 몰리면 평균이 아니라 최악을 본다.

실무에서는 해시 충돌이 보안 공격으로 이어질 수 있다. 공격자가 충돌을 많이 일으키는 키를 대량으로 보내면 서버가 해시 테이블 처리에 시간을 쓰느라 느려질 수 있다. 이를 Hash DoS라고 부른다. 현대 런타임은 random seed를 섞거나 충돌이 길어졌을 때 다른 구조로 바꾸는 등 방어를 넣는다.

첫 회독에서 중요한 실패 신호는 다음이다.

평균 응답 시간은 괜찮은데 p99/p999만 특정 요청에서 튄다.
특정 키 패턴이나 특정 사용자 입력에서만 Map/Set 기반 로직이 느려진다.
직접 만든 해시 함수가 단순해 비슷한 문자열이 같은 버킷으로 몰린다.
해시 테이블을 범위 조회에 쓰려고 전체를 순회하고 있다.

7-5. JavaScript Map vs Object

JavaScript에서 키-값 저장소를 만들 때 Map과 Object를 모두 쓸 수 있다. 하지만 목적이 다르다.

항목	Map	Object
키 타입	모든 값 가능	문자열 또는 Symbol 중심
크기 확인	`map.size`	`Object.keys(obj).length`
삽입 순서	보장	일반 키는 보장되지만 숫자 키는 정렬 규칙 영향
동적 추가/삭제	적합	`delete`가 내부 최적화를 깨기 쉽다
JSON 직렬화	직접 불가	바로 가능
고정된 설정 형태	과할 수 있음	적합

const map = new Map();
map.set(1, "number");
map.set("1", "string");
map.set(true, "boolean");

console.log(map.size); // 3
console.log(map.get(1)); // "number"
console.log(map.get("1")); // "string"

const obj = {};
obj[1] = "number";
obj["1"] = "string";

console.log(Object.keys(obj)); // ["1"]
console.log(obj[1]); // "string"

Object는 키를 문자열로 바꾸므로 숫자 1과 문자열 "1"이 같은 키가 된다. 반대로 Map은 객체 키를 참조 동일성으로 비교한다. 같은 모양의 객체라도 새로 만들면 다른 키다.

const permissions = new Map();

const userKey = (id) => ({ id });

permissions.set(userKey(42), "admin");
console.log(permissions.get(userKey(42))); // undefined

이 코드는 에러 없이 실패한다. 두 { id: 42 }는 모양이 같지만 같은 객체가 아니다. Map의 객체 키를 쓸 때는 동일 참조를 유지하거나, id처럼 안정적인 primitive 키를 쓰는 편이 안전하다.

primitive key는 문자열, 숫자, boolean처럼 값 자체로 비교되는 원시값 키다. 요청 ID, 사용자 ID처럼 안정적인 원시값을 키로 쓰면 객체 참조가 새로 만들어져 조회가 실패하는 문제를 피할 수 있다.

7-6. Hash Table이 DB 쿼리와 다른 이유

“Hash Table은 O(1)인데 왜 DB 조회는 느릴 수 있는가?”라는 질문은 자료구조와 시스템 비용을 구분하게 만든다.

자료구조의 복잡도는 연산 횟수의 성장률이다. DB 쿼리는 여기에 디스크 I/O, 네트워크, 락, 캐시 적중률, 실행 계획, 결과 직렬화가 붙는다. 또한 Hash Index는 동등 조건에는 맞지만 범위 조건에는 맞지 않는다.

실무 앵커를 붙이면 감각이 더 쉽다. SQS나 BullMQ의 기본 큐 동작은 “먼저 들어온 작업을 먼저 처리한다”는 FIFO 모델에서 출발하고, 우선순위가 붙으면 L10의 Heap/Priority Queue 문제로 넘어간다. Redis Hash는 user:1 같은 key 안에 name, age field를 두고 field 단위로 조회하는 구조라, Hash Table의 key-field 조회 직관과 연결된다.

쿼리 모양	Hash 계열	Tree 계열
`email = ?`	잘 맞음	잘 맞음
`created_at BETWEEN a AND b`	정렬 정보가 없어 약함	잘 맞음
`ORDER BY created_at LIMIT 20`	별도 정렬 필요	인덱스 순서 활용 가능
prefix/range 탐색	일반적으로 약함	구조에 따라 가능

이 문서에서는 Hash Table의 원리를 잡고, B-Tree와 DB 인덱스의 자세한 내용은 L9/L10 후속 문서에서 연결한다.

7-7. Hash Table 선택 기준 정리

Hash Table을 선택하기 좋은 경우는 명확하다.

id -> user, email -> account처럼 키 하나로 값을 찾는다.
중복 여부만 빠르게 알고 싶다.
삽입 순서나 정렬 순서가 핵심 요구사항이 아니다.
전체 데이터가 메모리에 올라와도 괜찮다.
최악 입력이나 공격 입력은 런타임/라이브러리 방어에 맡길 수 있거나 별도 제한을 둔다.

피해야 할 경우도 명확하다.

created_at > ? 같은 범위 조회가 핵심이다.
메모리가 빡빡하고 항목 수가 매우 크다.
키가 불안정하다. 예를 들어 요청마다 새 객체를 키로 만든다.
오래된 항목을 제거할 정책이 없다.
입력 키를 직접 해시하는 구현을 운영에 넣어야 하는데 충돌 방어를 설명할 수 없다.

8. 선택 기준: 어떤 구조를 고를 것인가

자료구조 선택은 표를 외우는 문제가 아니라 질문을 줄이는 과정이다.

8-1. 선택 질문

질문	YES면 먼저 볼 구조	왜
특정 위치를 자주 읽는가	Array	인덱스 접근 O(1)
뒤에 계속 추가하고 순회하는가	Dynamic Array	`push`는 분할 상환 O(1), 순회가 빠름
맨 앞에서 자주 넣고 빼는가	Deque, Queue, 경우에 따라 Linked List	배열 `shift/unshift` 반복을 피한다
가장 최근 값을 되돌려야 하는가	Stack	LIFO가 문제 규칙과 맞다
먼저 들어온 일을 먼저 처리해야 하는가	Queue	FIFO가 문제 규칙과 맞다
키로 빠르게 찾아야 하는가	Hash Table, Map, Set	평균 조회 O(1)
정렬된 범위가 필요한가	Tree 계열, 정렬 배열, DB B-Tree	Hash는 순서를 보존하지 않는다
최소/최대값을 반복해서 꺼내는가	Heap	삽입/삭제 O(log n), top 조회 O(1)

Heap과 Tree는 이 문서에서 깊게 다루지 않는다. 단, 선택 기준에 이름이 등장하는 이유는 기본 자료구조를 고르는 순간 이미 다음 구조의 필요성을 감지해야 하기 때문이다.

8-2. 자주 틀리는 선택

상황	흔한 실수	왜 문제인가	더 나은 방향
중복 검사	배열에 넣고 `includes` 반복	O(n) 검사를 n번 반복해 O(n^2)	`Set`으로 본 값을 기록
작업 큐	`push` + `shift`	`shift`가 매번 앞쪽 이동을 유발	head index Queue
동적 키-값 저장	Object에 계속 추가/삭제	키 문자열 변환, delete 비용, hidden class 깨짐	`Map`
고정 설정 객체	모든 것을 Map으로 저장	JSON 변환과 구조 파악이 불편	`Object`
범위 조회	Hash Table만 사용	순서 정보가 없어 전체 스캔	Tree/정렬 배열/DB 인덱스
반복 최소값 추출	매번 배열 정렬	추출마다 O(n log n)	Heap

8-3. 수치 감각

실제 기준은 환경마다 다르지만, 아래 숫자는 “언제 신호가 커지는가”를 잡는 데 도움 된다.

시나리오	위험해지는 규모	이유
`Array.includes`로 중복 검사	n > 1,000부터 눈에 띄기 쉬움	O(n^2) 비교가 된다
`shift()` 기반 Queue	n > 10,000에서 체감되기 쉬움	앞 원소 제거마다 이동 비용
일반 Array 숫자 1,000,000개	수십 MB 가능	값 외 런타임 오버헤드가 붙는다
`Float64Array(1_000_000)`	약 8MB	8바이트 숫자가 연속 저장된다
`Map`/`Set` 1,000,000개 항목	수십 MB 이상	버킷, 포인터, 엔트리 오버헤드

const floatArr = new Float64Array(1_000_000); // 약 8MB
const intArr = new Int32Array(1_000_000); // 약 4MB

숫자 배열을 크게 다루고 메모리 제한이 빡빡하다면 TypedArray가 좋은 선택일 수 있다. 반대로 일반 객체나 문자열이 섞인 데이터를 다루면 TypedArray는 맞지 않는다.

8-4. 자료구조별 메모리 직관

정확한 바이트 수는 런타임과 값의 종류에 따라 달라진다. 그래도 아래 표는 선택을 할 때 유용한 방향성을 준다.

자료구조	메모리 직관	왜 그런가
TypedArray	가장 예측 가능	고정 타입 숫자가 연속 저장된다
Array of number	비교적 효율적이지만 런타임 표현 영향	숫자 최적화가 깨지면 비용이 커질 수 있다
Array of object	값 자체보다 참조와 객체 오버헤드가 큼	각 객체가 별도 메타데이터를 가진다
Linked List	원소당 오버헤드가 큼	값 외에 next/prev 참조와 객체 헤더가 붙는다
Map/Set	조회는 빠르지만 항목당 오버헤드가 큼	버킷, 해시 메타데이터, 엔트리 저장이 필요하다
Object	고정 구조는 효율적일 수 있음	hidden class 같은 런타임 최적화가 작동할 수 있다

hidden class는 V8 같은 JavaScript 엔진이 “같은 모양의 객체”를 빠르게 접근하기 위해 내부적으로 붙이는 구조 정보다. 객체에 동적 키를 계속 추가하거나 delete를 반복하면 이 최적화가 깨질 수 있어, 동적 키-값 저장에는 Map이 더 안정적이다.

따라서 “Map이 빠르다”는 말은 “항상 Map을 쓰라”가 아니다. 원소가 몇 개 안 되는 고정 설정은 Object가 더 읽기 쉽고 충분히 빠르다. 반대로 요청마다 수천 개 membership test를 한다면 Set의 메모리 비용을 내고 시간을 줄이는 것이 합리적이다.

8-5. 첫 회독용 의사결정 절차

자료구조가 헷갈릴 때는 아래 순서로 좁힌다.

가장 많이 반복되는 연산을 하나 고른다.
그 연산이 위치 접근, 키 조회, 순서 처리, 범위 조회 중 무엇인지 분류한다.
입력 크기 n이 어느 정도까지 커질지 적는다.
시간 O(n)을 공간 O(n)으로 줄일 가치가 있는지 판단한다.
최악 입력이 장애가 될 수 있는지 확인한다.

예를 들어 “요청 1건에서 20,000개 주문 id가 허용 목록에 있는지 확인”해야 한다면, 허용 목록을 배열로 두고 includes를 20,000번 호출하는 것은 위험하다. 허용 목록을 Set으로 바꾸면 준비 비용 O(n)과 공간 O(n)을 내고, 각 확인을 평균 O(1)에 가깝게 줄인다.

9. Worked Examples

9-1. 중복 사용자 찾기: O(n^2)에서 O(n)으로

문제: 사용자 배열에서 이메일이 중복된 사용자를 찾는다.

type User = {
  id: string;
  email: string;
};

function findDuplicateUsersSlow(users: User[]) {
  const duplicates: User[] = [];

  for (const user of users) {
    for (const other of users) {
      if (user.id !== other.id && user.email === other.email) {
        duplicates.push(user);
      }
    }
  }

  return duplicates;
}

이 코드는 모든 사용자 쌍을 비교한다. 사용자가 10,000명이면 최대 100,000,000번 수준의 비교가 생긴다.

function findDuplicateUsers(users: User[]) {
  const firstByEmail = new Map<string, User>();
  const duplicates: User[] = [];

  for (const user of users) {
    if (firstByEmail.has(user.email)) {
      duplicates.push(user);
      continue;
    }

    firstByEmail.set(user.email, user);
  }

  return duplicates;
}

이 버전은 각 사용자를 한 번씩만 본다. Map은 “이 이메일을 본 적 있는가?”라는 질문을 평균 O(1)에 처리한다. 시간 O(n)을 얻는 대신 이메일 개수만큼 공간 O(n)을 쓴다.

9-2. Two Sum: 보수를 기억한다

배열에서 합이 target인 두 수의 인덱스를 찾는다.

function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }

    seen.set(nums[i], i);
  }

  return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

핵심은 “현재 값과 더해 target이 되는 보수가 이미 나왔는가?”다. 이 질문을 배열에서 찾으면 O(n)이지만, Map에 저장해 두면 평균 O(1)이다.

9-3. 고정 윈도우 합: 매번 다시 더하지 않는다

크기 k인 연속 구간의 최대 합을 구한다.

function maxSubarraySum(nums: number[], k: number): number {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

  for (let right = k; right < nums.length; right++) {
    windowSum += nums[right];
    windowSum -= nums[right - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // 9

매 위치마다 k개를 다시 더하면 O(nk)다. 하지만 오른쪽으로 한 칸 이동할 때 새 값 하나를 더하고 왼쪽 값 하나를 빼면 O(n)이 된다. 여기서 중요한 자료구조는 거대한 라이브러리가 아니라 “현재 윈도우의 상태를 유지하는 변수”다.

9-4. 선택 확장: 단조 Stack으로 다음 큰 값 찾기

각 원소의 오른쪽에서 처음 만나는 더 큰 값을 찾는다.

function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }

    stack.push(i);
  }

  return result;
}

console.log(nextGreaterElement([2, 1, 2, 4, 3]));
// [4, 2, 4, -1, -1]

스택에는 아직 답을 찾지 못한 인덱스가 들어 있다. 현재 값이 스택 top의 값보다 크면, 현재 값이 그 원소의 다음 큰 값이다. 각 인덱스는 한 번 push되고 한 번 pop되므로 전체 O(n)이다.

10. 직접 확인해보기

10-1. O(1) 접근과 O(n) 탐색 비교

function measureTime(fn, label) {
  const start = performance.now();
  fn();
  const end = performance.now();
  console.log(`${label}: ${(end - start).toFixed(3)}ms`);
}

const n = 100_000;
const arr = Array.from({ length: n }, (_, i) => i);

measureTime(() => arr[n - 1], "O(1) index access");
measureTime(() => arr.find((x) => x === n - 1), "O(n) linear search");

예상 패턴:

O(1) index access: 매우 작음
O(n) linear search: 입력 크기에 따라 증가

정확한 ms는 장비와 런타임에 따라 달라진다. 중요한 것은 입력을 10배 늘렸을 때 선형 탐색 시간이 대체로 함께 커진다는 점이다.

10-2. `shift()`와 head index 비교

function measureShiftVsPointer(size) {
  const arr1 = Array.from({ length: size }, (_, i) => i);
  const start1 = performance.now();
  while (arr1.length) arr1.shift();
  const time1 = performance.now() - start1;

  const arr2 = Array.from({ length: size }, (_, i) => i);
  let head = 0;
  const start2 = performance.now();
  while (head < arr2.length) head++;
  const time2 = performance.now() - start2;

  console.log(
    `n=${size}: shift=${time1.toFixed(1)}ms, pointer=${time2.toFixed(1)}ms`,
  );
}

measureShiftVsPointer(10_000);
measureShiftVsPointer(100_000);

예상 패턴:

n=10,000: shift는 pointer보다 크게 느림
n=100,000: shift 쪽 증가폭이 훨씬 큼

이 실험은 큐를 배열로 만들 때 shift()를 조심해야 하는 이유를 보여준다.

환경마다 수치는 달라지지만, 100,000개 정도부터 shift() 반복은 수백 ms에서 수 초까지 튈 수 있고 head index 방식은 보통 몇 ms 수준에 머무는 식으로 차이가 커진다. 숫자 자체보다 입력을 10배 늘렸을 때 증가폭이 어느 쪽에서 폭발하는지를 본다.

10-3. `Array.includes`와 `Set.has` 비교

const N = 100_000;
const values = Array.from({ length: N }, (_, i) => i);
const valueSet = new Set(values);
const target = N - 1;

console.time("Array.includes");
for (let i = 0; i < 1_000; i++) {
  values.includes(target);
}
console.timeEnd("Array.includes");

console.time("Set.has");
for (let i = 0; i < 1_000; i++) {
  valueSet.has(target);
}
console.timeEnd("Set.has");

기존 문서의 실측 예시는 Array.includes 1,000회가 약 320ms, Set.has 1,000회가 약 0.8ms 수준으로 차이가 났다. 환경마다 수치는 달라도 “끝 값을 반복 탐색하는 배열”과 “해시 기반 조회”의 성장 차이는 유지된다.

10-4. Map과 Object 키 차이 확인

const map = new Map();
map.set(1, "number");
map.set("1", "string");
map.set(true, "boolean");

console.log(map.size);
console.log(map.get(1));
console.log(map.get("1"));

const obj = {};
obj[1] = "number";
obj["1"] = "string";

console.log(Object.keys(obj));
console.log(obj[1]);

예상 출력:

3
number
string
["1"]
string

Object는 키 변환 때문에 1과 "1"을 같은 키로 취급한다. Map은 둘을 다른 키로 본다.

10-5. 해시 충돌 직접 확인

function simpleHash(key, size) {
  let hash = 0;
  for (const char of key) {
    hash = (hash + char.charCodeAt(0)) % size;
  }
  return hash;
}

const tableSize = 5;
const keys = ["name", "mane", "amen", "age", "gap"];
const buckets = {};

for (const key of keys) {
  const index = simpleHash(key, tableSize);
  buckets[index] ??= [];
  buckets[index].push(key);
}

for (const [index, items] of Object.entries(buckets)) {
  const collision = items.length > 1 ? " collision" : "";
  console.log(`bucket[${index}]: ${items.join(", ")}${collision}`);
}

예상 패턴:

bucket[0]: name, mane, amen collision
bucket[3]: age, gap collision

충돌 자체는 실패가 아니다. 해시 테이블은 충돌이 생길 수 있다는 전제로 설계된다. 실패는 충돌이 특정 버킷에 과도하게 몰리고, 그 결과 평균 O(1)로 기대한 조회가 O(n)에 가까워지는 것이다.

11. 실패 신호로 복습하기

이 절은 긴 트러블슈팅 런북이 아니라, 증상을 자료구조 개념으로 연결하는 복습표다.

p99는 전체 요청 중 느린 상위 1%가 시작되는 지연 시간이고, p999는 느린 상위 0.1%가 시작되는 지연 시간이다. 평균은 정상인데 p99/p999만 튀면 특정 입력 패턴이나 특정 자료구조 경계가 일부 요청만 망가뜨리고 있을 가능성이 높다.

증상	의미	먼저 의심할 개념
데이터가 커질수록 앞 삽입이 급격히 느려진다	`unshift`가 매번 기존 값을 이동한다	Array 앞 삽입 O(n), Deque
BFS가 작은 입력은 빠른데 큰 입력에서 시간 초과가 난다	`shift()` 기반 Queue가 O(n^2)를 만든다	Queue head pointer
”Map에 넣었는데 조회가 안 된다”	객체 키를 새로 만들어 참조가 달라졌다	Map key equality
`obj[1]`과 `obj["1"]`이 덮어써진다	Object 키가 문자열로 변환된다	Object key coercion
평균 응답은 정상인데 p99만 특정 입력에서 튄다	특정 키 패턴이 해시 충돌을 만들 수 있다	Hash collision, Hash DoS
`Set`/`Map` 캐시가 계속 커진다	항목을 제거하지 않아 메모리가 누적된다	공간 복잡도, TTL, WeakMap
Hash Table로 범위 조회를 구현했더니 전체 스캔한다	해시 구조에는 정렬 불변식이 없다	Tree/정렬 배열/B-Tree
Linked List로 바꿨는데 순회가 더 느리다	포인터 추적과 캐시 미스가 커졌다	메모리 지역성
`push`는 빠른데 가끔 튄다	동적 배열 재할당이 발생했다	amortized O(1)

11-1. Map/Set 메모리 누수 예시

WeakMap은 객체뿐 아니라 전역 Symbol registry에 등록되지 않은 Symbol도 키로 받을 수 있다. Symbol.for()로 만든 전역 등록 Symbol과 문자열·숫자·boolean·bigint·null·undefined 같은 다른 primitive는 키로 쓸 수 없다. WeakMap은 이런 키를 강하게 붙잡아 살려 두지 않으므로 다른 곳에서 더 이상 도달할 수 없으면 GC(Garbage Collection, 가비지 컬렉션)가 항목을 회수할 수 있지만, 회수 시점은 보장되지 않는다. 명시적인 만료 정책이나 통계가 필요하면 Map + TTL cleanup이 더 읽기 쉽다. TTL(Time To Live)은 항목을 얼마 동안만 유효하게 둘지 정한 시간이고, cleanup은 만료된 항목을 주기적으로 지우는 작업이다.

class RequestTracker {
  private requestData = new Map<string, { data: unknown; expiry: number }>();

  track(requestId: string, data: unknown, ttlMs = 60_000) {
    this.requestData.set(requestId, {
      data,
      expiry: Date.now() + ttlMs,
    });
  }

  cleanup() {
    const now = Date.now();

    for (const [key, value] of this.requestData) {
      if (value.expiry < now) {
        this.requestData.delete(key);
      }
    }
  }
}

여기서 중요한 것은 NestJS 클래스가 아니라 실패 원리다. Map은 값을 빠르게 찾게 해주지만 자동으로 오래된 값을 지워주지 않는다. 모듈 스코프나 싱글턴 객체에 Map을 두면 수명도 길어진다. 따라서 캐시, 요청 추적, rate limit 카운터에는 TTL, 최대 크기, 주기적 삭제 같은 수명 정책이 필요하다.

12. 핵심 키워드

키워드	한 줄 설명
자료구조	데이터 배치, 접근 방식, 불변식, 비용을 함께 정한 구조
Big-O	입력 크기 증가에 따른 시간·공간 비용의 성장률
시간 복잡도	연산 횟수가 입력 크기에 따라 어떻게 증가하는지
공간 복잡도	추가 메모리 사용량이 입력 크기에 따라 어떻게 증가하는지
분할 상환	가끔 비싼 연산을 여러 번의 연산에 나눠 평균낸 비용
Array	연속 배치와 인덱스 접근에 강한 구조
Dynamic Array	크기를 늘릴 수 있는 배열, `push` 평균 O(1)
Linked List	노드가 다음 노드를 참조하는 구조
포인터/참조	다른 값이나 노드의 위치를 가리키는 정보
Stack	LIFO, 마지막에 들어온 값을 먼저 꺼내는 구조
Queue	FIFO, 먼저 들어온 값을 먼저 꺼내는 구조
Deque	양쪽 끝에서 삽입·삭제가 가능한 큐
Hash Function	키를 해시값으로 바꾸는 함수
Bucket	해시 테이블에서 값이 저장되는 칸
Hash Collision	서로 다른 키가 같은 버킷으로 가는 현상
Chaining	충돌 항목을 같은 버킷에 연결해 저장하는 방식
Open Addressing	충돌 시 테이블 안의 다른 슬롯을 찾는 방식
Load Factor	저장 항목 수와 버킷 수의 비율
Map	JavaScript의 해시 기반 키-값 컬렉션
Set	중복 없는 값 컬렉션, membership test에 강함
TypedArray	숫자를 고정 타입 연속 메모리로 저장하는 배열 계열

13. 체크리스트