Array
연관된 데이터를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조
특징
- 고정된 저장 공간 (fixed-size)
- 순차적인 데이터 저장(order)
- lookup과 append가 빠르기 때문에 조회를 자주 해야되는 작업에 많이 쓰임
- 크기를 미리 정하기 때문에 메모리 낭비나 추가적인 overhead가 발생 할 수 있음
시간복잡도
| Array | |
|---|---|
| access | O(1) |
| append | O(1) |
| 마지막 원소delete | O(1) |
| insertion | O(n) |
| deletion | O(n) |
| search | O(n) |
Dynamic Array
저장공간이 가득 차게 되면 resize하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조
resize
- data를 계속 추가하다가 기존에 할당된 Memory를 초과하게 되면 사이즈가 더 큰 배열을 선언하여 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 됨.
doubling
- 기존 Array size의 2배 size를 할당하는 방법
- append의 시간복잡도 amortized O(1)
- 가끔 발생하는 O(n)의 resize하는 시간을, 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로 써 전체적으로 O(1)의 시간 소요
