컴퓨터가 데이터를 메모리에 저장하는 가장 기본적인 두 가지 방법입니다. 배열(Array)은 메모리 공간에 빈틈없이 데이터를 나열하며, 연결 리스트(Linked List)는 데이터와 포인터(다음 데이터를 가리키는 주소)를 쌍으로 묶어 메모리 곳곳에 흩어진 채로 자유롭게 이어 나갑니다.
1. 시각적 구조 비교
2. 성능 및 특징 비교 (시간 복잡도)
연산 (Operation)
배열 (Array)
연결 리스트 (Linked List)
상세 설명
인덱스 접근 (Access)
O(1) 🚀
O(N)
배열은 메모리 주소 계산으로 즉시 접근 가능. 반면 연결 리스트는 처음부터 순차적으로 포인터를 따라가야 합니다.
탐색 (Search)
O(N)
O(N)
특정 '값'을 찾으려면 둘 다 전체를 뒤져야 합니다. (단, 정렬된 배열은 이진 탐색으로 O(log N) 가능)
맨 뒤 삽입/삭제
O(1)
O(1) (Tail 포인터 시)
배열의 맨 뒤나, Tail 포인터를 가진 연결 리스트의 맨 뒤 조작은 매우 빠릅니다.
중간 삽입/삭제
O(N)
O(1) 🚀 (위치 안다면)
배열은 중간에 끼워넣기 위해 뒤의 모든 요소를 밀어야 하지만, 연결 리스트는 포인터만 '딸깍' 연결해주면 끝납니다.
💡 실무 지식: 배열의 은밀한 무기, 캐시 지역성(Cache Locality)
이론적으로 중간 삽입/삭제가 빈번하면 연결 리스트가 유리해 보이지만, 실제 물리적인 CPU 환경에서는 다릅니다. 배열은 연속된 메모리를 차지하므로 CPU 캐시(Cache)에 한 번에 왕창 로드되어 엄청나게 빠른 속도를 자랑합니다. (공간 지역성) 반면 흩어져 있는 연결 리스트는 캐시 미스(Cache Miss)가 자주 발생하여 오히려 배열보다 실제 속도가 느린 경우가 많습니다. 현대 프로그래밍 언어들은 대부분 배열(가변 배열)을 기본으로 사용합니다.
// 📂 LinkedList.js (JavaScript)
// 자바스크립트 클래스를 활용한 단순 연결 리스트 구현
class Node {
constructor(data) {
this.data = data;
this.next = null; // 다음 노드를 가리키는 포인터
}
}
class LinkedList {
constructor() {
this.head = null; // 리스트의 시작점
}
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
printList() {
let current = this.head;
const result = [];
while (current) {
result.push(current.data);
current = current.next;
}
console.log(result.join(" -> "));
}
}
// 📂 main.js (사용 예시)
// 1. 배열(Array) 사용
const arr = [10, 20, 30];
arr.push(40);
console.log("Array:", arr);
// 2. 연결 리스트(LinkedList) 사용
const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.append(40);
process.stdout.write("LinkedList: ");
list.printList();
