배열·링크드리스트·스택·큐
메모리 연속(배열) vs 포인터 연결(리스트), LIFO(스택), FIFO(큐) — 선형 자료구조 4형제.
작업 실행 순서·히스토리·BFS 방문 대기 — 기본 자료구조를 맞게 고르면 코드가 훨씬 깨끗해진다. 같은 Big O라도 캐시 지역성에 따라 수십 배 차이(ch13-4 참고).
배열(Array)은 RAM에 연속 배치된 저장공간. 인덱스로 즉시 접근 O(1), 중간 삽입/삭제 O(n). 링크드리스트는 각 원소가 다음 원소 주소를 포인터로 가리키는 구조. 중간 삽입/삭제 O(1)이지만 인덱스 접근 O(n).
| 연산 | 배열 | 링크드리스트 |
|---|---|---|
| 인덱스 접근 | O(1) | O(n) |
| 맨 끝 삽입 | 평균 O(1)*(amortized) | O(1) (tail 포인터 시) |
| 중간 삽입/삭제 | O(n) (시프트) | O(1) (포인터만) |
| 메모리 지역성 | ✅ 캐시 친화 | ❌ 여기저기 |
| 현대 기본 선택 | 배열(대부분) | 드물게(큐·덱 구현 내부) |
현대 실무에서는 배열이 거의 항상 정답. 링크드리스트는 이론적 이점이 있어도 캐시 미스 때문에 실제로 배열보다 느린 경우 많음. 배열 기반 동적 배열(JS Array, Python list, Java ArrayList)이 디폴트.
스택(Stack)은 LIFO(Last-In-First-Out) — 접시 더미. push/pop만 가능. 큐(Queue)는 FIFO(First-In-First-Out) — 줄 서기. enqueue/dequeue.
// ━━━ 스택 (JS 배열로 그대로) ━━━
const stack = [];
stack.push("A");
stack.push("B");
stack.pop(); // "B" (마지막이 먼저 나옴)
// 실전: 함수 호출 스택, 실행 취소(Undo), 괄호 매칭
function isBalanced(s) {
const stack = [];
for (const c of s) {
if ("({[".includes(c)) stack.push(c);
else if (")}]".includes(c)) {
const top = stack.pop();
if (!matches(top, c)) return false;
}
}
return stack.length === 0;
}
// ━━━ 큐 ━━━
// JS: shift()는 O(n) → 대량이면 deque 라이브러리 or 인덱스 포인터
const queue = [];
queue.push("A"); // enqueue
queue.push("B");
queue.shift(); // "A" (먼저 들어간 게 먼저)
// Python: collections.deque 사용
// from collections import deque
// q = deque(); q.append(x); q.popleft()
// 실전: BFS 방문 대기(ch17-4), 작업 큐(Redis BullMQ), 프린터 큐JS는 스택/큐 전용 자료형 없이 배열로 대용. 대량 데이터의 큐 `shift()`는 O(n)이라 느릴 수 있음 → 앞쪽 포인터 유지 패턴이나 deque 라이브러리.
덱(Deque, Double-Ended Queue)은 양 끝 모두 O(1) 삽입/삭제. Python `collections.deque`가 표준 구현. 슬라이딩 윈도우·최근 N개 캐시에 자주 등장.
LIFO 구조로, 가장 나중에 들어간 원소가 먼저 나오는 자료구조는?
링크드리스트는 캐시 지역성이 배열보다 좋다.