이미지 로딩 중...
AI Generated
2025. 11. 6. · 6 Views
배열 기반 vs 연결 리스트 기반 자료구조 완벽 가이드
배열과 연결 리스트 기반 자료구조의 차이를 실무 관점에서 비교하고, 각각의 장단점과 최적의 사용 시나리오를 코드 예제와 함께 상세히 설명합니다. 성능 특성을 이해하고 올바른 선택을 할 수 있도록 도와드립니다.
목차
- 배열 기반 자료구조의 기초 - 연속된 메모리 공간의 힘
- 연결 리스트 기반 자료구조의 기초 - 유연한 포인터의 세계
- 성능 비교 - 시간 복잡도로 보는 실전 선택 가이드
- 메모리 특성 - 캐시와 메모리 레이아웃의 비밀
- Stack 구현 비교 - 배열 vs 연결 리스트로 만드는 스택
- Queue 구현 비교 - 효율적인 큐의 선택
- 실무 선택 기준 - 언제 배열을, 언제 연결 리스트를 사용할까
- JavaScript 특화 고려사항 - 언어 특성과 최적화
1. 배열 기반 자료구조의 기초 - 연속된 메모리 공간의 힘
시작하며
여러분이 사용자 목록을 관리하는 기능을 개발할 때, 특정 사용자의 정보를 빠르게 조회해야 하는 상황을 겪어본 적 있나요? 예를 들어, 10만 명의 사용자 중 ID가 50000인 사용자의 정보를 즉시 가져와야 한다면 어떻게 하시겠습니까?
이런 문제는 실제 개발 현장에서 자주 발생합니다. 데이터 접근 속도가 느리면 사용자 경험이 저하되고, 서버 응답 시간이 길어져 전체 시스템 성능에 영향을 미칩니다.
특히 대용량 데이터를 다루는 서비스에서는 자료구조 선택이 성능을 좌우하는 핵심 요소가 됩니다. 바로 이럴 때 필요한 것이 배열 기반 자료구조입니다.
배열은 연속된 메모리 공간에 데이터를 저장하여 인덱스를 통한 즉각적인 접근(O(1) 시간 복잡도)을 가능하게 합니다.
개요
간단히 말해서, 배열 기반 자료구조는 연속된 메모리 주소에 데이터를 순차적으로 저장하는 방식입니다. 마치 아파트 호수처럼 각 데이터가 고유한 인덱스 번호를 가지고 있어서, 그 번호만 알면 즉시 찾을 수 있습니다.
배열이 필요한 이유는 명확합니다. 랜덤 액세스가 빈번한 애플리케이션에서는 데이터 조회 속도가 생명입니다.
예를 들어, 게임에서 플레이어의 인벤토리 아이템을 슬롯 번호로 즉시 접근하거나, 주식 거래 시스템에서 특정 시점의 가격 데이터를 빠르게 조회하는 경우에 매우 유용합니다. 전통적인 방법과의 비교를 해보겠습니다.
기존에 순차적으로 데이터를 탐색하며 찾았다면, 이제는 인덱스 계산을 통해 메모리 주소로 직접 점프할 수 있습니다. 이는 마치 책의 목차를 보고 원하는 페이지로 바로 가는 것과 같습니다.
배열의 핵심 특징은 다음과 같습니다: 첫째, O(1) 시간에 인덱스로 접근 가능합니다. 둘째, 캐시 지역성이 뛰어나 CPU 캐시 효율이 높습니다.
셋째, 메모리 오버헤드가 최소화됩니다(데이터만 저장). 이러한 특징들이 중요한 이유는 현대 컴퓨터 아키텍처에서 메모리 접근 패턴이 성능에 직접적인 영향을 미치기 때문입니다.
코드 예제
// 배열 기반 자료구조 구현 - 동적 배열(Dynamic Array)
class DynamicArray {
constructor() {
this.data = new Array(2); // 초기 용량 2
this.size = 0; // 실제 저장된 요소 개수
this.capacity = 2; // 현재 배열 용량
}
// O(1) 평균 시간 복잡도 - 재할당이 필요할 때만 O(n)
push(value) {
if (this.size === this.capacity) {
this._resize(this.capacity * 2); // 용량 2배 증가
}
this.data[this.size] = value;
this.size++;
}
// O(1) 시간 복잡도 - 인덱스 직접 접근
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('Index out of bounds');
}
return this.data[index];
}
// O(n) 시간 복잡도 - 모든 요소를 새 배열로 복사
_resize(newCapacity) {
const newData = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
// O(n) 시간 복잡도 - 중간 삽입 시 뒤의 요소들을 이동
insertAt(index, value) {
if (index < 0 || index > this.size) {
throw new Error('Index out of bounds');
}
if (this.size === this.capacity) {
this._resize(this.capacity * 2);
}
// 뒤에서부터 한 칸씩 이동
for (let i = this.size; i > index; i--) {
this.data[i] = this.data[i - 1];
}
this.data[index] = value;
this.size++;
}
}
설명
이것이 하는 일: 위 코드는 JavaScript에서 동적 배열을 구현한 것으로, 고정 크기의 배열을 내부적으로 사용하면서 필요에 따라 자동으로 크기를 조정합니다. 이는 C++의 vector나 Java의 ArrayList와 동일한 개념입니다.
첫 번째로, 생성자에서는 초기 용량 2의 배열을 생성합니다. 이렇게 작은 크기로 시작하는 이유는 메모리를 절약하기 위함입니다.
size는 실제로 저장된 요소의 개수를, capacity는 현재 할당된 배열의 크기를 추적합니다. 이 두 값의 차이가 중요한데, 이를 통해 언제 재할당이 필요한지 판단할 수 있습니다.
그 다음으로, push 메서드가 실행되면서 크기 관리가 이루어집니다. size가 capacity와 같아지면 _resize를 호출하여 용량을 2배로 늘립니다.
이러한 "배수 증가" 전략은 분할 상환 분석(amortized analysis)에서 O(1) 평균 시간을 보장합니다. 대부분의 push 연산은 단순히 배열에 값을 추가하기만 하므로 매우 빠릅니다.
get 메서드는 배열의 진정한 강점을 보여줍니다. 인덱스를 사용하여 메모리 주소를 직접 계산(base_address + index * element_size)하므로 데이터의 위치와 상관없이 항상 동일한 시간이 걸립니다.
이는 연결 리스트가 O(n) 시간이 걸리는 것과 대조적입니다. insertAt 메서드는 배열의 약점을 보여줍니다.
중간에 요소를 삽입하려면 해당 위치 뒤의 모든 요소를 한 칸씩 뒤로 이동해야 합니다. 10만 개의 요소가 있는 배열의 맨 앞에 삽입하려면 10만 번의 이동 연산이 필요합니다.
이것이 배열의 가장 큰 단점입니다. 여러분이 이 코드를 사용하면 다음과 같은 이점을 얻을 수 있습니다.
첫째, 메모리 사용량을 최소화하면서도 빠른 접근 속도를 유지합니다. 둘째, 캐시 친화적인 메모리 레이아웃 덕분에 순차 접근 시 성능이 극대화됩니다.
셋째, 데이터가 연속적으로 저장되어 있어 메모리 단편화가 발생하지 않습니다.
실전 팁
💡 배열의 초기 용량을 예상 크기로 설정하면 재할당 비용을 크게 줄일 수 있습니다. 1000개의 요소를 저장할 것을 안다면 처음부터 new Array(1000)으로 시작하세요.
💡 중간 삽입/삭제가 빈번하다면 배열 대신 연결 리스트를 고려하세요. 배열은 끝에서의 추가/제거(push/pop)에는 O(1)이지만 중간 연산은 O(n)입니다.
💡 JavaScript의 내장 Array는 이미 동적 배열로 구현되어 있으므로, 대부분의 경우 직접 구현할 필요가 없습니다. 하지만 이 원리를 이해하면 성능 최적화에 도움이 됩니다.
💡 배열을 순회할 때는 for 루프가 forEach나 map보다 빠릅니다. 성능이 중요한 경우 기본 for 루프를 사용하세요.
💡 TypedArray(Int32Array, Float64Array 등)를 사용하면 메모리 사용량을 더욱 줄이고 성능을 향상시킬 수 있습니다. 특히 대량의 숫자 데이터를 다룰 때 유용합니다.
2. 연결 리스트 기반 자료구조의 기초 - 유연한 포인터의 세계
시작하며
여러분이 음악 재생 목록을 구현할 때, 사용자가 중간에 노래를 추가하거나 삭제하는 작업이 빈번하게 일어나는 상황을 생각해보세요. 배열을 사용하면 매번 수천 개의 요소를 이동시켜야 할 수도 있습니다.
이런 문제는 삽입과 삭제가 자주 발생하는 모든 애플리케이션에서 발생합니다. 작업 큐, 실행 취소/다시 실행 기능, 브라우저 히스토리 등이 대표적인 예입니다.
배열을 사용하면 단순한 삽입/삭제 작업에도 많은 비용이 듭니다. 바로 이럴 때 필요한 것이 연결 리스트 기반 자료구조입니다.
각 노드가 다음 노드를 가리키는 포인터를 가지고 있어, 포인터만 변경하면 O(1) 시간에 삽입과 삭제가 가능합니다.
개요
간단히 말해서, 연결 리스트는 각 요소(노드)가 데이터와 다음 노드를 가리키는 포인터를 함께 저장하는 방식입니다. 마치 보물찾기처럼 각 노드가 "다음은 여기로 가세요"라는 정보를 가지고 있는 구조입니다.
연결 리스트가 필요한 이유는 동적인 데이터 관리에 있습니다. 데이터의 크기를 미리 알 수 없거나, 삽입과 삭제가 빈번한 경우에 매우 효율적입니다.
예를 들어, 텍스트 에디터의 실행 취소 스택, 운영체제의 프로세스 스케줄링, 혹은 블록체인의 블록 연결 같은 경우에 이상적입니다. 전통적인 배열 방식과 비교해보겠습니다.
기존에는 중간에 요소를 삽입하려면 뒤의 모든 요소를 이동시켰다면, 이제는 단순히 두 개의 포인터만 변경하면 됩니다. 이는 마치 기차 칸을 연결하고 분리하는 것처럼 간단합니다.
연결 리스트의 핵심 특징은 다음과 같습니다: 첫째, O(1) 시간에 삽입과 삭제가 가능합니다(위치를 알고 있을 때). 둘째, 크기 제한이 없어 동적으로 성장할 수 있습니다.
셋째, 메모리가 연속적일 필요가 없어 메모리 단편화에 강합니다. 이러한 특징들이 중요한 이유는 실시간 시스템이나 메모리 제약이 있는 환경에서 유연성을 제공하기 때문입니다.
코드 예제
// 단일 연결 리스트(Singly Linked List) 구현
class Node {
constructor(data) {
this.data = data; // 노드가 저장하는 실제 데이터
this.next = null; // 다음 노드를 가리키는 포인터
}
}
class LinkedList {
constructor() {
this.head = null; // 리스트의 첫 번째 노드
this.tail = null; // 리스트의 마지막 노드 (최적화용)
this.size = 0;
}
// O(1) 시간 복잡도 - 맨 앞에 추가
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head; // 새 노드가 현재 head를 가리킴
this.head = newNode; // head를 새 노드로 업데이트
if (!this.tail) this.tail = newNode; // 첫 노드라면 tail도 설정
this.size++;
}
// O(1) 시간 복잡도 - 맨 뒤에 추가
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = this.tail = newNode; // 빈 리스트면 head와 tail 모두 설정
} else {
this.tail.next = newNode; // 현재 tail의 next를 새 노드로
this.tail = newNode; // tail을 새 노드로 업데이트
}
this.size++;
}
// O(n) 시간 복잡도 - 순차 탐색 필요
find(data) {
let current = this.head;
while (current) {
if (current.data === data) return current;
current = current.next; // 다음 노드로 이동
}
return null;
}
// O(1) 시간 복잡도 - 특정 노드 뒤에 삽입
insertAfter(node, data) {
if (!node) return;
const newNode = new Node(data);
newNode.next = node.next; // 새 노드가 기존 다음 노드를 가리킴
node.next = newNode; // 현재 노드가 새 노드를 가리킴
if (node === this.tail) this.tail = newNode; // tail 갱신
this.size++;
}
// O(1) 시간 복잡도 - 특정 노드 다음 노드 삭제
deleteAfter(node) {
if (!node || !node.next) return;
const deleted = node.next;
node.next = deleted.next; // 포인터를 건너뛰어 연결
if (deleted === this.tail) this.tail = node; // tail 갱신
this.size--;
return deleted.data;
}
}
설명
이것이 하는 일: 위 코드는 단일 연결 리스트를 구현한 것으로, 각 노드가 하나의 next 포인터만 가집니다. 이는 메모리 효율적이면서도 기본적인 리스트 연산을 제공합니다.
head와 tail을 모두 유지하여 양쪽 끝에서의 연산을 O(1)로 최적화했습니다. 첫 번째로, Node 클래스는 데이터와 포인터를 캡슐화합니다.
data 필드에는 실제 저장할 값을, next 필드에는 다음 노드의 참조를 저장합니다. 이러한 자기 참조적 구조가 연결 리스트의 핵심입니다.
JavaScript에서는 객체 참조가 포인터 역할을 하므로 메모리 주소를 직접 다루지 않아도 됩니다. 그 다음으로, prepend와 append 메서드가 실행됩니다.
prepend는 새 노드의 next를 현재 head로 설정하고, head를 새 노드로 바꾸기만 하면 됩니다. 이는 배열의 unshift(O(n))보다 훨씬 빠릅니다.
append는 tail 포인터 덕분에 O(1)에 가능한데, tail이 없다면 끝까지 순회해야 해서 O(n)이 걸립니다. find 메서드는 연결 리스트의 약점을 보여줍니다.
배열처럼 인덱스로 직접 접근할 수 없어서, head부터 시작해 next 포인터를 따라가며 순차 탐색해야 합니다. 이는 O(n) 시간이 걸리며, 대량의 데이터에서는 비효율적일 수 있습니다.
insertAfter와 deleteAfter 메서드는 연결 리스트의 진정한 강점입니다. 특정 노드의 위치를 이미 알고 있다면, 포인터 2개만 변경하면 삽입과 삭제가 완료됩니다.
배열처럼 뒤의 요소들을 이동시킬 필요가 전혀 없습니다. 이것이 연결 리스트를 사용하는 가장 큰 이유입니다.
여러분이 이 코드를 사용하면 다음과 같은 상황에서 큰 이점을 얻습니다. 첫째, 중간 삽입/삭제가 빈번한 애플리케이션에서 성능이 크게 향상됩니다.
둘째, 최대 크기를 예측할 수 없는 동적 데이터를 효율적으로 관리할 수 있습니다. 셋째, 메모리 단편화가 심한 환경에서도 안정적으로 동작합니다.
실전 팁
💡 tail 포인터를 유지하면 append 연산이 O(1)이 됩니다. tail이 없으면 매번 끝까지 순회해야 하므로 O(n)이 걸립니다.
💡 이중 연결 리스트(Doubly Linked List)를 사용하면 역방향 순회가 가능하고, 특정 노드의 이전 노드에 접근할 수 있어 더 유연합니다.
💡 연결 리스트는 캐시 미스가 많이 발생합니다. 노드들이 메모리에 흩어져 있어 CPU 캐시 효율이 낮기 때문입니다. 성능이 중요하다면 이를 고려하세요.
💡 JavaScript에서 메모리 누수를 방지하려면 노드 삭제 시 명시적으로 null을 할당하세요. 특히 순환 참조가 있을 때 중요합니다.
💡 head 노드를 삭제하는 경우는 특별히 처리해야 합니다. deleteAfter로는 처리할 수 없으므로 별도의 deleteHead 메서드를 만드세요.
3. 성능 비교 - 시간 복잡도로 보는 실전 선택 가이드
시작하며
여러분이 프로젝트에서 자료구조를 선택해야 할 때, "이게 더 빠를까?"라는 고민을 해본 적 있나요? 배열과 연결 리스트 중 무엇을 선택할지는 단순히 "어떤 게 더 좋은가"가 아니라 "어떤 연산을 주로 사용하는가"에 달려 있습니다.
이 문제는 실무에서 성능 병목의 주요 원인이 됩니다. 잘못된 자료구조를 선택하면 단순한 작업에도 불필요한 시간이 소모되고, 사용자는 답답함을 느낍니다.
특히 데이터 양이 많아질수록 이 차이는 기하급수적으로 커집니다. 바로 이럴 때 필요한 것이 연산별 시간 복잡도에 대한 명확한 이해입니다.
각 자료구조가 어떤 연산에 강하고 약한지 알면, 상황에 맞는 최적의 선택을 할 수 있습니다.
개요
간단히 말해서, 시간 복잡도는 데이터의 양이 증가할 때 연산에 걸리는 시간이 어떻게 변하는지를 나타냅니다. O(1)은 데이터 양과 무관하게 일정한 시간, O(n)은 데이터 양에 비례하는 시간을 의미합니다.
이 개념이 중요한 이유는 실제 서비스에서 데이터는 계속 증가하기 때문입니다. 100개의 데이터로 테스트할 때는 문제없던 코드가, 10만 개가 되면 응답이 느려지는 경우가 많습니다.
예를 들어, 전자상거래 사이트의 장바구니, 소셜 미디어의 피드, 메시징 앱의 대화 목록 등에서 올바른 선택이 사용자 경험을 결정합니다. 전통적인 방식으로는 실제로 실행해보고 느린 부분을 찾았습니다.
하지만 이제는 시간 복잡도 분석을 통해 사전에 성능 문제를 예측하고 예방할 수 있습니다. 이는 마치 건물을 짓기 전에 구조 계산을 하는 것과 같습니다.
핵심 비교 포인트는 다음과 같습니다: 첫째, 접근(Access) - 특정 위치의 데이터 읽기. 둘째, 탐색(Search) - 특정 값을 가진 요소 찾기.
셋째, 삽입(Insert) - 새 요소 추가. 넷째, 삭제(Delete) - 기존 요소 제거.
이 네 가지 연산의 특성을 이해하면 최적의 자료구조를 선택할 수 있습니다.
코드 예제
// 성능 비교 벤치마크 코드
function benchmarkArrayVsLinkedList(size) {
// 배열 테스트
const arr = [];
const list = new LinkedList();
// 1. 끝에 추가(Append) 테스트
console.time('Array append');
for (let i = 0; i < size; i++) {
arr.push(i); // O(1) 평균
}
console.timeEnd('Array append');
console.time('LinkedList append');
for (let i = 0; i < size; i++) {
list.append(i); // O(1) with tail pointer
}
console.timeEnd('LinkedList append');
// 2. 랜덤 접근(Access) 테스트
const randomIndex = Math.floor(size / 2);
console.time('Array access');
const arrValue = arr[randomIndex]; // O(1) 직접 접근
console.timeEnd('Array access');
console.time('LinkedList access');
let current = list.head;
for (let i = 0; i < randomIndex; i++) {
current = current.next; // O(n) 순차 접근
}
const listValue = current.data;
console.timeEnd('LinkedList access');
// 3. 중간 삽입(Insert) 테스트
const insertIndex = Math.floor(size / 2);
console.time('Array insert middle');
arr.splice(insertIndex, 0, 999); // O(n) 요소 이동 필요
console.timeEnd('Array insert middle');
console.time('LinkedList insert middle');
current = list.head;
for (let i = 0; i < insertIndex; i++) {
current = current.next;
}
list.insertAfter(current, 999); // O(1) 포인터만 변경
console.timeEnd('LinkedList insert middle');
// 4. 탐색(Search) 테스트
const searchValue = Math.floor(size * 0.8);
console.time('Array search');
arr.indexOf(searchValue); // O(n) 순차 탐색
console.timeEnd('Array search');
console.time('LinkedList search');
list.find(searchValue); // O(n) 순차 탐색
console.timeEnd('LinkedList search');
}
// 실행 예시
benchmarkArrayVsLinkedList(10000);
설명
이것이 하는 일: 위 코드는 배열과 연결 리스트의 주요 연산을 실제로 실행하고 소요 시간을 측정하는 벤치마크입니다. console.time/timeEnd를 사용하여 각 연산의 실제 성능을 비교할 수 있습니다.
첫 번째로, append 테스트에서는 두 자료구조 모두 O(1) 시간 복잡도를 보입니다. 배열의 push는 대부분 O(1)이지만 재할당 시에는 O(n)이 되고, 연결 리스트는 tail 포인터 덕분에 항상 O(1)입니다.
실제로 실행해보면 작은 데이터셋에서는 배열이 약간 빠르지만, 큰 데이터셋에서는 비슷한 성능을 보입니다. 그 다음으로, 접근(access) 테스트에서 배열의 압도적인 우위가 드러납니다.
arr[index]는 단순한 메모리 주소 계산으로 즉시 완료되지만, 연결 리스트는 head부터 시작해 index번 만큼 next를 따라가야 합니다. 10,000개 중 5,000번째 요소에 접근한다면, 배열은 1회의 연산, 연결 리스트는 5,000회의 연산이 필요합니다.
중간 삽입(insert middle) 테스트에서는 상황이 역전됩니다. arr.splice는 삽입 위치 뒤의 모든 요소를 한 칸씩 이동시켜야 하므로 O(n)입니다.
반면 연결 리스트는 insertAfter로 단순히 두 개의 포인터만 변경하면 되므로 O(1)입니다. 단, 삽입 위치까지 도달하는 시간은 별도로 소요됩니다.
탐색(search) 테스트에서는 두 자료구조 모두 O(n)의 시간 복잡도를 보입니다. 정렬되지 않은 데이터에서 특정 값을 찾으려면 처음부터 끝까지 확인해야 하기 때문입니다.
하지만 실제 실행 시간은 배열이 더 빠른데, 이는 캐시 지역성 때문입니다. 배열의 연속된 메모리는 CPU 캐시에 효율적으로 로드됩니다.
여러분이 이 벤치마크를 실행해보면 이론과 실제의 차이를 체감할 수 있습니다. 시간 복잡도는 데이터 양이 증가할 때의 추세를 나타내지만, 작은 데이터셋에서는 상수 요인(constant factors)이 더 중요할 수 있습니다.
실제 프로젝트에서는 데이터 크기와 주요 연산을 고려하여 선택해야 합니다.
실전 팁
💡 데이터가 1000개 미만이라면 대부분의 경우 배열이 더 빠릅니다. 캐시 효율과 낮은 메모리 오버헤드 때문입니다.
💡 중간 삽입/삭제가 전체 연산의 50% 이상을 차지한다면 연결 리스트를 고려하세요. 그렇지 않다면 배열이 더 나은 선택입니다.
💡 메모리 사용량도 고려하세요. 연결 리스트는 각 노드마다 포인터를 저장하므로 배열보다 1.5~2배 더 많은 메모리를 사용합니다.
💡 JavaScript의 Array는 이미 고도로 최적화되어 있습니다. 대부분의 경우 직접 연결 리스트를 구현하는 것보다 내장 Array를 사용하는 것이 빠릅니다.
💡 성능 측정은 실제 환경에서 하세요. 개발 도구의 콘솔과 프로덕션 환경의 성능은 다를 수 있습니다.
4. 메모리 특성 - 캐시와 메모리 레이아웃의 비밀
시작하며
여러분이 대용량 데이터를 처리하는 애플리케이션을 개발할 때, 시간 복잡도는 같은데도 실제 실행 속도가 크게 다른 경우를 경험해본 적 있나요? 두 알고리즘 모두 O(n)인데 하나는 1초, 다른 하나는 10초가 걸리는 상황 말입니다.
이런 현상의 원인은 메모리 접근 패턴에 있습니다. 현대 컴퓨터는 CPU와 메인 메모리 사이의 속도 차이를 줄이기 위해 캐시를 사용합니다.
캐시 친화적인 코드와 그렇지 않은 코드의 성능 차이는 수십 배에 달할 수 있습니다. 바로 이럴 때 필요한 것이 자료구조의 메모리 레이아웃에 대한 이해입니다.
배열과 연결 리스트가 메모리에서 어떻게 배치되는지 알면, 실제 성능을 훨씬 정확하게 예측할 수 있습니다.
개요
간단히 말해서, 캐시 지역성(cache locality)은 자주 사용되는 데이터가 캐시에 존재할 확률을 의미합니다. 데이터가 연속적으로 배치되어 있으면 한 번의 캐시 로드로 여러 요소를 가져올 수 있어 성능이 크게 향상됩니다.
이 개념이 중요한 이유는 메모리 접근 속도가 전체 성능의 병목이 되기 때문입니다. CPU 레지스터 접근은 1사이클, L1 캐시는 4사이클, L2 캐시는 10사이클, 메인 메모리는 100~300사이클이 걸립니다.
예를 들어, 이미지 처리, 비디오 인코딩, 데이터 분석 같은 CPU 집약적 작업에서는 캐시 효율이 전체 성능을 결정합니다. 배열과 연결 리스트의 메모리 특성을 비교해보겠습니다.
배열은 연속된 메모리 블록을 사용하여 공간 지역성(spatial locality)이 뛰어납니다. 반면 연결 리스트는 노드가 메모리 곳곳에 흩어져 있어 캐시 미스가 빈번하게 발생합니다.
핵심 차이점은 다음과 같습니다: 첫째, 배열은 한 번의 캐시 라인 로드로 여러 요소를 가져옵니다. 둘째, 연결 리스트는 각 노드마다 새로운 메모리 접근이 필요합니다.
셋째, 배열은 메모리 오버헤드가 없지만 연결 리스트는 포인터를 위한 추가 공간이 필요합니다. 이러한 차이가 실제 성능에 결정적인 영향을 미칩니다.
코드 예제
// 메모리 레이아웃과 캐시 효율 비교
class MemoryBenchmark {
// 배열: 연속된 메모리 레이아웃
static arraySequentialAccess(size) {
const arr = new Array(size);
// 초기화: 연속된 메모리 할당
for (let i = 0; i < size; i++) {
arr[i] = i * 2;
}
// 순차 접근: 캐시 친화적
console.time('Array sequential access');
let sum = 0;
for (let i = 0; i < size; i++) {
sum += arr[i]; // 캐시 라인이 미리 로드되어 매우 빠름
}
console.timeEnd('Array sequential access');
return sum;
}
// 배열: 랜덤 접근 (캐시 미스 발생 가능)
static arrayRandomAccess(size) {
const arr = new Array(size);
const indices = [];
// 랜덤 인덱스 생성
for (let i = 0; i < size; i++) {
arr[i] = i * 2;
indices.push(Math.floor(Math.random() * size));
}
// 랜덤 접근: 캐시 효율 저하
console.time('Array random access');
let sum = 0;
for (let i = 0; i < size; i++) {
sum += arr[indices[i]]; // 예측 불가능한 접근으로 캐시 미스
}
console.timeEnd('Array random access');
return sum;
}
// 연결 리스트: 비연속적 메모리 레이아웃
static linkedListSequentialAccess(size) {
const list = new LinkedList();
// 초기화: 메모리 곳곳에 노드 생성
for (let i = 0; i < size; i++) {
list.append(i * 2);
}
// 순차 접근: 포인터 추적으로 캐시 미스 빈번
console.time('LinkedList sequential access');
let sum = 0;
let current = list.head;
while (current) {
sum += current.data; // 각 노드가 다른 메모리 위치에 있어 느림
current = current.next; // 포인터 역참조로 캐시 미스
}
console.timeEnd('LinkedList sequential access');
return sum;
}
// 메모리 오버헤드 비교
static compareMemoryUsage(size) {
// 배열의 메모리 사용량 (대략)
// JavaScript에서 숫자는 8바이트 (64비트)
const arrayMemory = size * 8;
// 연결 리스트의 메모리 사용량 (대략)
// 각 노드: 데이터(8바이트) + next 포인터(8바이트) = 16바이트
const linkedListMemory = size * 16;
console.log(`Array memory: ${(arrayMemory / 1024).toFixed(2)} KB`);
console.log(`LinkedList memory: ${(linkedListMemory / 1024).toFixed(2)} KB`);
console.log(`Memory overhead: ${((linkedListMemory / arrayMemory - 1) * 100).toFixed(2)}%`);
}
}
// 실행 및 비교
const size = 100000;
MemoryBenchmark.arraySequentialAccess(size);
MemoryBenchmark.arrayRandomAccess(size);
MemoryBenchmark.linkedListSequentialAccess(size);
MemoryBenchmark.compareMemoryUsage(size);
설명
이것이 하는 일: 위 코드는 배열과 연결 리스트의 메모리 접근 패턴을 실제로 측정하여 캐시 효율의 차이를 보여줍니다. 순차 접근과 랜덤 접근, 그리고 메모리 오버헤드를 각각 비교합니다.
첫 번째로, arraySequentialAccess는 배열의 진정한 강점을 보여줍니다. 연속된 메모리를 순차적으로 접근하면 CPU는 다음에 필요한 데이터를 예측하여 미리 캐시에 로드합니다(prefetching).
일반적인 캐시 라인은 64바이트이므로, 하나의 요소를 읽을 때 인접한 여러 요소도 함께 캐시에 들어옵니다. 이는 마치 도서관에서 한 권의 책을 빌릴 때 같은 선반의 다른 책도 함께 가져오는 것과 같습니다.
arrayRandomAccess는 배열이라도 랜덤 접근 시 캐시 효율이 떨어지는 것을 보여줍니다. 접근 패턴이 예측 불가능하면 prefetching이 작동하지 않고, 캐시 라인에 로드된 인접 데이터를 활용할 수 없습니다.
그럼에도 연속된 메모리 구조 덕분에 연결 리스트보다는 여전히 빠릅니다. linkedListSequentialAccess에서 연결 리스트의 약점이 드러납니다.
순차 접근임에도 불구하고 각 노드가 메모리의 서로 다른 위치에 있어서 매번 새로운 메모리 접근이 필요합니다. next 포인터를 읽고, 그 주소로 이동하고, 데이터를 읽는 과정이 반복되며, 각 단계마다 캐시 미스가 발생할 수 있습니다.
실제로 배열보다 5~10배 느린 경우가 많습니다. compareMemoryUsage는 메모리 오버헤드를 계산합니다.
연결 리스트는 각 노드마다 next 포인터(64비트 시스템에서 8바이트)를 저장해야 하므로, 동일한 데이터를 저장하는데 거의 2배의 메모리가 필요합니다. 이중 연결 리스트라면 prev 포인터까지 추가되어 3배가 됩니다.
여러분이 이 코드를 실제로 실행해보면 놀라운 성능 차이를 확인할 수 있습니다. 10만 개의 요소를 순회할 때 배열은 몇 밀리초, 연결 리스트는 수십 밀리초가 걸립니다.
이는 O(n)이라는 동일한 시간 복잡도 뒤에 숨겨진 실제 성능의 차이입니다. 실무에서는 이러한 상수 요인(constant factor)이 사용자 경험을 결정합니다.
실전 팁
💡 대량의 데이터를 순차적으로 처리한다면 거의 항상 배열이 더 빠릅니다. 캐시 지역성의 이점이 크기 때문입니다.
💡 메모리가 제한된 환경(임베디드, 모바일)에서는 연결 리스트의 2배 메모리 오버헤드가 치명적일 수 있습니다. 신중하게 선택하세요.
💡 성능 프로파일링 도구(Chrome DevTools Performance 탭)를 사용하면 캐시 미스를 시각적으로 확인할 수 있습니다.
💡 데이터가 자주 재할당되는 경우(크기 변경), 배열의 복사 비용이 연결 리스트의 캐시 미스보다 클 수 있습니다. 이럴 때는 연결 리스트가 유리합니다.
💡 JavaScript 엔진은 배열을 고도로 최적화하므로, 이론적으로 연결 리스트가 유리한 상황에서도 실제로는 배열이 더 빠를 수 있습니다. 항상 실측하세요.
5. Stack 구현 비교 - 배열 vs 연결 리스트로 만드는 스택
시작하며
여러분이 브라우저의 뒤로 가기 기능이나 텍스트 에디터의 실행 취소 기능을 구현해야 한다면 어떻게 하시겠습니까? 이러한 기능들의 공통점은 "가장 최근에 추가된 것을 먼저 제거"하는 LIFO(Last In First Out) 패턴입니다.
이런 패턴은 프로그래밍 어디에나 있습니다. 함수 호출 스택, 수식 계산, 괄호 검사, DFS(깊이 우선 탐색) 알고리즘 등이 모두 스택을 사용합니다.
스택을 어떻게 구현하느냐에 따라 성능과 메모리 효율이 달라집니다. 바로 이럴 때 선택해야 하는 것이 배열 기반 스택과 연결 리스트 기반 스택입니다.
각각의 장단점을 이해하면 상황에 맞는 최적의 구현을 선택할 수 있습니다.
개요
간단히 말해서, 스택은 한쪽 끝(top)에서만 데이터를 추가(push)하고 제거(pop)하는 자료구조입니다. 마치 접시를 쌓아올리듯이, 가장 위에 있는 것만 꺼낼 수 있는 구조입니다.
스택이 필요한 이유는 순서를 역전시키거나 최근 상태를 추적할 때 매우 효율적이기 때문입니다. 재귀 함수는 내부적으로 호출 스택을 사용하고, JSON 파싱이나 HTML 태그 검증도 스택으로 구현됩니다.
예를 들어, 계산기 앱에서 수식 "3 + 4 * 2"를 올바르게 계산하려면 연산자 우선순위를 관리하는 스택이 필요합니다. 배열과 연결 리스트로 스택을 구현하는 방식을 비교해보겠습니다.
배열 기반 스택은 JavaScript의 내장 메서드(push/pop)를 그대로 활용할 수 있어 간단하고 빠릅니다. 연결 리스트 기반 스택은 크기 제한 없이 동적으로 성장하고, 재할당 비용이 없습니다.
핵심 특징은 다음과 같습니다: 첫째, 두 구현 모두 push와 pop이 O(1)입니다. 둘째, 배열은 메모리 효율적이고 캐시 친화적입니다.
셋째, 연결 리스트는 크기 예측이 어려울 때 유리합니다. 이러한 특징을 바탕으로 적절한 구현을 선택할 수 있습니다.
코드 예제
// 배열 기반 스택 구현
class ArrayStack {
constructor(capacity = 100) {
this.items = new Array(capacity); // 고정 용량으로 시작
this.top = -1; // 스택의 최상단 인덱스
this.capacity = capacity;
}
// O(1) - 상수 시간 추가
push(item) {
if (this.top === this.capacity - 1) {
// 용량 초과 시 재할당 (O(n) 한 번)
this._resize(this.capacity * 2);
}
this.items[++this.top] = item; // 인덱스 증가 후 추가
}
// O(1) - 상수 시간 제거
pop() {
if (this.isEmpty()) throw new Error('Stack underflow');
const item = this.items[this.top];
this.items[this.top--] = null; // 메모리 누수 방지
return item;
}
// O(1) - 최상단 요소 확인
peek() {
if (this.isEmpty()) return null;
return this.items[this.top];
}
isEmpty() {
return this.top === -1;
}
_resize(newCapacity) {
const newItems = new Array(newCapacity);
for (let i = 0; i <= this.top; i++) {
newItems[i] = this.items[i];
}
this.items = newItems;
this.capacity = newCapacity;
}
}
// 연결 리스트 기반 스택 구현
class LinkedListStack {
constructor() {
this.top = null; // 최상단 노드
this.size = 0;
}
// O(1) - 항상 상수 시간 (재할당 없음)
push(item) {
const newNode = new Node(item);
newNode.next = this.top; // 새 노드가 현재 top을 가리킴
this.top = newNode; // top을 새 노드로 업데이트
this.size++;
}
// O(1) - 항상 상수 시간
pop() {
if (this.isEmpty()) throw new Error('Stack underflow');
const item = this.top.data;
this.top = this.top.next; // top을 다음 노드로 이동
this.size--;
return item;
}
// O(1) - 최상단 요소 확인
peek() {
if (this.isEmpty()) return null;
return this.top.data;
}
isEmpty() {
return this.top === null;
}
}
// 실전 예제: 괄호 검사
function isValidParentheses(str) {
const stack = new ArrayStack(); // 배열 기반 스택 사용
const pairs = { ')': '(', '}': '{', ']': '[' };
for (const char of str) {
if (['(', '{', '['].includes(char)) {
stack.push(char); // 여는 괄호는 스택에 추가
} else if ([')', '}', ']'].includes(char)) {
if (stack.isEmpty() || stack.pop() !== pairs[char]) {
return false; // 짝이 맞지 않으면 유효하지 않음
}
}
}
return stack.isEmpty(); // 모든 괄호가 닫혔는지 확인
}
console.log(isValidParentheses("()[]{}")); // true
console.log(isValidParentheses("([)]")); // false
설명
이것이 하는 일: 위 코드는 스택을 배열과 연결 리스트 두 가지 방식으로 구현하고, 실전 예제로 괄호 검사 알고리즘을 보여줍니다. 각 구현의 특징과 장단점을 명확히 비교할 수 있습니다.
첫 번째로, ArrayStack은 배열의 끝을 스택의 top으로 사용합니다. top 인덱스를 통해 현재 스택의 최상단 위치를 추적하며, push는 top을 증가시키고 값을 저장합니다.
pop은 top 위치의 값을 반환하고 top을 감소시킵니다. 이 방식은 JavaScript의 내장 Array.push/pop과 동일한 원리이며, 실제로 대부분의 경우 내장 메서드를 사용하는 것이 더 빠릅니다.
배열 기반 스택의 주요 장점은 메모리 효율과 캐시 친화성입니다. 모든 데이터가 연속된 메모리에 저장되어 있어 순회가 필요한 경우 매우 빠릅니다.
또한 포인터를 저장할 필요가 없어 메모리 오버헤드가 없습니다. 단점은 용량을 초과하면 전체 배열을 복사하는 재할당이 필요하다는 것입니다.
LinkedListStack은 연결 리스트의 head를 top으로 사용합니다. push는 새 노드를 생성하여 현재 top 앞에 삽입하고, pop은 top을 다음 노드로 이동시킵니다.
이 구현의 가장 큰 장점은 재할당이 전혀 필요 없다는 것입니다. 크기가 얼마나 커지든 항상 O(1) 시간에 push가 가능합니다.
연결 리스트 기반 스택은 스택의 최대 크기를 예측하기 어려울 때 유용합니다. 예를 들어, 매우 깊은 재귀 호출이나 무제한 실행 취소 기능에서는 연결 리스트 기반이 안전합니다.
단점은 각 노드마다 포인터를 저장하는 메모리 오버헤드와 캐시 효율 저하입니다. isValidParentheses 함수는 스택의 전형적인 활용 예시입니다.
여는 괄호를 만나면 스택에 push하고, 닫는 괄호를 만나면 스택에서 pop하여 짝이 맞는지 확인합니다. 이 알고리즘은 O(n) 시간과 O(n) 공간 복잡도를 가지며, 컴파일러의 구문 분석이나 JSON 검증에서 실제로 사용됩니다.
여러분이 이 코드를 프로젝트에 적용할 때는 다음을 고려하세요. 스택의 크기가 일정하고 예측 가능하다면 배열 기반을 선택하세요.
크기가 매우 가변적이거나 무제한이라면 연결 리스트 기반을 선택하세요. 대부분의 JavaScript 프로젝트에서는 내장 Array를 그대로 사용하는 것이 가장 실용적입니다.
실전 팁
💡 JavaScript에서는 대부분의 경우 단순히 배열의 push/pop을 사용하는 것이 가장 효율적입니다. 별도로 스택 클래스를 만들 필요가 없습니다.
💡 스택의 최대 크기를 알고 있다면 배열의 초기 용량을 그 크기로 설정하여 재할당을 방지하세요.
💡 메모리가 제한된 환경에서는 pop 시 명시적으로 null을 할당하여 가비지 컬렉션을 도와주세요.
💡 스택 오버플로우를 방지하려면 최대 크기를 설정하고 push 전에 확인하세요. 특히 사용자 입력을 처리할 때 중요합니다.
💡 디버깅 시 스택의 내용을 출력하는 toString() 메서드를 추가하면 매우 유용합니다. 현재 상태를 한눈에 파악할 수 있습니다.
6. Queue 구현 비교 - 효율적인 큐의 선택
시작하며
여러분이 메시지 처리 시스템이나 작업 스케줄러를 구현할 때, "먼저 들어온 것을 먼저 처리"하는 FIFO(First In First Out) 패턴이 필요했던 경험이 있나요? 프린터 대기열, 콜센터 전화 대기, 네트워크 패킷 처리 등이 모두 이 패턴을 사용합니다.
큐를 잘못 구현하면 성능 문제가 발생합니다. 특히 배열로 큐를 구현할 때 shift() 메서드를 사용하면 O(n) 시간이 걸려 대기열이 길어질수록 느려집니다.
실시간 시스템에서는 이런 지연이 치명적일 수 있습니다. 바로 이럴 때 올바른 큐 구현이 필요합니다.
연결 리스트 기반 큐는 항상 O(1)에 enqueue와 dequeue를 수행하며, 순환 배열 큐는 메모리 효율을 유지하면서도 빠른 성능을 제공합니다.
개요
간단히 말해서, 큐는 한쪽 끝(rear)에서 데이터를 추가하고 다른 쪽 끝(front)에서 제거하는 자료구조입니다. 마치 은행 창구 대기줄처럼, 먼저 온 사람이 먼저 서비스를 받는 공정한 구조입니다.
큐가 중요한 이유는 순서 보장이 필요한 모든 시스템에서 필수적이기 때문입니다. 비동기 작업 처리, BFS(너비 우선 탐색) 알고리즘, 이벤트 루프, 캐시 관리(LRU) 등에서 핵심적인 역할을 합니다.
예를 들어, Node.js의 이벤트 루프는 내부적으로 여러 큐를 사용하여 비동기 작업을 순서대로 처리합니다. 배열과 연결 리스트로 큐를 구현하는 방식을 비교해보겠습니다.
단순 배열로 구현하면 shift()가 O(n)이라 비효율적이지만, 순환 배열을 사용하면 O(1)로 개선할 수 있습니다. 연결 리스트는 자연스럽게 O(1) enqueue/dequeue를 제공하며 크기 제한도 없습니다.
핵심 비교 포인트는 다음과 같습니다: 첫째, 단순 배열 큐는 dequeue가 O(n)이라 피해야 합니다. 둘째, 순환 배열 큐는 O(1) 연산과 캐시 효율을 모두 얻을 수 있습니다.
셋째, 연결 리스트 큐는 구현이 간단하고 크기 제한이 없습니다. 사용 사례에 따라 적절한 구현을 선택해야 합니다.
코드 예제
// 순환 배열 기반 큐 (Circular Array Queue)
class CircularArrayQueue {
constructor(capacity = 10) {
this.items = new Array(capacity);
this.front = 0; // 첫 번째 요소의 인덱스
this.rear = 0; // 다음 요소가 들어갈 위치
this.size = 0;
this.capacity = capacity;
}
// O(1) - 상수 시간 추가
enqueue(item) {
if (this.isFull()) throw new Error('Queue overflow');
this.items[this.rear] = item;
this.rear = (this.rear + 1) % this.capacity; // 순환 처리
this.size++;
}
// O(1) - 상수 시간 제거 (shift보다 훨씬 빠름!)
dequeue() {
if (this.isEmpty()) throw new Error('Queue underflow');
const item = this.items[this.front];
this.items[this.front] = null; // 메모리 정리
this.front = (this.front + 1) % this.capacity; // 순환 처리
this.size--;
return item;
}
peek() {
if (this.isEmpty()) return null;
return this.items[this.front];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.capacity;
}
}
// 연결 리스트 기반 큐
class LinkedListQueue {
constructor() {
this.front = null; // 첫 번째 노드 (제거될 위치)
this.rear = null; // 마지막 노드 (추가될 위치)
this.size = 0;
}
// O(1) - 항상 상수 시간
enqueue(item) {
const newNode = new Node(item);
if (this.isEmpty()) {
this.front = this.rear = newNode; // 첫 노드는 front와 rear 모두
} else {
this.rear.next = newNode; // 현재 rear 뒤에 추가
this.rear = newNode; // rear를 새 노드로 이동
}
this.size++;
}
// O(1) - 항상 상수 시간
dequeue() {
if (this.isEmpty()) throw new Error('Queue underflow');
const item = this.front.data;
this.front = this.front.next; // front를 다음 노드로 이동
if (!this.front) this.rear = null; // 마지막 노드였다면 rear도 null
this.size--;
return item;
}
peek() {
if (this.isEmpty()) return null;
return this.front.data;
}
isEmpty() {
return this.front === null;
}
}
// 잘못된 구현 (피해야 할 방식!)
class SlowArrayQueue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item); // O(1)
}
dequeue() {
return this.items.shift(); // O(n) - 매우 느림!
}
}
// 성능 비교
function compareQueuePerformance(size) {
const circular = new CircularArrayQueue(size + 1);
const linked = new LinkedListQueue();
console.time('Circular queue enqueue/dequeue');
for (let i = 0; i < size; i++) {
circular.enqueue(i);
}
for (let i = 0; i < size; i++) {
circular.dequeue();
}
console.timeEnd('Circular queue enqueue/dequeue');
console.time('Linked queue enqueue/dequeue');
for (let i = 0; i < size; i++) {
linked.enqueue(i);
}
for (let i = 0; i < size; i++) {
linked.dequeue();
}
console.timeEnd('Linked queue enqueue/dequeue');
}
compareQueuePerformance(10000);
설명
이것이 하는 일: 위 코드는 큐를 순환 배열과 연결 리스트로 구현하고, 잘못된 배열 구현(shift 사용)과 비교합니다. 각 구현의 성능 특성과 적합한 사용 사례를 명확히 보여줍니다.
첫 번째로, CircularArrayQueue는 모듈로 연산(%)을 사용하여 배열을 순환시킵니다. front와 rear 인덱스가 배열의 끝에 도달하면 다시 처음으로 돌아가므로, 배열 공간을 재사용할 수 있습니다.
이는 마치 시계의 시침이 12를 지나면 다시 1로 돌아가는 것과 같습니다. 이 방식으로 dequeue 시 요소를 이동시키지 않아도 되어 O(1)을 달성합니다.
순환 배열의 핵심은 (index + 1) % capacity 공식입니다. rear가 9번 인덱스에 있고 capacity가 10이라면, 다음 rear는 (9 + 1) % 10 = 0이 됩니다.
이렇게 배열을 링처럼 사용하여 공간을 낭비하지 않습니다. 단, 크기가 고정되어 있어 capacity를 초과하면 enqueue가 실패합니다.
동적 크기 조정을 원한다면 추가 로직이 필요합니다. LinkedListQueue는 front와 rear 포인터 두 개를 유지합니다.
enqueue는 rear 뒤에 노드를 추가하고 rear를 업데이트합니다. dequeue는 front 노드를 제거하고 front를 다음 노드로 이동시킵니다.
이 구현은 매우 직관적이며, 스택과 달리 양쪽 끝을 추적해야 한다는 점만 다릅니다. 연결 리스트 큐의 큰 장점은 크기 제한이 없다는 것입니다.
메모리가 허용하는 한 무한정 enqueue가 가능하므로, 대기열의 크기를 예측하기 어려운 시스템에 적합합니다. 예를 들어, 웹 서버의 요청 큐나 메시지 브로커에서는 트래픽 급증에 대비하여 연결 리스트 큐를 선호합니다.
SlowArrayQueue는 절대 사용해서는 안 되는 잘못된 구현입니다. shift()는 첫 번째 요소를 제거한 후 나머지 모든 요소를 한 칸씩 앞으로 이동시켜야 하므로 O(n)입니다.
10,000개의 요소가 있다면 dequeue 한 번에 9,999번의 이동 연산이 발생합니다. 이는 성능을 심각하게 저하시키며, 큐가 길어질수록 기하급수적으로 느려집니다.
여러분이 큐를 선택할 때는 다음을 고려하세요. 최대 크기를 알고 메모리 효율이 중요하다면 순환 배열을 선택하세요.
크기가 가변적이고 무제한 성장이 필요하다면 연결 리스트를 선택하세요. JavaScript에서는 두 구현 모두 충분히 빠르지만, 대용량 처리에서는 순환 배열이 캐시 효율 덕분에 약간 더 빠를 수 있습니다.
실전 팁
💡 순환 배열의 capacity는 실제 최대 크기보다 1 크게 설정하세요. front와 rear가 같을 때 비어있는지 가득 찬 것인지 구분하기 위함입니다.
💡 priority queue(우선순위 큐)가 필요하다면 힙(heap) 자료구조를 사용하세요. 일반 큐로는 우선순위를 효율적으로 처리할 수 없습니다.
💡 연결 리스트 큐에서 rear 포인터를 유지하지 않으면 enqueue가 O(n)이 됩니다. 반드시 rear를 추적하세요.
💡 JavaScript의 배열 shift()를 큐로 사용하지 마세요. 작은 데이터셋에서는 괜찮아 보이지만 큰 규모에서는 성능 병목이 됩니다.
💡 deque(double-ended queue)가 필요하다면 이중 연결 리스트를 사용하세요. 양쪽 끝에서 모두 O(1)로 추가/제거가 가능합니다.
7. 실무 선택 기준 - 언제 배열을, 언제 연결 리스트를 사용할까
시작하며
여러분이 새로운 기능을 설계할 때, 자료구조 선택에서 고민한 경험이 있나요? "배열이 더 빠르다던데", "연결 리스트가 더 유연하다던데"라는 일반적인 조언만으로는 구체적인 상황에서 올바른 결정을 내리기 어렵습니다.
잘못된 자료구조 선택은 나중에 리팩토링 비용으로 돌아옵니다. 처음에는 문제없어 보이다가 사용자가 늘고 데이터가 많아지면서 성능 문제가 드러나는 경우가 많습니다.
이미 수천 줄의 코드가 해당 자료구조에 의존하고 있다면 변경이 매우 어렵습니다. 바로 이럴 때 필요한 것이 실무 기반의 명확한 선택 기준입니다.
연산 패턴, 데이터 크기, 메모리 제약, 성능 요구사항 등을 종합적으로 고려하여 최적의 선택을 할 수 있어야 합니다.
개요
간단히 말해서, 자료구조 선택은 "무엇이 더 좋은가"가 아니라 "이 상황에서 무엇이 더 적합한가"의 문제입니다. 각 자료구조는 특정 연산에 최적화되어 있으며, 여러분의 사용 패턴과 맞아야 합니다.
이 선택 기준이 중요한 이유는 성능과 유지보수성에 직접적인 영향을 미치기 때문입니다. 올바른 선택은 코드를 단순하게 만들고, 잘못된 선택은 불필요한 복잡성과 성능 저하를 가져옵니다.
예를 들어, 실시간 채팅 애플리케이션의 메시지 목록, 온라인 게임의 플레이어 인벤토리, 전자상거래의 장바구니 등 각각에 최적의 자료구조가 다릅니다. 선택 과정을 체계적으로 접근해보겠습니다.
첫째, 가장 빈번한 연산이 무엇인지 파악합니다. 둘째, 데이터의 최대 크기를 예측합니다.
셋째, 메모리 제약이 있는지 확인합니다. 넷째, 성능 요구사항(응답 시간)을 명확히 합니다.
이 네 가지 질문에 답하면 자연스럽게 최적의 선택이 드러납니다. 의사결정 체크리스트는 다음과 같습니다: 랜덤 접근이 50% 이상이면 배열, 중간 삽입/삭제가 50% 이상이면 연결 리스트, 데이터가 1000개 미만이면 대부분 배열, 크기를 예측할 수 없으면 연결 리스트, 순차 처리가 주요 연산이면 배열.
이러한 기준들을 실제 프로젝트에 적용하면 합리적인 결정을 내릴 수 있습니다.
코드 예제
// 실무 시나리오별 최적 자료구조 선택 가이드
// 시나리오 1: 사용자 인벤토리 시스템 (게임)
// 특징: 고정된 슬롯 수, 빈번한 랜덤 접근, 드래그 앤 드롭
// 최적: 배열
class GameInventory {
constructor(slotCount = 40) {
this.slots = new Array(slotCount).fill(null); // 고정 크기 배열
}
// O(1) - 특정 슬롯에 아이템 배치
setItem(slotIndex, item) {
if (slotIndex < 0 || slotIndex >= this.slots.length) return false;
this.slots[slotIndex] = item;
return true;
}
// O(1) - 특정 슬롯의 아이템 확인
getItem(slotIndex) {
return this.slots[slotIndex];
}
// O(1) - 두 슬롯 교환 (드래그 앤 드롭)
swapSlots(index1, index2) {
[this.slots[index1], this.slots[index2]] =
[this.slots[index2], this.slots[index1]];
}
}
// 시나리오 2: 브라우저 히스토리 (앞으로/뒤로 가기)
// 특징: 중간 삽입 빈번, 순차 이동, 무제한 크기
// 최적: 이중 연결 리스트
class BrowserHistory {
constructor() {
this.list = new DoublyLinkedList(); // 이중 연결 리스트
this.current = null;
}
// O(1) - 새 페이지 방문
visit(url) {
// 현재 위치 이후의 히스토리 삭제
while (this.current && this.current.next) {
this.list.deleteNode(this.current.next);
}
this.list.append(url);
this.current = this.list.tail;
}
// O(1) - 뒤로 가기
back() {
if (this.current && this.current.prev) {
this.current = this.current.prev;
return this.current.data;
}
return null;
}
// O(1) - 앞으로 가기
forward() {
if (this.current && this.current.next) {
this.current = this.current.next;
return this.current.data;
}
return null;
}
}
// 시나리오 3: 실시간 주식 가격 데이터
// 특징: 시간순 데이터, 대량 순차 처리, 고정 윈도우
// 최적: 순환 배열
class StockPriceWindow {
constructor(windowSize = 100) {
this.prices = new Array(windowSize);
this.timestamps = new Array(windowSize);
this.index = 0;
this.size = 0;
this.capacity = windowSize;
}
// O(1) - 새 가격 데이터 추가
addPrice(price, timestamp) {
this.prices[this.index] = price;
this.timestamps[this.index] = timestamp;
this.index = (this.index + 1) % this.capacity;
if (this.size < this.capacity) this.size++;
}
// O(n) - 평균 가격 계산 (배열 순회의 캐시 효율 이점)
getAveragePrice() {
let sum = 0;
for (let i = 0; i < this.size; i++) {
sum += this.prices[i];
}
return sum / this.size;
}
}
// 의사결정 트리 함수
function chooseDataStructure(requirements) {
const {
randomAccessFrequency, // 0-100: 랜덤 접근 빈도
insertDeleteFrequency, // 0-100: 중간 삽입/삭제 빈도
maxSize, // 예상 최대 크기
isFixedSize, // 크기 고정 여부
memoryConstrained // 메모리 제약 여부
} = requirements;
// 의사결정 로직
if (randomAccessFrequency > 70) {
return {
structure: 'Array',
reason: '랜덤 접근이 주요 연산이므로 O(1) 접근이 가능한 배열이 최적'
};
}
if (insertDeleteFrequency > 50 && maxSize > 1000) {
return {
structure: 'LinkedList',
reason: '빈번한 중간 삽입/삭제와 큰 데이터셋에서는 연결 리스트가 효율적'
};
}
if (isFixedSize && maxSize < 10000) {
return {
structure: 'Array',
reason: '고정 크기의 중소 규모 데이터는 배열의 캐시 효율이 유리'
};
}
if (!isFixedSize && memoryConstrained) {
return {
structure: 'Array with growth strategy',
reason: '메모리 제약이 있으나 동적 크기가 필요하면 신중한 재할당 전략 사용'
};
}
if (maxSize === Infinity) {
return {
structure: 'LinkedList',
reason: '크기를 예측할 수 없으면 무제한 성장 가능한 연결 리스트'
};
}
// 기본 권장사항
return {
structure: 'Array',
reason: 'JavaScript에서는 대부분의 경우 최적화된 내장 Array가 최선'
};
}
// 예시 사용
console.log(chooseDataStructure({
randomAccessFrequency: 80,
insertDeleteFrequency: 20,
maxSize: 100,
isFixedSize: true,
memoryConstrained: false
}));
// { structure: 'Array', reason: '랜덤 접근이 주요 연산이므로 O(1) 접근이 가능한 배열이 최적' }
설명
이것이 하는 일: 위 코드는 세 가지 실무 시나리오(게임 인벤토리, 브라우저 히스토리, 주식 데이터)를 통해 각각에 최적화된 자료구조를 보여줍니다. 또한 의사결정 함수를 제공하여 요구사항에 따른 선택 과정을 자동화합니다.
첫 번째 시나리오인 GameInventory는 배열이 완벽한 선택입니다. 게임 인벤토리는 40개 같은 고정된 슬롯 수를 가지며, 플레이어가 "5번 슬롯에 있는 아이템을 확인"하거나 "3번과 7번 슬롯을 교환"하는 랜덤 접근이 주요 연산입니다.
배열의 O(1) 인덱스 접근과 교환 연산이 이 사용 패턴에 정확히 일치합니다. 또한 슬롯 수가 고정되어 있어 재할당 걱정도 없습니다.
두 번째 시나리오인 BrowserHistory는 이중 연결 리스트가 이상적입니다. 사용자가 새 페이지를 방문하면 현재 위치 이후의 히스토리를 모두 삭제해야 하는데, 연결 리스트는 포인터 조작만으로 O(1)에 가능합니다.
back()과 forward()도 prev/next 포인터를 따라가기만 하면 되어 매우 효율적입니다. 히스토리 개수도 무제한이므로 동적 크기 조정이 필요 없는 연결 리스트가 완벽합니다.
세 번째 시나리오인 StockPriceWindow는 순환 배열이 최고의 선택입니다. 최근 100개의 가격만 유지하는 슬라이딩 윈도우 패턴에서, 새 데이터가 들어오면 가장 오래된 데이터를 덮어쓰면 됩니다.
순환 배열은 이를 자연스럽게 처리하며, 평균 계산 같은 순차 처리에서 배열의 캐시 효율이 큰 이점을 제공합니다. 실시간 처리에서 이런 성능 차이가 누적되면 매우 큽니다.
chooseDataStructure 함수는 정량적 기준을 제공합니다. randomAccessFrequency가 70% 이상이면 배열의 O(1) 접근 성능이 결정적입니다.
insertDeleteFrequency가 50% 이상이고 데이터가 1000개 이상이면 연결 리스트의 O(1) 삽입/삭제가 배열의 O(n)보다 훨씬 유리합니다. 이런 임계값들은 실제 벤치마크와 경험에서 나온 것입니다.
크기가 예측 불가능한 경우(maxSize === Infinity)는 연결 리스트를 권장합니다. 배열은 재할당 시 전체 복사가 필요하므로 급격한 성장에 취약합니다.
반면 작은 고정 크기 데이터(< 10000)는 배열의 메모리 효율과 캐시 친화성이 압도적으로 유리합니다. 여러분이 실무에서 이 코드를 활용할 때는 먼저 여러분의 요구사항을 정량화하세요.
"자주"나 "가끔"이 아니라 "전체 연산의 70%가 랜덤 접근"처럼 구체적인 수치로 표현하세요. 그런 다음 chooseDataStructure 함수 같은 체크리스트를 적용하여 객관적인 선택을 하세요.
마지막으로 실제 데이터로 프로토타입을 만들어 검증하세요.
실전 팁
💡 처음에는 단순하게 시작하세요. JavaScript에서는 내장 Array로 시작하고, 성능 문제가 실제로 발생할 때 최적화하세요.
💡 성능 측정 없이 추측하지 마세요. console.time()이나 performance.now()로 실제 병목을 확인한 후 자료구조를 변경하세요.
💡 하이브리드 접근도 고려하세요. 예를 들어, 자주 접근하는 상위 100개는 배열로, 나머지는 연결 리스트로 관리하는 방식도 효과적입니다.
💡 라이브러리를 활용하세요. collections.js나 immutable.js 같은 검증된 라이브러리는 이미 최적화가 되어 있습니다.
💡 미래의 확장성도 고려하세요. 지금은 100개 데이터지만 1년 후 10만 개가 될 수 있다면, 처음부터 확장 가능한 구조를 선택하세요.
8. JavaScript 특화 고려사항 - 언어 특성과 최적화
시작하며
여러분이 Python이나 Java에서 사용하던 자료구조 패턴을 JavaScript로 그대로 옮겼을 때, 예상과 다른 성능을 경험한 적 있나요? JavaScript는 동적 타입 언어이자 가비지 컬렉션을 사용하는 인터프리터 언어로, 저수준 언어와는 다른 특성을 가집니다.
이런 차이를 모르고 코딩하면 성능 저하와 메모리 누수가 발생합니다. JavaScript 엔진(V8, SpiderMonkey 등)은 내부적으로 다양한 최적화를 수행하는데, 이를 방해하는 코드는 10배 이상 느려질 수 있습니다.
특히 타입 변경, 객체 형태 변화, 희소 배열 등이 주범입니다. 바로 이럴 때 필요한 것이 JavaScript 특화된 자료구조 지식입니다.
언어의 특성을 이해하고 엔진 최적화를 활용하면, 이론적으로 동일한 알고리즘도 실제로는 훨씬 빠르게 동작합니다.
개요
간단히 말해서, JavaScript의 Array는 다른 언어의 배열과 다릅니다. 실제로는 해시맵에 가까운 객체이며, 엔진이 사용 패턴을 분석하여 내부적으로 최적화된 형태로 변환합니다.
이 과정을 이해하면 더 빠른 코드를 작성할 수 있습니다. JavaScript 자료구조의 특수성이 중요한 이유는 언어 자체의 설계 철학 때문입니다.
유연성을 위해 동적 타이핑을 채택했지만, 이는 성능 최적화를 어렵게 만듭니다. 예를 들어, 웹 애플리케이션의 실시간 데이터 처리, SPA의 대규모 상태 관리, Node.js의 고성능 서버 등에서 이런 세부사항이 결정적 차이를 만듭니다.
JavaScript 엔진의 최적화 전략을 살펴보겠습니다. V8 엔진은 배열을 "요소가 모두 같은 타입"이고 "빈 공간 없이 연속적"일 때 내부적으로 C++ 배열처럼 최적화합니다(Fast Elements).
하지만 타입이 섞이거나 희소 배열이 되면 해시맵 모드(Dictionary Elements)로 전환되어 느려집니다. 핵심 최적화 포인트는 다음과 같습니다: 첫째, 단일 타입 유지(monomorphic) - 배열의 모든 요소를 같은 타입으로 유지하세요.
둘째, 희소 배열 방지 - delete 연산 대신 null 할당을 사용하세요. 셋째, 객체 형태 고정(hidden class) - 동일한 구조의 객체를 일관되게 생성하세요.
넷째, TypedArray 활용 - 숫자 데이터는 Int32Array나 Float64Array를 사용하세요. 이러한 패턴들이 엔진 최적화를 최대한 활용합니다.
코드 예제
// JavaScript 특화 최적화 기법
// ❌ 나쁜 예: 타입 혼합으로 최적화 불가
function slowArrayUsage() {
const arr = [1, 2, 3];
arr.push("string"); // 타입 변경 - Dictionary Elements로 전환
arr.push({}); // 더욱 느려짐
arr.push(true);
// 이제 arr는 해시맵처럼 동작하여 느림
return arr[0]; // O(1)이지만 상수 요인이 큼
}
// ✅ 좋은 예: 단일 타입 유지
function fastArrayUsage() {
const arr = [1, 2, 3]; // 모두 숫자
arr.push(4);
arr.push(5);
// Fast Elements 모드 유지로 최적화
return arr[0]; // 진짜 O(1)
}
// ❌ 나쁜 예: 희소 배열 생성
function slowSparseArray() {
const arr = new Array(1000);
arr[0] = 1;
arr[999] = 2;
// 중간이 비어있어 희소 배열 - Dictionary Elements
for (let i = 0; i < arr.length; i++) {
// 매우 느린 순회
if (arr[i] !== undefined) {
console.log(arr[i]);
}
}
}
// ✅ 좋은 예: 밀집 배열 유지
function fastDenseArray() {
const arr = [];
for (let i = 0; i < 1000; i++) {
arr[i] = i; // 연속적으로 채움
}
// Fast Elements 유지로 빠른 순회
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
}
// TypedArray 활용 - 숫자 데이터 최적화
class OptimizedBuffer {
constructor(size) {
// 일반 배열 대신 TypedArray 사용
this.data = new Float64Array(size); // 8바이트 실수 전용
this.size = size;
}
// 메모리 레이아웃이 C++ 배열과 동일
fill(value) {
for (let i = 0; i < this.size; i++) {
this.data[i] = value; // 타입 체크 없이 직접 할당
}
}
// SIMD 최적화 가능
sum() {
let total = 0;
for (let i = 0; i < this.size; i++) {
total += this.data[i]; // 벡터 연산으로 최적화 가능
}
return total;
}
}
// Hidden Class 최적화 - 객체 형태 일관성
// ❌ 나쁜 예: 객체 형태가 계속 변경됨
function slowObjectCreation() {
const objects = [];
// 각 객체가 다른 형태 - 여러 hidden class 생성
objects.push({ x: 1 });
objects.push({ x: 1, y: 2 });
objects.push({ y: 2, x: 1 }); // 속성 순서도 다름!
// 엔진이 최적화하기 어려움
}
// ✅ 좋은 예: 일관된 객체 형태
function fastObjectCreation() {
const objects = [];
// 모든 객체가 동일한 형태 - 단일 hidden class
objects.push({ x: 1, y: 0 });
objects.push({ x: 1, y: 2 });
objects.push({ x: 2, y: 1 });
// 엔진이 효율적으로 최적화
}
// 링크드 리스트도 JavaScript에서는 배열이 더 나을 수 있음
function compareRealPerformance(size) {
// 연결 리스트 (이론적으로 O(1) 삽입)
const list = new LinkedList();
console.time('LinkedList build');
for (let i = 0; i < size; i++) {
list.append(i);
}
console.timeEnd('LinkedList build');
console.time('LinkedList traverse');
let current = list.head;
let sum1 = 0;
while (current) {
sum1 += current.data;
current = current.next;
}
console.timeEnd('LinkedList traverse');
// 배열 (이론적으로 O(1) 평균)
const arr = [];
console.time('Array build');
for (let i = 0; i < size; i++) {
arr.push(i);
}
console.timeEnd('Array build');
console.time('Array traverse');
let sum2 = 0;
for (let i = 0; i < arr.length; i++) {
sum2 += arr[i];
}
console.timeEnd('Array traverse');
console.log('배열이 연결 리스트보다 순회에서 5-10배 빠름 (캐시 + 최적화)');
}
compareRealPerformance(100000);
// 가비지 컬렉션 고려
class MemoryEfficientQueue {
constructor(capacity) {
this.items = new Array(capacity);
this.front = 0;
this.rear = 0;
this.size = 0;
this.capacity = capacity;
}
enqueue(item) {
if (this.size === this.capacity) throw new Error('Full');
this.items[this.rear] = item;
this.rear = (this.rear + 1) % this.capacity;
this.size++;
}
dequeue() {
if (this.size === 0) throw new Error('Empty');
const item = this.items[this.front];
this.items[this.front] = null; // GC를 위해 명시적 null 할당
this.front = (this.front + 1) % this.capacity;
this.size--;
return item;
}
}
설명
이것이 하는 일: 위 코드는 JavaScript 엔진의 내부 최적화 메커니즘을 활용하는 방법과 피해야 할 안티패턴을 보여줍니다. 동일한 알고리즘도 작성 방식에 따라 성능이 크게 달라집니다.
첫 번째로, slowArrayUsage와 fastArrayUsage의 차이는 타입 일관성입니다. JavaScript 엔진(특히 V8)은 배열을 처음 생성할 때 요소의 타입을 추적합니다.
모든 요소가 SMI(Small Integer, 31비트 정수)라면 가장 빠른 형태로 저장합니다. 하지만 문자열이나 객체가 섞이면 "polymorphic" 상태가 되어 일반 해시맵처럼 느려집니다.
실제로 2-3배 성능 차이가 납니다. 희소 배열과 밀집 배열의 차이는 더욱 극적입니다.
new Array(1000)을 생성하고 몇 개만 채우면, 엔진은 "이 배열은 대부분 비어있구나"라고 판단하여 Dictionary Elements 모드로 전환합니다. 이 모드에서는 인덱스 접근도 해시 검색이 필요하여 느립니다.
delete 연산자도 희소 배열을 만드므로 피해야 합니다. OptimizedBuffer 클래스는 TypedArray의 강력함을 보여줍니다.
Float64Array는 실제로 C++의 double 배열과 동일한 메모리 레이아웃을 가집니다. 타입 체크, 박싱/언박싱 오버헤드가 전혀 없으며, SIMD(Single Instruction Multiple Data) 최적화도 가능합니다.
대량의 숫자 데이터(이미지 처리, 과학 계산, 게임 물리)에서는 일반 배열보다 10배 이상 빠를 수 있습니다. Hidden Class 최적화는 객체 지향 코드에서 중요합니다.
V8은 동일한 속성을 가진 객체들에 대해 "hidden class"(다른 엔진에서는 "shape" 또는 "structure")를 생성하여 속성 접근을 최적화합니다. 객체를 생성할 때마다 속성 순서나 타입이 다르면 각각 다른 hidden class가 생성되어 최적화가 불가능합니다.
생성자 함수나 클래스를 사용하여 일관된 형태를 유지하세요. compareRealPerformance는 놀라운 사실을 보여줍니다.
이론적으로 연결 리스트가 유리한 상황에서도, JavaScript에서는 배열이 더 빠른 경우가 많습니다. 이유는 다중적입니다: 배열의 고도한 내부 최적화, 캐시 효율, 노드 생성의 오버헤드, 포인터 역참조 비용 등.
10,000개 미만의 데이터에서는 거의 항상 배열이 승리합니다. MemoryEfficientQueue는 가비지 컬렉션을 고려한 코드입니다.
JavaScript는 자동 메모리 관리를 하지만, 큰 객체에 대한 참조를 오래 유지하면 메모리 누수가 발생할 수 있습니다. dequeue 시 명시적으로 null을 할당하여 "이 객체는 더 이상 필요 없다"고 GC에 알려주는 것이 좋습니다.
여러분이 JavaScript로 고성능 자료구조를 작성할 때는 이런 언어 특성을 항상 염두에 두세요. Chrome DevTools의 Performance 탭에서 "Optimize/Deoptimize" 이벤트를 확인하여 여러분의 코드가 최적화되는지 검증할 수 있습니다.
실전 팁
💡 배열에 여러 타입을 저장해야 한다면, 각 타입별로 별도 배열을 만드세요. {numbers: [], strings: []} 형태가 [{type: 'number', value: 1}]보다 훨씬 빠릅니다.
💡 대량의 숫자 데이터는 무조건 TypedArray를 사용하세요. Float64Array, Int32Array 등이 일반 배열보다 메모리 효율도 좋고 속도도 빠릅니다.
💡 객체 풀(Object Pool) 패턴을 사용하면 가비지 컬렉션 압력을 줄일 수 있습니다. 노드를 매번 생성/삭제하지 말고 재사용하세요.
💡 arr[arr.length] = value가 arr.push(value)보다 약간 빠르지만, 가독성을 해치므로 성능이 정말 중요한 핫스팟에만 사용하세요.
💡 Chrome DevTools의 Memory 프로파일러로 객체 할당을 추적하세요. 예상치 못한 메모리 사용을 발견할 수 있습니다. 이상으로 "배열 기반 vs 연결 리스트 기반 자료구조"에 대한 8개의 상세한 카드 뉴스를 작성했습니다. 각 카드는 실무에서 바로 활용할 수 있는 깊이 있는 내용으로 구성되었으며, 초급 개발자도 이해할 수 있도록 친근한 블로그 스타일로 작성했습니다.