배열

Goal

• 배열의 특징을 이해하고 장단점을 말할 수 있다
• 배열의 장단점을 이해하고 적절한 상황에 맞게 배열을 사용할 수 있다

---

배열(Array)

개념 : 동일한 자료형을 연속적인 메모리 공간에 저장한 자료구조

 

특징

• 인덱스(index)를 사용하여 임의 접근(Random Access)이 가능하다. 
• 각 항목이 동일한 자료형이므로 동일한 크기를 갖는다
• 저장 공간의 크기가 고정적이다.

장단점

[장점]

1. 원소 접근이 빠르다

원소 접근하는데 걸리는 시간이 상수 시간 O(1)이다.

(배열시작 주소 + index * 원소 크기)로 해당 원소에 접근이 가능 => Random Access 가능

 

2. 캐시 적중률(Cache hit rate)이 높다

연속된 메모리 공간에 저장되기 때문에 캐시 지역성(cache locality)이 증가하여 캐시 적중률이 증가한다.

 

3. 추가적인 메모리가 필요 없다 => overhead가 적음

다른 자료구조들은 해당 자료 구조를 구현하기 위해 추가적으로 소모되는 메모리가 존재하는데 배열 같은 경우 그런 추가적인 메모리 소모가 없다. 

 

 

[단점]

1. 원소 삽입 삭제에 불리하다

시작과 끝이 아닌 중간에 원소를 삽입하고 삭제하는 경우 추가적인 이동을 요구하기 때문에 삽입 삭제에 불리하다.

 

2. 메모리 낭비가 발생할 수 있다

크기가 고정되어 있기 때문에 사용되지 않는 부분이 많을 경우 저장 공간 낭비가 발생할 수 있다. => 내부 단편화

 

3. 배열을 크게 잡을 경우 메모리 할당에 제약이 생길 수 있다

연속되 메모리를 할당해야 하기 때문에 배열을 크게 선언할 경우 할당에 제약을 받을 수 있다.