[DATA STRUCTURE] 02. 배열(Array)

 

//C
int nArr[5] = { 1,2,3,4,5 };

//C++ with STL
std::array<int, 5> num = { 1,2,3,4,5 };

 

 

주요 특징

 

1. 순차적인 메모리 할당 : 데이터 요소를 연속적으로 메모리에 할당한다.

(각 요소는 고유한 인덱스를 가지며, 인덱스를 사용해 배열 요소에 바로 접근할 수 있다.)

 

2. 고정 크기 : 일반적으로 정적인 크기를 가지며 이 크기는 런타임중 변경이 불가능하다.

 

3. 메모리 효율성 : 데이터 요소를 연속적으로 저장하므로 추가적인 링크를 가지지 않으므로 구조가 간단하다.

 

4. 다차원 확장 : 다차원 배열로 확장할 수 있으며, 이를 통해 행렬과 같은 구조를 표현할 수 있다.

 

 

장점

 

1. 빠른 접근 속도 및 지역성 : 요소에 인덱스를 사용해 빠르게 접근이 가능하며 O(1)의 시간 복잡도를 가진다.

그와 더불어 캐시 지역성(Cache Locality)을 가지고 있으며 하나의 원소에 접근할 때

그 근방에 있는 원소도 함께 캐시(Cache)로 가져온다

 

2. 메모리의 효율성 : 메모리 내에서 연속적으로 할당되므로 메모리 사용이 효율적이며

다른 자료구조 대비 상대적으로 적은 오버헤드가 있다.

 

3. 간단한 구조 : 간단하고 직관적인 구조로 되어 있으므로, 다른 자료구조와 함께 사용하기 쉬우며

많은 프로그래밍 언어에서 기본적으로 배열을 지원한다.

 

 

단점

 

1. 고정된 크기 : 생성 시 크기가 고정되는 탓에 일반적으로는 크기 변경이 어렵다.

크기를 동적으로 조절하려면 새 배열을 생성하고 기존 데이터를 복사하는 작업이 요구된다.

 

2. 요소 삽입 및 삭제의 어려움 : 중간에 요소를 삽입하거나 삭제하기가 어렵다.

삭제된 요소 이후의 모든 요소를 이동시켜야 하며 이에 따라 성능 저하와 메모리 사용량이 늘어날 수 있다.

이 작업의 시간 복잡도는 O(n)이다.

 

3. 메모리 낭비 가능성 : 미리 정해진 크기를 가지므로 필요 이상의 크기를 가진 배열을 할당하면 스택 메모리가 낭비될 수 있다.

(스택 메모리는 보통 1MB가 할당 되어있다.)

 

4. 비효율적인 동적 크기 조절 : 크기를 동적으로 조절하려면 새 배열을 할당 후 데이터를 복사해야 하는 특성이 있다.

이 작업은 비용이 많이 들며 큰 배열을 사용한다면 시간이 오래 걸릴 수 있다. 앞에 설명한 단점 2와 연결되는 단점이다.

 

정리하자면 배열은 간단하면서도 빠른 접근이 필요한 상황에서 유용하지만, 크기가 동적으로 변하는 데이터나

중간에 요소를 삽입 / 삭제해야 하는 경우에는 좋지 않은 선택이 될 수 있다.