배열 vs 연결 리스트

이 토픽을 마치면

배열과 연결 리스트의 메모리 구조 차이를 설명할 수 있고, 상황에 따라 어떤 것을 선택해야 하는지 판단할 수 있습니다.

배열 — 연속된 메모리

배열(Array)은 데이터를 메모리에 나란히 저장합니다.

메모리 주소:  100  104  108  112  116
            +----+----+----+----+----+
값:         | 10 | 20 | 30 | 40 | 50 |
            +----+----+----+----+----+
인덱스:       0    1    2    3    4

장점은 인덱스로 즉시 접근 가능합니다.

arr = [10, 20, 30, 40, 50]
print(arr[3])  # 40 — 즉시 접근 (O(1))

"3번째 칸"이라고 하면 시작 주소 + (3 × 크기) = 바로 그 위치. 몇 개가 있든 한 번에 찾습니다.

배열의 약점: 삽입과 삭제

[10, 20, 30, 40, 50]에서 인덱스 1에 15를 삽입하려면?

1단계: 20, 30, 40, 50을 모두 한 칸씩 뒤로 밀기
2단계: 빈 자리에 15 넣기

[10, 15, 20, 30, 40, 50]

데이터가 100만 개면, 맨 앞에 삽입할 때 100만 개를 전부 밀어야 합니다.

연결 리스트 — 흩어진 메모리

연결 리스트(Linked List)는 각 데이터가 다음 데이터의 위치를 기억합니다.

[10|→] → [20|→] → [30|→] → [40|→] → [50|∅]

각 노드 = 값 + 다음 노드의 주소(포인터)

메모리에 연속으로 있을 필요가 없습니다. 각 노드가 "다음은 어디야"를 알고 있으면 됩니다.

연결 리스트의 장점: 삽입과 삭제

[10|→] → [20|→] → [30|→]에서 20 뒤에 25 삽입:

1단계: 새 노드 [25|→] 생성
2단계: 20의 포인터를 25로, 25의 포인터를 30으로 변경

[10|→] → [20|→] → [25|→] → [30|→]

다른 노드를 밀 필요가 없습니다. 포인터 2개만 바꾸면 끝. O(1).

연결 리스트의 약점: 접근

# "3번째 값이 뭐야?"
# 배열: arr[3] → 즉시 (O(1))
# 연결 리스트: 처음부터 1→2→3 따라가야 함 (O(n))

인덱스가 없으므로 n번째 값을 찾으려면 처음부터 n번 따라가야 합니다.

비교 정리

선택 기준

실무에서는 대부분 배열(Python의 list, JavaScript의 Array)을 씁니다. 현대 언어의 동적 배열은 크기 조절도 자동이고, CPU 캐시에 유리합니다. 연결 리스트는 특수한 상황(큐, 스택 구현, 대용량 삽입/삭제)에서 사용합니다.