🚂 배열(Array) · 동적 배열(Dynamic Array) · 연결 리스트(Linked List) 비교 정리

1. 배열 (Array) 

배열이란 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조다. 각 요소는 인덱스를 통해 접근할 수 있으며 인덱스는 0부터 시작한다.

배열의 요소들이 동일한 타입인 이유는 각 요소의 크기가 같아야 인덱스를 이용해 데이터의 위치를 수학적으로 계산할 수 있기 때문이다. 데이터의 크기가 일정하면 시작 주소 + (데이터 크기 * 인덱스) 라는 연산을 통해 특정 위치의 요소에 즉시 접근할 수 있다.

또한 배열은 연속된 메모리 공간에 저장되므로 인접한 데이터가 함께 캐시에 로드될 가능성이 높아 캐시 히트율이 높다.

이러한 구조적 특성 때문에 배열은 다음과 같은 특징을 가진다.

- 정적 할당

배열은 생성 시 크기를 지정해야 하며 한 번 정해진 크기는 변경할 수 없다. 이는 배열이 연속된 메모리 공간을 한 번에 확보해야 하기 때문이다.

프로그램이 배열을 생성하면 운영체제(혹은 런타임 시스템)는 요청된 크기만큼의 메모리 공간을 미리 예약한다. 확보된 메모리 공간은 연속성을 유지해야 하므로 배열의 크기를 중간에 늘리려면 더 큰 연속 공간을 새로 확보하고 기존 데이터를 복사해야 한다. 따라서 기본적인 배열 구조에서는 크기 변경이 불가능하다.

- 인덱스를 통한 빠른 접근

배열은 동일한 크기의 데이터가 연속된 메모리 공간에 저장되므로 인덱스를 통해 특정 요소의 메모리 주소를 즉시 계산할 수 있다. 이 과정은 데이터의 개수와 무관하게 일정한 시간에 수행되므로 시간 복잡도는 O(1)이다. 이를 임의 접근(Random Access)이라고 한다.

- 중간 삽입/삭제에 비효율

배열은 연속적인 메모리 공간을 사용한다. 따라서 중간 위치에 데이터를 삽입하거나 삭제하면 그 뒤에 있는 모든 요소를 한 칸씩 이동시켜야 한다.

예를 들어 인덱스 i 위치에 새로운 요소를 삽입하는 경우 i 이후의 모든 요소를 오른쪽으로 한 칸씩 이동해야 하며 삭제의 경우에는 왼쪽으로 한 칸씩 당겨야 한다. 이 과정은 최악의 경우 전체 요소를 이동시켜야 하므로 시간 복잡도는 O(n)이다.

2. 동적 배열 (Dynamic Array)

동적 배열은 고정 크기를 가지는 배열의 제약을 보완하기 위한 자료구조다. 처음에는 일정한 크기의 배열로 시작하지만 저장 공간이 부족해지면 더 큰 배열을 새로 할당한 뒤 기존 데이터를 복사하여 크기를 확장한다.

이러한 방식 덕분에 인덱스를 통한 접근은 O(1)을 유지하면서도 크기를 유연하게 조절할 수 있다.

대표적인 동적 배열 구현으로는 Java의 ArrayList와 Python의 list가 있다.

- 가변적인 크기

동적 배열은 내부적으로는 배열을 사용하며 현재 저장된 요소의 개수(size)와 실제 할당된 배열의 크기(capacity)를 구분하여 관리한다.

처음에는 일정한 크기로 시작하며 저장 공간이 부족해지면 더 큰 배열을 새로 할당하고 기존 데이터를 복사한다. 이때 새로운 배열의 크기는 보통 기존 크기의 1.5배 또는 2배로 증가시킨다.

이처럼 배열의 크기를 기하급수적으로 확장하기 때문에 재할당은 가끔 발생하지만 전체적으로 보면 맨 뒤 삽입 연산은 분할 상환 시간 복잡도 O(1)을 가진다.

3. 연결 리스트 (Linked List)

연결 리스트는 데이터를 저장할 때 배열처럼 연속된 공간에 저장하지 않고 각 요소(노드)가 다음 요소를 포인터를 통해 가리키는 방식으로 연결된 선형 자료구조다.

배열은 연속된 메모리 구조를 사용하기 때문에 중간 삽입이나 삭제 시 요소 이동이 발생하며 O(n)의 시간이 소요될 수 있다. 이러한 배열의 한계를 보완하기 위해 데이터를 물리적으로 연속된 공간에 저장하지 않고 노드 간의 연결만을 관리하는 연결 리스트 구조가 등장하였다.

각 노드는 값과 다음 노드의 주소를 포함하며 구조에 따라 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)로 나뉜다.

- 중간 삽입/삭제에 효율적

연결 리스트는 특정 위치의 노드를 알고 있다면 포인터만 변경하여 효율적으로 중간에 데이터를 삽입하거나 삭제할 수 있다.

삽입할 위치의 이전 노드가 새로운 노드를 가리키도록 하고 새로운 노드가 다음 노드를 가리키도록 연결만 수정하는 식이다. 이러한 방식은 배열처럼 요소를 이동시킬 필요가 없기 때문에 삽입과 삭제 연산이 O(1)의 시간 복잡도를 가진다.

- 임의 접근 불가능

연결 리스트는 배열과 달리 메모리 상에서 연속된 구조를 가지지 않기 때문에 인덱스를 이용한 직접 접근이 불가능하다.

특정 위치의 요소에 접근하려면 시작 노드부터 순차적으로 다음 노드를 따라 이동해야 하므로 접근 시간은 최악의 경우 O(n)이 된다. 따라서 연결 리스트에서는 임의 접근이 지원되지 않는다.

- 메모리 오버헤드

연결 리스트는 데이터 외에도 노드 간 연결을 위해 포인터를 저장해야 하므로 추가적인 메모리 공간이 필요하다.

예를 들어 단일 연결 리스트의 경우 값 데이터와 함께 다음 노드의 주소를 저장해야 한다. 이처럼 배열에 비해 부가적인 메모리 사용(메모리 오버헤드)이 발생한다.