배열과 연결 리스트

핵심 요약

배열과 연결 리스트의 저장 방식, 주소 계산, 삽입·삭제·탐색 비용을 비교한다.

본문

자료구조를 선택하는 기준

자료구조는 데이터를 저장하는 모양뿐 아니라 접근, 탐색, 삽입, 삭제 비용을 결정한다.

• 배열: 연속된 메모리 공간에 같은 자료형의 원소를 저장한다.
• 연결 리스트: 떨어진 노드를 포인터 또는 참조로 연결한다.
• 선택 기준은 임의 접근 필요성, 삽입·삭제 위치, 원소 수의 변화, 추가 메모리 사용량이다.

배열

배열은 인덱스를 주소로 계산할 수 있어 임의 접근이 빠르다. 원소 하나의 크기를 w, 시작 주소를 base, 배열의 하한을 L이라 하면 1차원 배열의 주소는 다음과 같다.

address(A[i]) = base + (i - L) × w

예를 들어 A[1..10], 시작 주소 1000, 원소 크기 4바이트일 때 A[7]의 주소는 1000 + (7-1)×4 = 1024이다.

2차원 배열 A[L1..U1][L2..U2]에서 행 수를 N1, 열 수를 N2라고 하면 다음과 같다.

행 우선: base + ((i-L1)×N2 + (j-L2))×w
열 우선: base + ((j-L2)×N1 + (i-L1))×w

배열의 연산 비용

연결 리스트

연결 리스트의 노드는 데이터와 다음 노드를 가리키는 링크로 구성된다. 형태에 따라 다음과 같이 나뉜다.

• 단일 연결 리스트: 다음 노드만 가리킨다.
• 이중 연결 리스트: 이전·다음 노드를 모두 가리킨다.
• 원형 연결 리스트: 마지막 노드가 첫 노드를 가리킨다.

인덱스로 즉시 접근할 수 없으므로 k번째 노드를 찾으려면 앞에서부터 이동해야 한다. 삽입·삭제에 필요한 앞·뒤 링크를 이미 알고 있다면 링크 몇 개만 바꾸면 된다. 단일 연결 리스트에서 특정 노드 앞에 삽입하거나 그 노드를 삭제하려면 이전 노드를 알아야 한다.

메모리 배치와 캐시 지역성

배열의 장점은 주소 계산만이 아니다. 원소가 연속되어 있어 인접 원소를 순서대로 읽을 때 공간 지역성이 좋다. 연결 리스트는 노드가 흩어질 수 있어 같은 O(n) 순회라도 실제 실행시간은 배열보다 불리할 수 있다.

배열:        [10][20][30][40]        ← 연속 주소
단일 리스트: [10|●] → [20|●] → [30|●] → [40|null]

점근 복잡도가 같아도 실제 성능이 같지는 않다. 점근 복잡도는 증가율을 나타내며 캐시 적중률, 할당 비용, 포인터 추적 비용까지 같다는 뜻이 아니다.

동적 배열과 분할 상환 분석

초기 용량이 1인 동적 배열에서 공간이 가득 찰 때마다 용량을 2배로 늘린다고 하자. 확장할 때는 기존 원소를 새 배열로 복사한다. 한 번의 확장은 O(n)이지만, n번의 끝 삽입 동안 발생하는 전체 복사량은 1+2+4+...<2n이므로 삽입 1회의 분할 상환 비용은 O(1)이다.

def append(dynamic_array, value):
    if dynamic_array.size == dynamic_array.capacity:
        dynamic_array.resize(dynamic_array.capacity * 2)
    dynamic_array.data[dynamic_array.size] = value
    dynamic_array.size += 1

분할 상환은 연속된 연산의 총비용을 연산 수로 나누어 계산한다. 입력을 무작위로 가정하는 평균 시간 복잡도와 구분한다.

연결 리스트 삽입·삭제 추적

단일 연결 리스트에서 prev 뒤에 새 노드 x를 삽입할 때는 링크를 잃지 않도록 순서를 지킨다.

변경 전: prev ─────→ next
1단계 : x.next = prev.next
2단계 : prev.next = x
변경 후: prev → x → next

Node *x = malloc(sizeof(Node));
x->data = value;
x->next = prev->next;
prev->next = x;

삭제 대상 target의 이전 노드 prev를 알고 있다면 prev->next = target->next로 연결을 우회한다. 이중 연결 리스트에서는 앞·뒤 링크를 모두 수정해야 한다.

원형·더미 노드와 경계 조건

• 원형 리스트는 마지막 노드의 next가 첫 노드를 가리켜 순환 작업에 유리하다.
• 더미 헤드(sentinel)를 두면 첫 노드 삽입·삭제도 일반 노드와 같은 코드로 처리할 수 있다.
• 빈 리스트, 원소 1개, 첫·마지막 노드 변경은 포인터 문제의 대표 경계 조건이다.

계산형 예제

B[2..5][1..6]이 행 우선으로 저장되고 시작 주소가 2000, 원소 크기가 4바이트라 하자. 열 수는 6이므로 B[4][5] 주소는 다음과 같다.

2000 + ((4-2)×6 + (5-1))×4
= 2000 + 16×4
= 2064

열 우선이라면 행 수 4를 사용하여 2000 + ((5-1)×4 + (4-2))×4 = 2072가 된다.

선택 기준 정리