Array
Array는 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기 만큼 저장하는 자료구조
Array의 특징
- 고정된 저장 공간
- 순차적인 데이터 저장
Array의 장점은 lookup과 append가 빠르다. 조회를 자주 해야되는 작업에서는 Array자료구조를 많이 사용
Array의 단점은 fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있다.
Q. 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 되면 어떻게 할것인가?
A. 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제하면 된다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 한다.
다른 방법으로 size가 예측하기 쉽지 않다면, Array대신 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용하면 된다.
Dynamic Array
Array의 fixed-size의 한계를 극복하기 위한 자료구조
저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장
- Doubling
resize의 대표적인 방법
데이터를 추가(append O(1))하다가 메모리를 초과하게 되면 기존 배열의 size보다 2배 큰 배열을 선언하고 데이터를 일일이 옮기는(O(n)) 방법
append의 시간복잡도
대부분 인덱스에 추가하는 (O(1))이고 resize 할때 O(n)이 발생하므로 전체적으로 --> O(1)
Linked List
Node라는 구조체로 이루어져있다. Node는 데이터 값과 다음 Node의 address를 저장
Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked list를 구성하는 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조
데이터 삽입/ 삭제
물리적 옮길 필요없이 next address의 주소값 변경만 하면 되기 때문에 O(1)의 시간복잡도를 가진다.
| Array | Linked List | |
|---|---|---|
| 메모리 구조 | 물리적 연속성 | 논리적 연속성 |
| 데이터 조회 | O(1) | O(n) |
| 삽입/삭제 | O(n) | O(1) |
| 메모리 할당 | 미리할당 -> 낭비 | 즉시할당 |
| 유리한 상황 | 1. 조회 작업이 잦을때 2. 데이터 갯수를 미리 알고 있을 때 3. 데이터 반복문을 통해 빠르게 순회할 때 4. 메모리를 적게 쓰는게 중요한 상황일 때. 미리 들어올 데이터 양을 알고 있다면 Array가 메모리를 더 효율적으로 사용한다. | 1. 삽입/ 삭제가 잦을 때 2. 얼마만큼의 데이터가 들어올지 예측 할 수 없을 때 3. 조회 작업을 별로 하지 않을 때 |
| 메모리 allocation | Compile - stack 영역 | Runtime - heap영역 |
