🤓오늘의 공부 주제: Array🤓
Q. Dynamic Array는 어떤 자료구조인가?
A. array의 경우 size가 고정되었기 때문에 선언시에 설정한 사이즈보다 많은 갯수의 데이터가 추가되면 저장이 불가. 이에 반해 dynamic array는 저장공간이 가득차게 되면 resize를 해서 유동적으로 size를 조절하여 데이터를 저장하는 자료구조.
🔑key point!
array의 특징 중 fixed-size의 한계점을 보완하고자 고안된 자료구조인 dynamic array에 대해서 중요하게 볼 부분은
1) resize방식
2) 데이터 추가 시 시간 복잡도
dynamic array는 사이즈를 자동적으로 리사이징하는 array. 기존의 고정된 사이즈를 가진 static array의 한계점을 보완하고자 고안. dynamic array는 데이터를 계속 추가하다가 기존에 할당된 메모리를 초과하게 되면 사이즈를 늘린 배열을 선언하고 그곳으로 데이터를 옮김으로써 늘어난 크기의 사이즈를 가진 배열이 된다. 이를 리사이즈라고 함. 따라서 미리 사이즈를 고민할 필요가 없음. 리사이징 방식은 여러가지가 있는데 그중 대표적인게 2배 사이즈를 할당하는 doubling.
doubling의 시간 복잡도는 데이터를 추가할때는 O(1)인데 메모리 초과 시 기존 배열에서 데이터를 일일이 옮겨야 하므로 O(n).
💡요약💡
장점: 데이터 접근과 할당이 O(1)으로 빠름
단점: 리사이즈할때 현저하게 낮은 O(n) 퍼포먼스 발생. 리사이즈에 시간이 많이 걸리니까 필요 이상의 메모리 공간을 할당 받아서 낭비되는 공간이 발생함.
Q. dynamic array와 linked list를 비교하여 장단점 설명.
A.dynamic array의 장점은 데이터 접근과 할당이 O(1)으로 빠름. random access를 통해서 배열 첫 데이터의 주소값 + offset으로 산술하기 때문. 반면 단점은 맨 끝이 아닌 곳에 데이터 삽입, 삭제 시에는 O(n)으로 느린편. 뒤에 있는 데이터들을 모두 한칸씩 옮겨야하기 때문. 또한 리사이즈할때 현저하게 낮은 O(n) 퍼포먼스 발생. 리사이즈에 시간이 많이 걸리니까 필요 이상의 메모리 공간을 할당 받아서 낭비되는 공간이 발생함.
출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]
