[자료구조] 1. 배열(Array)

리스트는 여러 개의 요소들을 나타내는 방식입니다. 자료구조론에서 이러한 리스트를 표현하는 밥법은 크게 두 가지로, 배열(Array)과 연결 리스트(Linked List)가 있습니다. 이번 글에서는 배열과 그 특성에 대해서 다루어보겠습니다.

배열

int arr[3] = {1, 2, 3};

 

배열은 같은 데이터 타입을 가지는 요소들의 sequence(시퀀스)입니다. 배열 속에서 각 요소들은 index(인덱스)로 접근가능합니다. N의 크기를 가지는 배열에서 첫 번째 요소의 인덱스는 0, 두 번째 요소의 인덱스는 1, 이런 식으로 증가하여 N번째(마지막) 요소의 인덱스는 N-1이 됩니다.

특징과 장점

같은 데이터 타입을 가지기 때문에 배열의 각 요소는 같은 크기를 가지게 됩니다. 같은 크기를 가진다는 점 덕분에 배열은 x번째 요소에 바로 접근이 가능합니다. 이것의 원리는 다음과 같습니다. 배열의 시작점의 메모리 주소, 즉 arr[0]의 메모리 주소를 0x0004라고 한다면, 그다음 arr[1]은 0x0008, arr[2]는 0x000C로 계산을 통해 주소를 즉시 알 수 있습니다. 이렇게 배열은 O(1) 시간만에 x번째 위치의 원소에 접근할 수 있습니다.

또한, 연결 리스트와 비교해 보면 배열은 메모리 영역에서 Heap뿐만 아니라 Stack에도 생성할 수 있는 장점이 있으며, 캐시 메모리에서의 지역성(cache locality)도 높을 것으로 기대됩니다.

 

즉, 배열은 이미 인덱스를 알고 있는 값에 대하여 매우 빠르게 접근이 가능하고, 접근이 빠르기에 수정 또한 빠르게 가능하다는 장점이 있습니다.

단점

그렇지만 배열에도 약점이 있습니다. 이러한 약점은 배열 사이에 데이터를 추가할 때 드러납니다. 배열 사이에 요소를 삽입하려면, 삽입할 장소 오른쪽의 모든 요소들을 한 칸씩 우측으로 이동해줘야 합니다. 그렇기 때문에 최악의 경우에는 배열의 모든 원소 N개를 다 오른쪽으로 이동(shift)해주어야 하기에 O(N)의 시간이 소요됩니다.

또한 배열 중간의 값을 삽입할 때뿐만이 아닌, 배열 중간의 값을 삭제할 때도 같은 이유로 O(N)의 시간이 소요됩니다.

구현

배열의 구현자체는 언어에서 기본적으로 제공됩니다. 그렇기에 배열의 삽입과 삭제 알고리즘에 대하여 알아보겠습니다.

삽입

 

삭제

동적 배열

동적 배열은 기존에 크기가 정해져 있다는 배열의 한계를 벗어난 크기 조정이 가능한 배열입니다. 다만 동적 배열이 특별한 알고리즘으로 구현되는것은 아니고, 동적 배열도 일반적인 배열을 이용하여 구현합니다. 그렇기에 배열 크기를 증가시킬 때에도 배열을 새로 생성하는 정도의 비용이 발생합니다.

이런 동적배열은 C++에서는 Vector, Java에서는 ArrayList 등으로 제공됩니다.

그렇다면 파이썬의 기본 배열은 동적 배열일까요? 일단은 그렇습니다. 파이썬은 동적 배열 개념을 기본 배열에 적용하고 있습니다. 그렇지만 파이썬의 리스트는 값의 포인터를 저장함으로써 str, int, float 등 다양한 데이터 타입을 한 배열에 저장할 수 있게 됩니다. 이로 인해 메모리 지역성이 감소하고 속도도 상대적으로 느려질 수 있습니다.

파이썬에서도 built-in list가 아닌 built-in array가 존재합니다. Medium, Python docs

즉 파이썬에서 같은 데이터타입으로 저장할 것이고, 속도가 중요하다면 built-in array나 numpy 등을 사용하는 게 좋습니다.