배열 자료구조의 가장 기본형인 Array(static array)를 한 마디로 정의하자면 아래와 같이 할 수 있다.
배열(Array)는 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다.
데이터 묶음를 하나의 변수에 담아 관리하는 선형 자료구조를 배열이라고 한다.
모든 프로그래밍 언어는 Array, ArrayList, List, Slice 등 다양한 형태의 선형 자료구조를 built-in으로 지원하는데, 이러한 선형 자료구조들은 배열을 기반으로 만들어졌으며 상황에 따라 서로다른 성능을 보여준다.
Array의 특징
1. 고정된 저장 공간(fixed-size)
배열은 선언될 때 데이터의 Type과 길이 정보를 바탕으로 RAM의 특정 공간에 고정된다.
만약 정수 1~4까지의 숫자를 배열에 담는다고 하면 실제 메모리에는 아래와 같이 저장되게 된다.
| Address | Index | Value |
|---|---|---|
| ... | ... | |
| 0xA0 ~ 0xA3 | 0 | 1 |
| 0xA4 ~ 0xA7 | 1 | 2 |
| 0xA8 ~ 0xAB | 2 | 3 |
| 0xAC ~ 0xAF | 3 | 4 |
| ... | ... |
정수형은 4byte 이므로 배열은 총 16byte를 할당받아 데이터를 저장한다. 배열이 할당받은 주소는 0xA0 ~ 0xAF까지 이므로 이곳에 추가적인 데이터를 넣을 수 없다.
경우에 따라서 배열의 각 메모리 공간에는 Value가 아닌 'Value의 주소' 가 들어갈 수도 있다. 예를 들면, 문자 데이터들은 문자열의 길이에 따라 메모리 사이즈가 달라지기 때문이다.
2. 순차적인 데이터 저장(order)
배열의 데이터들이 연속된 메모리 주소를 할당받기 때문에 인덱스로 빠르게 접근할 수 있다. 만약 위 표에서 1번 인덱스의 값을 가져오려면 배열의 시작 주소인 0xA0에서 (4byte * 1)을 한 0xA4 ~ 0xA7의 값을 가져오면 된다.
Array의 시간복잡도
1. 조회(lookup)
메모리상에서 연속적인 데이터를 임의 접근(Random Access)하기 때문에 O(1) 의 시간이 소요된다.
2. 추가(append)
배열이 비어있는 상태에서 마지막 인덱스에 값을 추가하는 경우 시간복잡도는 O(1)이다. 단, Array는 선언시에 길이가 고정되어 때문에 append 연산은 최초 할당시에만 적용된다.
3. 삽입(insertion)
특정 위치에 데이터를 삽입하려면 길이가 긴 새로운 배열을 생성하고, 추가하려는 인덱스 이전 데이터를 새로운 배열에 복사하고 새로운 데이터를 추가한 후 남은 데이터를 순차적으로 복사하한다. 따라서 시간복잡도는 O(N)이다.
4. 삭제(deletion)
특정 위치의 데이터를 삭제하려면 길이가 짧은 새로운 배열을 생성하고, 삭제하려고 하는 데이터를 제외한 모든 데이터를 순차적으로 복사한다. 따라서 시간복잡도는 O(N)이다.
5. 검색(search)
배열의 첫번째 인덱스부터 값을 비교하며 찾아야 하므로 시간복잡도는 O(N)이다.
요약
| Operation | Worst Case |
|---|---|
| 조회(lookup) | O(1) |
| 추가(append) | O(1) |
| 삽입(insertion) | O(N) |
| 삭제(deletion) | O(N) |
| 검색(search) | O(N) |
장점
- 빠른 조회: 배열의 길이와 상관 없이 O(1)로 접근이 가능하다.
- 빠른 데이터 추가: 배열의 비어있는 공간에 O(1)로 추가가 가능하다.
단점
- 고정된 크기: 최초 선언시 정확한 길이를 알아야 하며, 선언 후 길이가 변경된다면 새로운 배열을 만들어 복사해야 한다.
- 삽입, 삭제시 낮은 성능: 해당 연산시 새로운 배열을 생성후 메모리 복제로 인해 O(N)으로 동작한다.
Reference
