일반적으로 "배열"이라고 하면 정적 배열을 의미하고 "동적 배열"이라고 명확하게 이야기해야 "동적 배열"을 뜻하는 것이다.
정적 배열
Array
연관된 데이터를 메모리상에 연속적이며 순차적으로, 미리 할당된 크기만큼 저장하는 자료구조이다. 인덱스만 알고 있으면 조회를 빠르게 할 수 있어서 조회를 자주해야되는 작업에서 Array 자료구조를 많이 사용한다. Array를 선언할 때 크기를 미리 정해야되므로 메모리 낭비나 추가적인 overhead가 발생할 수 있는 것이 단점이다.
특징
- 고정된 저장 공간
- 순차적 데이터 저장
- 인덱스만 알고 있으면, 조회가 빠르다. (시간복잡도:
(O(1)) - 특정 조건을 충족하는 값을 찾는 "탐색"은 느리다. (시간복잡도:
(O(n))
동적 배열
Dynamic Array
저장 공간이 가득 차는 경우 자동적으로 사이즈를 늘려 데이터를 추가/저장 할 수 있는 유동적인 자료구조. Array의 한계를 극복하고자 고안되었다. 예상한 것보다 더 많은 수의 data를 저장하느라 선언된 Array의 size를 넘어선 경우 기존의 size 보다 더 큰 Array를 선언하여 데이터를 옮긴 뒤, 기존의 Array는 메모리에서 삭제한다.
특징
- 데이터의 접근과 할당이 빠르다.
- 필요한 것이상의 Memory 공간을 할당받으므로 낭비되는 메모리 공간이 발생한다.
append(추가) 는 동적 배열의 끝에 데이터를 넣을 때 쓰는 표현
insertion(삽입) 동적 배열의 아무 위치에나 데이터를 넣어줄 때 쓰는 표현
차이점
정적 배열
- 배열의 크기가 고정되어 변하지 않음. (요소 추가 불가능)
- 낭비되는 공간이 없음
동적 배열
- 배열의 크기는 변할 수 있음 (요소 추가 가능)
- 낭비되는 공간이 생길 수 있음
