들어가며
"자료구조? 그거 학교에서나 배우는 거 아니야?"
실무에서 코딩만 하면 되지, 왜 자료구조를 알아야 하는지 의문을 가진 적 있으신가요? 저도 처음에는 그랬습니다. 하지만 자료구조는 단순히 이론이 아닙니다. 우리가 매일 작성하는 코드의 효율성과 직결되는 실전 개념입니다.
컴퓨터의 메모리는 무한해 보이지만, 사실은 매우 한정적입니다. 이 한정된 공간에서 데이터를 어떻게 효율적으로 저장하고 관리할 것인가. 이것이 바로 자료구조를 배우는 이유입니다.
오늘은 실무에서 가장 많이 사용되는 4가지 핵심 자료구조를 알아보겠습니다.
1. 스택 (Stack): 드럼통처럼 쌓이는 구조
스택이란?
스택을 이해하는 가장 쉬운 방법은 드럼통을 떠올리는 것입니다. 드럼통에 물건을 하나씩 넣으면 위로 쌓이죠? 꺼낼 때는 가장 나중에 넣은 것부터 꺼내게 됩니다.
이것이 바로 스택의 핵심 원리입니다: LIFO (Last In, First Out) - 마지막에 들어간 것이 먼저 나옵니다.
스택의 기본 연산
// 스택의 주요 연산
interface Stack<T> {
push(item: T): void; // 삽입: 스택에 아이템 추가
pop(): T | undefined; // 삭제: 스택에서 아이템 제거
peek(): T | undefined; // 조회: 최상단 아이템 확인 (제거 X)
}동작 방식 예시:
1. push('A') → [A]
2. push('B') → [A, B]
3. push('C') → [A, B, C]
4. pop() → [A, B] // C 반환
5. pop() → [A] // B 반환
6. pop() → [] // A 반환스택, 실제로 어디에 쓰일까?
1) 함수 호출 (Call Stack)
우리가 매일 사용하는 함수 호출이 바로 스택 구조입니다.
function main() {
console.log(bar(6));
}
function bar(num: number) {
return foo(num);
}
function foo(num: number) {
return num * 2 + 16;
}
main();실행 과정:
1. [main] 실행 시작
2. [main, console.log] console.log 호출
3. [main, console.log, bar] bar(6) 호출
4. [main, console.log, bar, foo] foo(6) 호출
5. [main, console.log, bar] foo 종료, 28 반환
6. [main, console.log] bar 종료, 28 반환
7. [main] console.log 종료, 28 출력
8. [] main 종료2) 브라우저의 뒤로 가기
브라우저에서 뒤로 가기를 누르면 가장 최근에 방문한 페이지가 나옵니다. 이것도 스택 구조입니다.
방문 순서: 페이지A → 페이지B → 페이지C
뒤로 가기: 페이지C → 페이지B → 페이지A3) 계산기 프로그램
수식을 계산할 때 괄호 처리도 스택으로 구현됩니다. 괄호를 만나면 스택에 저장하고, 닫는 괄호를 만나면 꺼내서 계산하는 방식이죠.
Stack Overflow란?
개발자라면 한 번쯤 들어본 "Stack Overflow" 웹사이트. 로고를 자세히 보면 스택 모양에 여러 블록이 쌓여있는 걸 볼 수 있습니다.
Stack Overflow 에러는 언제 발생할까?
프로그램 실행 시 할당된 스택 공간을 초과하면 발생합니다.
// 종료 조건이 없는 재귀 함수
function infiniteRecursion() {
infiniteRecursion(); // Stack Overflow!
}함수가 무한정 호출되면 콜 스택이 계속 쌓이다가 결국 메모리 한계를 넘어 에러가 발생합니다.
면접 팁
스택은 면접에서 자주 나오는 주제입니다. "스택을 코드로 구현해보세요"라는 문제가 단골 질문이니, 배열이나 연결 리스트로 스택을 직접 구현해보는 연습을 추천합니다.
2. 큐 (Queue): 줄 서는 사람들처럼
큐란?
큐는 줄을 서서 기다리는 사람들을 떠올리면 됩니다. 먼저 온 사람이 먼저 나가는 구조죠.
이것이 큐의 핵심 원리입니다: FIFO (First In, First Out) - 먼저 들어간 것이 먼저 나옵니다.
큐의 기본 연산
interface Queue<T> {
enqueue(item: T): void; // 삽입: 큐의 뒤에 아이템 추가
dequeue(): T | undefined; // 삭제: 큐의 앞에서 아이템 제거
front(): T | undefined; // 맨 앞 아이템 확인
rear(): T | undefined; // 맨 뒤 아이템 확인
}동작 방식 예시:
enqueue → [1] → [1, 2] → [1, 2, 3]
↓
dequeue
↓
[2, 3] → [3] → []- Front: 다음에 나갈 아이템 (맨 앞)
- Rear: 방금 들어온 아이템 (맨 뒤)
- Front와 Rear가 같으면 → 큐가 비어있는 상태
큐, 실제로 어디에 쓰일까?
1) JavaScript 이벤트 루프 (Callback Queue)
JavaScript 엔진은 내부적으로 큐를 사용합니다.
Call Stack: 함수 실행
↓
Web API: 비동기 작업 처리
↓
Callback Queue: 완료된 작업 대기 (큐!)
↓
Event Loop: 큐에서 하나씩 꺼내 실행console.log('1');
setTimeout(() => {
console.log('2'); // Callback Queue에 등록
}, 0);
console.log('3');
// 출력 순서: 1 → 3 → 2
// setTimeout의 콜백은 큐에서 대기했다가 실행됨2) 티켓팅 시스템
인터파크 같은 티켓 예매 사이트도 큐를 사용합니다. 먼저 클릭한 사람이 먼저 티켓을 구매할 수 있어야 하니까요.
// 티켓 예매 시스템 (의사 코드)
const ticketQueue = new Queue<User>();
// 사용자 클릭 순서대로 큐에 추가
ticketQueue.enqueue(user1);
ticketQueue.enqueue(user2);
ticketQueue.enqueue(user3);
// 순서대로 처리
while (!ticketQueue.isEmpty()) {
const user = ticketQueue.dequeue();
processTicket(user);
}3) 프린터 대기열
여러 문서를 출력할 때도 큐가 사용됩니다. 먼저 요청한 문서부터 인쇄되죠.
실습 추천
큐도 배열과 연결 리스트 두 가지 방법으로 구현해보세요. 각각의 장단점을 직접 느낄 수 있습니다.
3. 연결 리스트 (Linked List): 손으로 연결된 사람들
배열의 한계
큐와 스택을 설명하면서 "배열로도 만들 수 있고, 연결 리스트로도 만들 수 있다"고 했는데요. 그럼 연결 리스트는 뭘까요?
먼저 배열의 문제점을 봅시다.
배열의 메모리 구조:
메모리: [A][B][C][D][E] - 연속된 공간
인덱스: 0 1 2 3 4배열은 메모리상에서 연속적으로 저장됩니다. 이게 문제가 되는 순간이 있습니다.
상황: 배열에 100개 요소를 추가하고 싶은데,
뒤쪽 메모리 공간이 이미 다른 데이터로 차있음
해결: 1. 더 큰 연속된 공간 찾기
2. 기존 데이터 전부 복사
3. 새 위치에 저장
→ 비효율적!연결 리스트란?
연결 리스트는 손으로 연결된 사람들처럼 각 데이터가 다음 데이터의 위치를 기억하는 구조입니다.
// 노드 구조
interface Node<T> {
data: T; // 실제 데이터
next: Node<T>; // 다음 노드의 위치 (포인터)
}메모리 구조 비교:
배열:
메모리 주소: [100][101][102][103] - 연속적
데이터: [A] [B] [C] [D]
연결 리스트:
메모리 주소: [100] [305] [152] [200] - 불연속
데이터: [A|305] [B|152] [C|200] [D|null]
↓ ↓ ↓
다음 위치 다음 위치 다음 위치연결 리스트의 장점: 삽입과 삭제
중간에 데이터 추가하기:
// 배열: O(n) - 뒤의 모든 요소를 이동해야 함
const arr = [1, 2, 3, 4];
arr.splice(2, 0, 99); // [1, 2, 99, 3, 4]
// 연결 리스트: O(1) - 포인터만 수정
// B와 C 사이에 X 추가
// 기존: A → B → C → D
// 1. B의 next를 X로 변경
// 2. X의 next를 C로 설정
// 결과: A → B → X → C → D데이터 삭제하기:
// 연결 리스트에서 B 삭제
// 기존: A → B → C → D
// A의 next를 C로 변경
// 결과: A → C → D (B는 참조가 끊겨 자동 삭제)단순 vs 이중 연결 리스트
단순 연결 리스트 (Singly Linked List):
A → B → C → D → null
(한 방향으로만 이동 가능)이중 연결 리스트 (Doubly Linked List):
null ← A ⇄ B ⇄ C ⇄ D → null
(양방향으로 이동 가능)이중 연결 리스트는 양방향 탐색이 가능하지만, 각 노드가 이전/다음 두 개의 포인터를 가져야 하므로 메모리를 더 사용합니다.
배열 vs 연결 리스트 비교
| 특성 | 배열 | 연결 리스트 |
|---|---|---|
| 메모리 할당 | 연속적 (고정 크기) | 비연속적 (동적 크기) |
| 삽입/삭제 | 느림 O(n) | 빠름 O(1) |
| 접근/탐색 | 빠름 O(1) | 느림 O(n) |
| 메모리 효율 | 높음 (데이터만) | 낮음 (포인터 추가) |
| 구현 복잡도 | 간단 | 복잡 (포인터 관리) |
언제 무엇을 사용할까?
// 배열이 좋은 경우
const users = [user1, user2, user3];
const thirdUser = users[2]; // 인덱스로 즉시 접근
// → 탐색이 많고, 크기가 고정적일 때
// 연결 리스트가 좋은 경우
// → 삽입/삭제가 빈번하고, 크기가 동적으로 변할 때
// 예: 음악 재생 목록, 브라우저 히스토리실무에서의 연결 리스트
솔직히 말하면, 실무에서 직접 연결 리스트를 구현할 일은 드뭅니다. 대부분 배열로 해결되고, 언어별로 제공하는 자료구조(JavaScript의 Array, Python의 List 등)가 내부적으로 최적화되어 있기 때문입니다.
하지만 연결 리스트의 개념을 이해하는 것은 중요합니다. 다른 자료구조(스택, 큐, 해시테이블)를 구현할 때 기반이 되기 때문이죠.
4. 해시 테이블 (Hash Table): 사전처럼 빠른 검색
선형 자료구조의 한계
배열이나 연결 리스트의 치명적인 단점이 있습니다. 데이터가 많아질수록 검색이 느려진다는 것입니다.
// 100만 개의 사용자 중 특정 사용자 찾기
const users = [...]; // 100만 개
const target = users.find(u => u.id === '12345');
// 최악의 경우 100만 번 비교 필요 😱이 문제를 해결하는 것이 바로 해시 테이블입니다.
해시 테이블이란?
해시 테이블은 사전과 비슷합니다. 사전에서 단어를 찾을 때, A부터 Z까지 전부 뒤지지 않죠? 'M'으로 시작하면 바로 중간쯤으로 건너뛰잖아요.
해시 테이블도 같은 원리입니다. 키(Key)를 해시 함수에 넣어 인덱스를 얻고, 그 위치에 바로 접근합니다.
해시 테이블의 구조
interface HashTable<K, V> {
set(key: K, value: V): void; // 저장
get(key: K): V | undefined; // 조회
delete(key: K): boolean; // 삭제
}
// 내부 구조
// Key → Hash Function → Index → Value동작 원리:
1. Key: "yuna"
↓
2. Hash Function: hash("yuna") → 2
↓
3. 테이블 인덱스 2에 저장: ["yuna", 15]
검색할 때:
1. hash("yuna") → 2
2. 인덱스 2 확인 → 즉시 찾음! O(1)예시 코드:
// 간단한 해시 테이블 구현
class SimpleHashTable {
private table: Array<[string, any][]>;
private size: number = 10;
constructor() {
this.table = new Array(this.size).fill(null).map(() => []);
}
// 해시 함수
private hash(key: string): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i)) % this.size;
}
return hash;
}
set(key: string, value: any): void {
const index = this.hash(key);
this.table[index].push([key, value]);
}
get(key: string): any {
const index = this.hash(key);
const bucket = this.table[index];
for (const [k, v] of bucket) {
if (k === key) return v;
}
return undefined;
}
}
// 사용
const hashTable = new SimpleHashTable();
hashTable.set("yuna", 15);
hashTable.set("yuri", 20);
console.log(hashTable.get("yuna")); // 15 - 즉시 찾음!충돌(Collision) 문제
해시 테이블의 가장 큰 문제는 충돌입니다. 서로 다른 키가 같은 인덱스를 가리킬 수 있습니다.
hash("john") → 2
hash("sandra") → 2 // 충돌!충돌 해결 방법
1) 체이닝 (Chaining)
같은 인덱스에 연결 리스트로 연결합니다.
인덱스 2: [john, 123] → [sandra, 456] → [ted, 789]
↓
연결 리스트class HashTableWithChaining {
private table: Array<Array<[string, any]>>;
set(key: string, value: any): void {
const index = this.hash(key);
// 같은 인덱스에 배열로 저장 (체이닝)
if (!this.table[index]) {
this.table[index] = [];
}
this.table[index].push([key, value]);
}
get(key: string): any {
const index = this.hash(key);
const bucket = this.table[index];
if (!bucket) return undefined;
// 연결된 리스트를 순회하며 찾기
for (const [k, v] of bucket) {
if (k === key) return v;
}
return undefined;
}
}2) 오픈 어드레싱 (Open Addressing)
충돌이 나면 다음 빈 공간을 찾아 저장합니다.
인덱스 1: [apple, 100]
인덱스 2: [banana, 200]
인덱스 3: [cherry, 300]
인덱스 4: [dragon, 400] ← 원래 인덱스는 1이었지만,
충돌로 인해 4에 저장class HashTableWithOpenAddressing {
private table: Array<[string, any] | null>;
set(key: string, value: any): void {
let index = this.hash(key);
// 빈 공간을 찾을 때까지 다음 인덱스 확인
while (this.table[index] !== null) {
index = (index + 1) % this.size;
}
this.table[index] = [key, value];
}
get(key: string): any {
let index = this.hash(key);
// 키를 찾을 때까지 순회
while (this.table[index] !== null) {
const [k, v] = this.table[index];
if (k === key) return v;
index = (index + 1) % this.size;
}
return undefined;
}
}해시 테이블, 어디에 쓰일까?
1) 신원 조회 시스템
// 대한민국 전체 국민 정보
const citizenDB = new Map<string, Citizen>();
// 주민등록번호로 즉시 검색
const person = citizenDB.get("123456-1234567"); // O(1)
// 100만 명이든 1억 명이든 속도 동일!2) 자동차 번호판 조회
const vehicleDB = new Map<string, Vehicle>();
vehicleDB.set("12가3456", { owner: "김철수", model: "소나타" });
// 번호판으로 즉시 조회
const car = vehicleDB.get("12가3456"); // O(1)3) 캐싱
const cache = new Map<string, string>();
function fetchData(url: string): string {
// 캐시에 있으면 즉시 반환
if (cache.has(url)) {
return cache.get(url)!;
}
// 없으면 가져와서 저장
const data = expensiveFetch(url);
cache.set(url, data);
return data;
}왜 데이터베이스는 해시 테이블을 안 쓸까?
해시 테이블이 이렇게 빠른데, 데이터베이스 인덱스로 쓰면 좋지 않을까요?
안타깝게도 아닙니다. 이유는 범위 검색 때문입니다.
// 해시 테이블은 정확한 값 검색에 최적화
userTable.get("user123"); // ✅ 빠름
// 범위 검색은 비효율적
// "2023-01-01부터 2023-12-31까지의 주문"
// → 모든 날짜를 하나씩 해시해서 찾아야 함 ❌
for (let date = start; date <= end; date++) {
const orders = orderTable.get(date.toString());
}데이터베이스는 범위 검색이 많기 때문에, 해시 테이블 대신 B-Tree라는 자료구조를 주로 사용합니다.
JavaScript의 Map과 Object
JavaScript에서는 해시 테이블이 이미 구현되어 있습니다.
// Object (제한적인 해시 테이블)
const obj = {
name: "John",
age: 30
};
// Map (완전한 해시 테이블)
const map = new Map<string, number>();
map.set("apple", 100);
map.set("banana", 200);
console.log(map.get("apple")); // 100 - O(1)Map vs Object:
// Object의 한계
const obj = {};
obj[123] = "숫자 키"; // 문자열로 변환됨
obj[{ id: 1 }] = "객체 키"; // "[object Object]"로 변환
// Map은 모든 타입 가능
const map = new Map();
map.set(123, "숫자 키");
map.set({ id: 1 }, "객체 키"); // 객체를 키로 사용 가능!마치며
오늘 살펴본 4가지 자료구조는 각각 고유한 특성과 용도가 있습니다.
| 자료구조 | 특징 | 주요 용도 | 시간 복잡도 |
|---|---|---|---|
| 스택 | LIFO | 함수 호출, 실행 취소 | O(1) |
| 큐 | FIFO | 이벤트 처리, 대기열 | O(1) |
| 연결 리스트 | 동적 크기 | 삽입/삭제 빈번한 경우 | 삽입: O(1), 탐색: O(n) |
| 해시 테이블 | Key-Value | 빠른 검색 | O(1) 평균 |
실무 팁:
- 대부분의 경우 배열로 충분합니다. JavaScript의 Array는 매우 최적화되어 있습니다.
- 빠른 검색이 필요하면 Map을 사용하세요. Object보다 더 강력합니다.
- 면접 준비는 직접 구현해보세요. 각 자료구조를 TypeScript로 구현하는 연습이 도움됩니다.
자료구조는 단순히 이론이 아닙니다. 우리가 매일 작성하는 코드 속에 숨어있고, 성능을 좌우하는 핵심 요소입니다.
다음 포스트에서는 트리(Tree) 구조에 대해 알아보겠습니다. B-Tree가 왜 데이터베이스에서 사용되는지, 이진 탐색 트리는 무엇인지 자세히 다룰 예정입니다.
관련 글:
- Big O 표기법 완벽 가이드: 알고리즘 성능을 측정하는 개발자 필수 개념
- 트리 자료구조 완벽 정리 (다음 편 예고)
'자료구조' 카테고리의 다른 글
| 연결 리스트(Linked List) 완전 정복: 메모리 효율적인 동적 자료구조의 모든 것 (5) | 2025.06.20 |
|---|---|
| 두 개의 스택으로 큐(Queue) 구현하기: 실전 면접에서 마주한 낯선 자료구조 문제 (0) | 2025.06.17 |
| Deque : 양방향 큐의 모든 것 (0) | 2025.05.30 |