자료구조 선택과 배열·연결 리스트
배열과 연결 리스트의 구조·연산 비용을 비교하고, 사용 조건에 맞는 자료구조를 선택한다.
자료구조와 추상 자료형
자료구조는 탐색·삽입·삭제 같은 연산을 효율적으로 수행할 수 있도록 데이터를 저장하고 관계를 표현하는 구체적인 방식이다. 추상 자료형(Abstract Data Type, ADT)은 구현 방법과 무관하게 데이터의 값과 허용되는 연산을 정의한 논리적 규격이다. 예를 들어 스택 ADT의 push와 pop은 배열로도, 연결 리스트로도 구현할 수 있다.
자료구조를 선택할 때는 이름보다 다음 조건을 먼저 확인한다.
- 어떤 연산을 가장 자주 수행하는가?
- 데이터 크기가 고정적인가, 자주 변하는가?
- 삽입·삭제할 위치나 선행 노드를 이미 알고 있는가?
- 순방향만 필요한가, 역방향 또는 반복 순회도 필요한가?
- 추가 메모리보다 접근 속도와 연속 저장의 이점이 더 중요한가?
배열
배열은 일반적으로 같은 크기의 원소를 연속된 메모리 공간에 저장하고 인덱스로 구분한다. 시작 인덱스를 L, 원소 한 개의 크기를 w라고 하면 1차원 배열 원소의 위치는 다음과 같이 계산할 수 있다.
A[i]의 주소 = 시작 주소 + (i - L) × w
인덱스만 알면 계산 한 번으로 원소 위치를 찾으므로 임의 접근(random access)은 O(1)이다. 다만 인덱스 접근과 값 검색은 다르다. 정렬되지 않은 배열에서 특정 값을 찾는 작업은 최악의 경우 모든 원소를 확인하므로 O(n)이며, 정렬된 배열은 이진 검색으로 O(log n)에 검색할 수 있다.
배열 중간에 원소를 삽입하면 뒤쪽 원소를 이동해 빈칸을 만들어야 하고, 삭제하면 빈자리를 메우기 위해 원소를 당겨야 한다. 따라서 일반적인 중간 삽입·삭제는 O(n)이다. 남는 용량이 있는 동적 배열의 끝에 추가하는 작업은 보통 O(1)이지만, 용량이 부족해 더 큰 공간을 할당하고 기존 원소를 복사하는 순간에는 O(n)이 걸릴 수 있다.
연결 리스트
연결 리스트는 각 노드(node)가 데이터와 다른 노드를 가리키는 링크를 가진 자료구조다. 노드가 메모리에 연속해서 놓일 필요가 없으므로 크기를 유연하게 늘리거나 줄일 수 있다. 그러나 i번째 노드로 바로 이동할 수 없고 첫 노드부터 링크를 따라가야 하므로 임의 위치 접근과 일반적인 값 검색은 O(n)이다.
연결 리스트의 삽입·삭제가 O(1)이라는 설명에는 조건이 붙는다. 삽입할 위치의 선행 노드를 이미 알고 있어야 하며, 단일 연결 리스트에서 중간 노드를 삭제하려면 일반적으로 그 노드의 선행 노드도 알고 있어야 한다. 위치나 값을 먼저 찾아야 한다면 탐색 O(n)이 추가되므로 전체 작업은 O(n)이 될 수 있다.
연결 리스트의 종류
| 종류 | 링크 구성 | 특징 |
|---|---|---|
| 단일 연결 리스트 | 다음 노드 링크 | 순방향으로만 이동하며 구조가 단순하다. |
| 이중 연결 리스트 | 이전·다음 노드 링크 | 양방향 이동이 가능하고, 대상 노드를 알고 있으면 링크 수정으로 삭제하기 쉽다. 대신 링크 저장 공간이 더 필요하다. |
| 원형 연결 리스트 | 마지막 노드가 첫 노드를 가리킴 | 어느 노드에서 시작해도 순환할 수 있다. 반복 처리에서는 시작 노드로 돌아왔는지 확인해야 한다. |
연결 리스트에서 첫 노드나 마지막 노드를 삭제하면 경계 참조도 갱신한다. 원소가 하나뿐일 때의 삭제는 head와 tail 모두를 빈 상태로 만드는 특수 경계 사례다.
이중 연결 리스트의 중간 노드를 삭제하려면 선행 노드의 next와 후행 노드의 prev를 서로 연결한다. 한 방향만 갱신하면 순방향과 역방향 순회 결과가 달라진다.
원형 리스트는 null 도달이 아니라 시작 노드의 재방문으로 한 바퀴를 판별한다. 값의 중복이 허용되므로 데이터 값이 아닌 노드 식별을 비교한다.
배열과 연결 리스트의 연산 비교
| 연산 | 배열 | 연결 리스트 | 판단 조건 |
|---|---|---|---|
| 인덱스로 i번째 원소 접근 | O(1) | O(n) | 연결 리스트는 앞에서부터 순차 이동한다. |
| 정렬되지 않은 데이터의 값 검색 | O(n) | O(n) | 접근 O(1)과 검색 O(1)을 혼동하지 않는다. |
| 중간 삽입 | O(n) | O(1)* | * 선행 노드를 이미 알고 있을 때이며, 위치 탐색은 별도다. |
| 중간 삭제 | O(n) | O(1)* | * 단일 리스트는 선행 노드, 이중 리스트는 대상 노드를 알고 있을 때다. |
| 끝에 원소 추가 | 여유 공간이 있으면 O(1) | 꼬리 포인터가 있으면 O(1) | 배열 재할당이나 꼬리 탐색이 필요하면 O(n)이 될 수 있다. |
선택 기준
배열이 적합한 경우
- 인덱스를 이용한 조회가 매우 잦다.
- 원소 수가 비교적 안정적이다.
- 추가 링크 저장 공간을 줄이고 연속된 데이터를 순차 처리하려 한다.
연결 리스트가 적합한 경우
- 크기가 자주 변한다.
- 이미 알고 있는 노드 주변에서 삽입·삭제가 자주 발생한다.
- 양방향 이동이나 원형 순회가 필요하다.
단순히 “삽입·삭제가 많다”는 이유만으로 연결 리스트를 선택해서는 안 된다. 매번 삽입 위치를 처음부터 찾아야 한다면 탐색 비용 때문에 장점이 줄어든다.
짧은 적용 예시
배열 [10, 20, 30]에서 10 뒤에 15를 삽입하려면 20과 30을 오른쪽으로 이동해야 한다. 단일 연결 리스트라면 새 노드의 다음 링크를 기존 20 노드로 연결하고, 10 노드의 다음 링크를 새 노드로 바꾸면 된다. 링크 수정 자체는 O(1)이지만 10 노드를 값으로 찾아야 한다면 그 탐색에는 O(n)이 걸릴 수 있다.