모든 자료구조는 배열(Array)로 통한다

배열은 거의 대부분의 프로그래밍 언어가 가지고 있고, 많은 자료구조의 기초가 되는 중요하고 기본적인 자료구조이다. 배열은 프로그래밍을 조금이라도 한 사람이라면 이미 익숙한 경우가 많겠지만, 자료구조의 관점에서 다시 한번 배열을 들여다보자.

 

---

배열의 정의

배열은 데이터와 인덱스가 대응되도록 한 자료구조이다. 배열은 크기가 정해져 있고, 배열의 인덱스는 일반적으로 0에서 시작한다.

 

배열은 사실상 가장 간단한 자료구조 중에 하나이다. 배열은 단순히 데이터를 정해진 개수만큼 순서대로 배치한 것이기 때문에 이보다 더 간단하게 데이터를 배치할 방법은 없다. 하지만, 그만큼 제한이 많은 데이터 구조 중에 하나이다. 우선, 크기가 정해져 있기 때문에 정해진 크기가 다 차면 더 이상 데이터를 추가할 수 없고, 또 중간에 데이터를 삽입하기 위해서는 배열을 처음부터 다시 만들어야 한다.

---

배열이 씌이는 곳

배열은 사실상 가장 기본적인 자료구조이기 때문에, 다른 모든 자료구조를 만들 때 쓰인다. 또, 정해진 크기를 미리 알 수 있는 모든 종류에 데이터에 씐다.

---

배열의 시간 복잡도

배열은 제한이 많은 자료구조이기 때문에 시간 복잡도가 가장 중요한 6개의 연산인 접근, 검색, 앞, 뒤, 중간에 삽입, 삭제 중에 무려 3개가 불가능하다.

 

연산 종류	시간 복잡도
접근	O(1)
검색	O(n)
앞에 삽입	불가능(새로 배열을 만들어서는 가능)
중간에 삽입	불가능(새로 배열을 만들어서는 가능)
뒤에 삽입	불가능(새로 배열을 만들어서는 가능)
삭제	불가능

 

다른 프로그래밍 언어를 사용해 본 적이 있다면, 1과 3으로 이루어진 배열에 2를 삽입하기 위해서 새로 배열을 만들어했을지도 모른다. 자바를 예로 들면 아래와 같은 코드이다.

 

int[] ex1 = {1, 3};
int[] ex2 = {1, 2, 3};
ex1 = ex2;

 

하지만, 이런 식의 삽입은, 기존에 있던 배열에 삽입하는 것이 아니라, 단순히 새로운 배열을 만들어서 원래 있던 배열은 버리고, 새로운 배열을 기존의 변수에 지정하는 것이기 때문에 삽입을 한 게 아니다. 같은 이유로 배열은 삭제도 불가능하다.

---

요약

1. 배열은 데이터를 순서대로 배치하고 인덱스로 부를 수 있는 크기가 정해진 자료구조이다.

2. 배열은 모든 자료구조의 기본이 된다.

3. 하지만 배열은 삽입이나 삭제가 안 되는 등의 제한이 많다.

---