배열과 연결 리스트

배열은 동일한 자료형의 데이터 요소들이 연속된 메모리 공간에 순차적으로 저장된 자료구조이다. 각 요소는 인덱스라는 고유한 번호로 식별되며, 일반적으로 0부터 시작하는 정수 값을 가진다. 배열의 크기는 선언 시에 결정되며, 대부분의 프로그래밍 언어에서는 생성 후 크기를 변경하기 어렵다. 이렇게 연속된 메모리 블록을 할당받는 특성은 배열의 가장 기본적인 구조적 특징이다.

배열의 요소에 접근하려면 배열의 이름과 함께 대괄호([]) 안에 인덱스를 지정한다. 예를 들어, arr[3]은 배열 arr의 네 번째 요소를 의미한다. 이 접근 방식은 메모리 주소를 직접 계산할 수 있게 하여 매우 빠른 속도를 보장한다. 배열의 첫 번째 요소의 주소(기본 주소)와 각 요소의 크기, 그리고 요청된 인덱스를 알고 있으면, '기본 주소 + (인덱스 * 요소 크기)'라는 간단한 산술 연산으로 정확한 메모리 위치를 즉시 얻을 수 있다. 이 메커니즘을 랜덤 액세스라고 한다.

배열은 1차원 구조가 가장 일반적이지만, 2차원(행렬), 3차원 이상의 다차원 배열로도 선언하여 사용할 수 있다. 다차원 배열도 결국 모든 요소가 연속된 메모리에 배치되지만, 프로그래밍 언어에 따라 행 우선 또는 열 우선 방식으로 저장 순서가 달라질 수 있다.

배열의 가장 큰 장점은 인덱스를 통한 빠른 접근 속도이다. 모든 요소가 메모리상에 연속적으로 저장되어 있기 때문에, 첫 번째 요소의 주소와 인덱스 값만으로 특정 요소의 위치를 즉시 계산하여 접근할 수 있다. 이로 인해 임의 접근(랜덤 액세스)의 시간 복잡도는 O(1)이다. 또한, 연속된 메모리 공간을 사용하기 때문에 캐시 지역성이 좋아 순차 접근 시 성능이 매우 우수하다.

반면, 배열의 주요 단점은 크기가 고정되어 있다는 점이다. 배열을 선언할 때 그 크기를 미리 지정해야 하며, 실행 중에 크기를 쉽게 변경할 수 없다. 이는 메모리 사용의 비효율성을 초래할 수 있다. 또한, 배열 중간에 요소를 삽입하거나 삭제하는 작업은 비효율적이다. 해당 위치 이후의 모든 요소를 한 칸씩 이동시켜야 하기 때문에, 평균적으로 O(n)의 시간이 소요된다.

배열의 시간 복잡도는 연산의 종류에 따라 크게 달라진다. 인덱스를 통한 임의 접근은 메모리 주소를 직접 계산할 수 있어 상수 시간 O(1)에 수행된다. 마찬가지로, 특정 위치의 값을 수정하는 연산도 O(1)의 시간이 소요된다. 그러나 배열의 중간에 새로운 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동시켜야 하므로 최악의 경우 선형 시간 O(n)이 필요하다. 배열의 끝에서 삽입/삭제를 수행하는 경우는 O(1)로 간주할 수 있다.

연결 리스트의 시간 복잡도는 접근 방식에 따른 제약이 명확히 나타난다. 단일 연결 리스트에서 i번째 노드에 접근하려면 헤드 포인터부터 시작하여 순차적으로 탐색해야 하므로, 접근과 탐색 연산의 시간 복잡도는 O(n)이다. 반면, 삽입과 삭제 연산은 수행 위치에 따라 효율성이 다르다. 리스트의 시작 부분에서의 삽입/삭제는 O(1)로 매우 빠르다. 리스트의 중간이나 끝에서의 삽입/삭제도, 원하는 노드 위치에 대한 포인터를 이미 알고 있다면 링크 조정만으로 O(1)에 가능하다. 그러나 해당 노드를 찾는 탐색 과정이 필요하다면 전체 시간 복잡도는 O(n)이 된다.

다음 표는 두 자료 구조의 주요 연산에 대한 시간 복잡도를 비교하여 보여준다.

이러한 복잡도 차이는 각 자료 구조의 내부 구현 방식, 즉 연속적인 메모리 할당과 포인터로 연결된 노드 구조에서 직접적으로 기인한다.

연결 리스트는 데이터 구조의 일종으로, 데이터 요소들을 선형으로 나열하지만, 물리적인 메모리 상에서 연속적으로 위치하지 않는다. 각 데이터 요소는 노드라는 독립적인 객체에 저장되며, 노드들은 포인터 또는 링크를 통해 논리적인 순서로 연결된다.

단일 연결 리스트의 기본적인 노드 구조는 저장할 데이터 필드와 다음 노드를 가리키는 하나의 링크 필드로 구성된다. 데이터 필드는 정수, 문자열, 객체 등 어떤 자료형도 저장할 수 있다. 링크 필드는 메모리에서 다음 노드의 주소를 담는 참조 역할을 한다. 리스트의 시작점을 가리키는 헤드 포인터와 마지막 노드의 링크가 널 포인터를 가리키는 것이 일반적인 구조이다.

노드 구조의 변형으로는 이중 연결 리스트와 원형 연결 리스트가 있다. 이중 연결 리스트의 노드는 다음 노드뿐만 아니라 이전 노드도 가리키는 두 개의 링크 필드를 가진다. 원형 연결 리스트에서는 마지막 노드의 링크가 첫 번째 노드를 가리켜 순환 구조를 형성한다.

배열의 가장 큰 장점은 인덱스를 통한 빠른 접근 속도이다. 모든 요소가 메모리에 연속적으로 저장되어 있기 때문에, 특정 위치의 요소 주소를 간단한 계산으로 즉시 얻을 수 있다. 이로 인해 랜덤 접근이 매우 효율적이다. 또한, 메모리 공간 자체에 오버헤드가 거의 없어 데이터를 저장하는 데 필요한 최소한의 공간만 사용한다는 점도 장점이다.

반면, 배열의 주요 단점은 크기가 고정되어 있다는 점이다. 선언 시 지정한 크기를 프로그램 실행 중에 변경하기 어렵다. 필요한 데이터 양을 미리 알 수 없는 경우, 크기를 예측하여 여유롭게 할당하거나, 더 큰 새 배열을 만들어 데이터를 복사하는 작업이 필요하다. 또한, 배열 중간에 요소를 삽입하거나 삭제할 때는 해당 위치 이후의 모든 요소를 이동시켜야 하므로 비효율적일 수 있다.

이러한 특성으로 인해 배열은 데이터의 개수가 변하지 않거나, 조회가 매우 빈번하게 발생하며, 순차적이거나 임의의 위치로 빠르게 접근해야 하는 상황에 적합하다.

배열의 시간 복잡도는 연산의 종류에 따라 크게 달라진다. 인덱스를 이용한 임의 접근(읽기 또는 쓰기)은 메모리 주소를 직접 계산할 수 있으므로 O(1)의 상수 시간에 수행된다. 그러나 배열 중간에 요소를 삽입하거나 삭제하는 연산은, 해당 위치 이후의 모든 요소를 한 칸씩 이동시켜야 하므로 최악의 경우 O(n)의 선형 시간이 소요된다. 배열의 끝에서만 삽입과 삭제를 수행하는 특수한 경우(예: 스택)에는 요소 이동이 필요 없어 O(1)의 성능을 보인다.

반면, 연결 리스트의 시간 복잡도는 접근과 수정에서 배열과 대조적인 특성을 보인다. 연결 리스트는 물리적으로 연속된 메모리를 사용하지 않으므로 i번째 노드에 접근하기 위해서는 헤드 노드부터 시작하여 순차적으로 노드를 따라가야 한다. 이로 인해 임의 접근의 시간 복잡도는 O(n)이다. 그러나 리스트의 시작 또는 끝 지점에서의 삽입과 삭제는 O(1)로 매우 빠르다. 특히, 삽입이나 삭제할 노드의 위치에 대한 참조(포인터)를 이미 알고 있는 경우, 해당 위치에서의 연산도 참조 조정만으로 O(1)에 가능하다[8].

배열은 연속된 메모리 공간에 데이터를 저장하는 선형 자료 구조이다. 모든 요소가 물리적으로 인접해 있으며, 일반적으로 선언 시 크기가 고정된다. 이 연속성 덕분에 인덱스를 통한 랜덤 접근이 매우 효율적이다. 반면, 연결 리스트는 노드라는 개별적인 메모리 블록으로 구성되며, 각 노드는 데이터와 다음 노드의 위치를 가리키는 포인터를 포함한다. 노드들은 물리적으로 흩어져 있을 수 있으며, 포인터를 통해 논리적인 순서만 유지된다.

이러한 메모리 할당 방식의 차이는 각 자료 구조의 성격을 결정짓는다. 배열은 크기가 고정되어 있어, 할당된 메모리 공간을 초과하는 데이터를 저장하려면 더 큰 새로운 배열을 할당하고 기존 데이터를 모두 복사해야 하는 오버헤드가 발생한다. 연결 리스트는 필요할 때마다 새로운 노드를 동적으로 생성하여 연결하기 때문에, 이론적으로 메모리가 허용하는 한 데이터 개수에 제한이 없다.

다음 표는 두 자료 구조의 메모리 할당 방식을 요약하여 비교한다.

결과적으로, 배열은 메모리 지역성 덕분에 캐시 효율이 높지만, 크기 조정이 어렵다. 연결 리스트는 크기 조정이 유연하지만, 각 노드마다 포인터를 위한 추가 메모리가 필요하며, 데이터가 흩어져 있어 캐시 효율이 떨어질 수 있다.

배열에서 특정 인덱스의 요소에 접근하거나 값을 수정하는 작업은 상수 시간 O(1)에 수행된다. 이는 배열이 연속 메모리 공간에 할당되어 시작 주소와 인덱스, 요소 크기를 통해 즉시 물리적 주소를 계산할 수 있기 때문이다. 예를 들어, 정수형 배열 arr의 시작 주소가 base이고 정수 크기가 4바이트일 때, arr[5]의 주소는 base + (5 * 4)로 단순한 산술 연산으로 결정된다. 따라서 접근과 수정은 매우 빠르다.

반면, 연결 리스트에서 특정 위치의 노드에 접근하거나 수정하려면 일반적으로 선형 시간 O(n)이 소요된다. 단일 연결 리스트의 경우, 첫 번째 노드(헤드)부터 시작하여 원하는 위치에 도달할 때까지 다음 노드 포인터를 순차적으로 따라가야 한다. 이 과정은 순차 탐색과 유사하다. 따라서 리스트 중간이나 끝에 있는 요소를 수정하기 위해서는 먼저 그 위치까지 탐색하는 비용이 추가된다.

다음 표는 두 자료 구조의 접근 및 수정 성능을 요약한다.

요약하면, 임의의 위치에 대한 빈번한 읽기와 쓰기가 필요한 시나리오에서는 배열이 압도적인 성능 우위를 가진다. 연결 리스트는 이러한 작업에 비효율적이지만, 데이터의 동적 삽입과 삭제가 주요 연산인 경우 그 장점을 발휘한다.

배열에서의 삽입과 삭제 연산은 일반적으로 비효율적이다. 중간이나 시작 부분에 새로운 요소를 삽입하려면, 삽입 지점 이후의 모든 요소를 한 칸씩 뒤로 이동시켜 공간을 만들어야 한다. 마찬가지로, 중간이나 시작 부분의 요소를 삭제하면, 삭제된 자리를 메우기 위해 뒤에 있는 모든 요소를 한 칸씩 앞으로 이동시켜야 한다. 이로 인해 최악의 경우(배열의 첫 번째 위치에서 연산 수행) 시간 복잡도는 O(n)이 된다. 요소의 이동에 필요한 시간은 배열의 크기에 비례한다.

반면, 연결 리스트에서의 삽입과 삭제는 상대적으로 효율적이다. 리스트의 중간에 노드를 삽입하거나 삭제할 때, 물리적인 데이터 이동이 필요하지 않다. 대신, 삽입 위치의 앞뒤 노드가 가리키는 포인터만 변경하면 된다. 단일 연결 리스트의 경우, 삽입/삭제할 노드의 이전 노드 위치를 알고 있다면, 포인터 조작만으로 상수 시간에 연산을 완료할 수 있다. 이 경우 시간 복잡도는 O(1)이다.

그러나 연결 리스트에서도 삽입이나 삭제를 위한 노드 탐색 비용은 고려해야 한다. 특정 인덱스 위치에 삽입하거나 삭제하려면, 그 위치까지 순차적으로 탐색하여 노드를 찾아야 한다. 이 탐색 과정의 시간 복잡도는 O(n)이다. 따라서, 노드에 대한 참조(포인터)가 이미 주어진 상태에서의 삽입/삭제는 O(1)이지만, 인덱스만으로 연산을 수행할 경우 전체적인 시간 복잡도는 여전히 O(n)이 될 수 있다.

다음 표는 두 자료 구조의 삽입 및 삭제 연산 성능을 요약한다.

배열의 끝에서 이루어지는 삽입과 삭제는 예외적으로 효율적일 수 있다. 이미 할당된 공간이 충분하다면, 끝에 요소를 추가하거나 제거하는 것은 O(1) 시간에 가능하다.

배열은 선언 시 지정된 크기를 변경할 수 없으므로, 프로그램 실행 전에 필요한 데이터의 최대 개수를 알고 있을 때 유용하게 사용된다. 예를 들어, 한 학급의 학생 수가 30명으로 고정되어 있다면, 크기가 30인 배열을 선언하여 각 학생의 점수를 저장하는 방식이 효율적이다. 이는 메모리가 연속적으로 할당되어 캐시 지역성을 높이고, 인덱스를 통한 빠른 접근을 가능하게 한다.

고정된 크기의 데이터를 다루는 대표적인 예로는 룩업 테이블이 있다. 삼각함수의 사인(sin) 값처럼 미리 계산된 결과를 저장해 두고 필요할 때 즉시 참조하는 방식이다. 요일 이름, 월 이름, 국가 코드 표준과 같은 변경되지 않는 열거형 데이터를 저장할 때도 배열이 자주 사용된다.

이러한 고정 크기 저장 방식은 메모리 사용이 예측 가능하고 관리가 단순하다는 장점이 있다. 그러나 데이터 양이 선언된 크기를 초과할 경우 배열을 재할당하거나 다른 자료 구조로 전환해야 하는 제약이 따른다.

배열은 인덱스를 통한 직접 접근이 가능한 자료 구조이다. 각 요소는 연속된 메모리 공간에 저장되며, 인덱스는 해당 요소의 메모리 시작 주소에 대한 오프셋으로 작동한다. 따라서 특정 위치의 요소를 찾기 위해 순차적으로 탐색할 필요 없이, 인덱스 값을 이용해 즉시 계산하여 접근할 수 있다. 이 특성은 랜덤 접근이 매우 효율적임을 의미한다.

이러한 특성 덕분에 배열은 이진 탐색과 같은 알고리즘의 기반이 된다. 정렬된 배열에서 특정 값을 찾을 때, 중간 인덱스를 계산하여 값을 비교하고 탐색 범위를 절반씩 줄여나가는 방식은 랜덤 접근이 빠르지 않다면 불가능하다. 또한 해시 테이블의 버킷 배열, 행렬이나 이미지 픽셀 데이터와 같은 다차원 데이터를 표현할 때도 특정 좌표의 값을 즉시 읽거나 쓰는 작업이 빈번하게 발생한다.

반면, 연결 리스트는 요소들이 포인터로 연결되어 있어 특정 위치에 접근하려면 처음부터 순차적으로 탐색해야 한다. 따라서 검색이나 특정 인덱스의 수정이 빈번한 애플리케이션에서는 배열이 훨씬 유리한 성능을 보인다. 대규모 데이터에서 개별 요소에 대한 빠른 읽기와 쓰기가 요구될 때 배열은 거의 필수적인 선택이 된다.

연결 리스트는 데이터의 개수가 미리 정해지지 않거나 실행 시간에 크기가 자주 변하는 동적 데이터 구조를 구현하는 데 적합한 기초 자료 구조이다. 배열은 크기가 고정되어 있어 데이터 추가 시 재할당과 복사가 필요할 수 있지만, 연결 리스트는 노드 단위로 메모리를 동적으로 할당하고 포인터로 연결하기 때문에 데이터의 삽입과 삭제에 따라 유연하게 크기를 조정할 수 있다.

이러한 특성 덕분에 연결 리스트는 스택, 큐, 해시 테이블의 체이닝, 그래프의 인접 리스트 표현 등 다양한 고급 추상 자료형의 내부 구현에 널리 사용된다. 특히 메모리 할당이 빈번한 프로그램에서 메모리 관리의 효율성을 높일 수 있다.

또한, 연결 리스트는 운영체제의 프로세스 관리나 파일 시스템에서 불연속적인 디스크 블록을 관리하는 데에도 응용된다. 데이터의 물리적 저장 순서가 논리적 순서와 일치하지 않아도 포인터 연결만으로 순차적 접근이 가능하기 때문이다.

연결 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하는 상황에서 특히 유리한 성능을 보인다. 이는 연결 리스트의 물리적 저장 구조가 순차적이지 않기 때문이다. 새로운 노드를 삽입하거나 기존 노드를 삭제할 때, 인접한 다른 데이터 요소들을 이동시킬 필요 없이 포인터(또는 링크)만 변경하면 작업이 완료된다. 예를 들어, 단일 연결 리스트에서 노드를 삭제하려면 삭제할 노드의 이전 노드가 가리키는 포인터를 삭제할 노드의 다음 노드를 가리키도록 갱신하면 된다.

이러한 특성은 데이터의 순서가 자주 재구성되는 자료 구조를 구현할 때 핵심적인 장점이 된다. 대표적인 예로 스택과 큐가 있으며, 특히 다른 자료 구조의 기반이 되는 경우가 많다. 또한 그래프의 인접 리스트 표현이나 해시 테이블에서 체이닝 방식으로 충돌을 해결할 때도 연결 리스트가 널리 사용된다. 운영 체제의 프로세스 관리나 메모리 관리에서 동적으로 생성되고 소멸되는 객체들을 연결 리스트로 관리하는 경우도 흔하다.

다음 표는 삽입/삭제가 빈번한 작업에서의 활용 예를 정리한 것이다.

반면, 배열은 중간에 데이터를 삽입하거나 삭제할 경우, 공간을 만들거나 메꾸기 위해 나머지 요소들을 이동시켜야 하므로 O(n)의 시간이 소요된다. 따라서 데이터 집합의 크기가 고정되어 있고, 검색이나 순차 접근이 주 작업이며, 삽입/삭제가 드문 경우에 배열이 더 적합하다. 결국, 작업의 빈도와 패턴에 따라 배열과 연결 리스트 중 적절한 자료 구조를 선택하는 것이 성능에 결정적인 영향을 미친다.

배열의 고정된 크기와 메모리 할당 방식에서 발생하는 한계를 극복하기 위해 여러 배열 기반 변형 자료 구조가 개발되었다. 가장 대표적인 것은 동적 배열이다. 동적 배열은 초기에 일정한 크기로 메모리를 할당하고, 요소가 추가되어 공간이 부족해지면 더 큰 크기의 새로운 배열을 할당하여 기존 데이터를 복사하는 방식을 사용한다. 이 과정을 재할당이라고 한다. 재할당은 일반적으로 현재 용량의 두 배와 같은 배수로 이루어져, 빈번한 재할당을 방지하고 분할 상환 분석 관점에서 효율적인 성능을 제공한다[9].

동적 배열 외에도 특정 목적에 맞춘 배열 변형이 존재한다. 행렬이나 다차원 배열은 2차원 이상의 인덱스를 사용하여 표나 그리드 형태의 데이터를 표현한다. 가변 배열은 각 행의 길이가 다른 2차원 배열을 효율적으로 표현할 수 있다. 희소 배열은 대부분의 요소가 동일한 값(보통 0)인 배열을 저장 공간을 절약하며 표현하기 위한 자료 구조로, 연결 리스트나 사전 등의 다른 구조를 활용하여 구현된다.

이러한 배열 기반 변형들은 기본 배열의 빠른 랜덤 접근 장점을 유지하면서, 크기 제약이나 특수한 데이터 패턴에 따른 문제를 해결한다. 선택은 저장할 데이터의 특성과 필요한 연산의 빈도에 따라 이루어진다.

연결 리스트의 기본적인 단일 연결 형태를 확장하거나 특정 문제를 해결하기 위해 여러 변형 구조가 개발되었다. 가장 대표적인 변형은 이중 연결 리스트이다. 이 구조에서는 각 노드가 다음 노드뿐만 아니라 이전 노드의 주소도 함께 저장한다. 이로 인해 양방향 순회가 가능해져 특정 노드에서 이전 노드를 즉시 참조할 수 있으며, 노드 삭제 시 이전 노드의 포인터 갱신이 더 효율적이다. 그러나 각 노드에 추가적인 포인터 공간이 필요해 메모리 오버헤드가 증가한다는 단점이 있다.

다른 중요한 변형으로는 원형 연결 리스트가 있다. 이 구조에서는 리스트의 마지막 노드가 첫 번째 노드를 가리켜 순환 구조를 형성한다. 이는 큐나 라운드 로빈 스케줄링과 같이 순환적인 데이터 처리가 필요한 응용 프로그램에 유용하다. 원형 연결 리스트는 단일 연결 또는 이중 연결 방식으로 모두 구현될 수 있다.

다음은 주요 연결 리스트 변형들의 특징을 비교한 표이다.

이 외에도 특정 상황에 최적화된 다양한 변형이 존재한다. 예를 들어, 스킵 리스트는 여러 층의 연결 리스트를 사용하여 정렬된 데이터에 대한 검색 성능을 O(log n) 수준으로 향상시킨다. 또한, 메모리 풀과 함께 사용되거나, 노드에 추가적인 메타데이터를 포함하는 자기조직화 리스트와 같은 변형도 연구 및 활용된다.