배열이란?
배열은 연관된 데이터를 다루는 자료구조이다.
배열은 고정된 메모리 공간을 할당받고, 선언 시 공간의 크기를 지정해주어야 한다.
배열 내부의 데이터는 메모리에 물리적으로 연속적으로 배치된다는 특징이 있다.
또한 메모리 상 주소를 가르킬 때 상대 주소인 인덱스를 활용해 쉽게 접근이 가능하다.
행위 별 시간 복잡도
| 행위 | 시간복잡도 |
|---|---|
| access | O(1) |
| append | O(1) |
| delete last | O(1) |
| insert | O(n) |
| delete | O(n) |
access
access는 배열에서 인덱스를 활용해서 데이터에 접근하는 행위를 뜻한다. 이때의 시간 복잡도는 위의 표를 보면 알 수 있지만 O(1)의 좋은 성능을 보인다. 이는 배열은 메모리 상 물리적으로 연속되어있기 때문에 인덱스 0이 배열의 시작 주소를 지니고 연산을 통해 다른 인덱스의 메모리 주소를 빠르게 계산 가능하기 때문이다.
ex) 인덱스 0이 메모리 주소가 10이고, 데이터 1개당 메모리를 2씩 차지한다고 할 때, 인덱스 2는 10 + (2 x 2) = 14를 연산하여 호출한다.
append
append는 배열의 가장 끝 위치에 데이터를 추가하는 행위이다. 별 다른 작업이 필요하지 않아서 O(1)의 성능을 보인다.
delete last
delete last는 배열의 가장 끝 위치에 데이터를 삭제하는 행위이다. append와 마찬가지로 별 다른 작업이 필요하지 않아서 O(1)의 성능을 보인다.
insert
Insert는 배열의 중간에 값을 삽입하는 행위이다. 중간에 데이터를 삽입 할 경우, 기존에 있는 데이터들의 인덱스를 순회하면서 변경해주어야 하는 Shift가 발생하기 때문에 O(n)의 성능을 보인다.
아래 그림과 같이 인덱스 1에 4를 삽입하게 되면, 기존에 존재하는 인덱스 1, 2의 값을 오른쪽으로 이동시켜 줘야 하기 때문이다.
delete
delete도 insert와 마찬가지로 배열의 중간 값을 삭제할 경우 shift가 발생해 O(n)의 성능을 보인다.
장단점
장점
조회의 경우 빠른 성능을 보이기 때문에, 조회 작업이 많다면 Array 자료구조를 사용하는 편이 좋다.
단점
고정된 크기로 인해 관리할 데이터의 수가 불확실 하다면, 사용하기 어려운 부분이 있다. 그리고 미리 메모리 공간을 할당받기 때문에, 사이즈만큼 사용되지 않는 경우엔 메모리 낭비가 발생할 수 있다.
또한 값이 자주 삽입/삭제가 되는 경우 shift가 발생하기 때문에, 삽입/삭제 작업이 많다면 다른 자료구조를 사용하는 편이 좋을 수 있다.
