배열과 연결 리스트

1. 자료구조를 선택하는 기준

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

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

2. 배열

배열은 인덱스를 주소로 계산할 수 있어 임의 접근이 빠르다. 원소 하나의 크기를 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

배열의 연산 비용

3. 연결 리스트

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

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

인덱스로 즉시 접근할 수 없으므로 k번째 노드를 찾으려면 앞에서부터 이동해야 한다. 반면 삽입·삭제할 위치의 노드를 이미 알고 있다면 링크 몇 개만 바꾸면 된다.

4. 메모리 배치와 캐시 지역성

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

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

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

5. 동적 배열과 분할 상환 분석

용량이 가득 찰 때마다 보통 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

최악 1회 비용과 여러 연산에 걸친 평균 비용을 구분해야 한다.

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

단일 연결 리스트에서 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로 연결을 우회한다. 이중 연결 리스트에서는 앞·뒤 링크를 모두 수정해야 한다.

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

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

8. 계산형 예제

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가 된다.

9. 선택 기준 정리

최종 확인 문제

1. 행 우선 배열 A[1..4][0..5]의 시작 주소가 100, 원소 크기가 2바이트일 때 A[3][4]의 주소를 구하시오.
2. 동적 배열의 끝 삽입이 최악 O(n)이면서 분할 상환 O(1)인 이유를 설명하시오.
3. 단일 연결 리스트에서 prev 뒤에 x를 삽입할 때 링크 변경 순서를 쓰시오.
4. 배열 순회와 연결 리스트 순회가 모두 O(n)이어도 배열이 실제로 빠를 수 있는 이유는 무엇인가?
5. 연결 리스트 삽입을 무조건 O(1)이라고 하면 안 되는 조건을 설명하시오.