[자료구조] Array(배열) , dynamic array

 Array

Array 란?

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다.

메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장합니다.

배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열의 위치를 가르키는 숫자를 index라고 합니다.

 

Array 특징

고정된 저장 공간

순차적인 데이터 저장

배열에 각 요소에 접근하는 시간은 O(1)로 모두 동일 

    - 기본위치 + offset(요소크기 * index)연산으로 모든 요소에 접근 가능

연속된 메모리에 단일 블록화하여 데이터를 저장

    - 낭비되는 공간이 거의 없음

    - 큰 배열일 경우, 필요 메모리 할당이 불가능할 수 있음

실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되고, indexing, slicing 가능

 

Array 장점

index를 이용한 접근으로 lookup과 append가 빠르다. 따라서 조회가 자주 일어나는 작업에서 array 자료구조르르 많이 사용한다.

 

 

Array 단점

fixed-size의 특성상 선언시에 array의 크기를 미리 정해야 하므로 메모리의 낭비 및 overhead가 발생할 수 있다.

중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 모든 요소를 이동시켜야한다. 그렇기 때문에 삽입 및 삭제에 비용이 많이 들게 된다.

 

Array 를 사용하는 경우

순차적인 데이터를 저장하며 값보다 순서가 중요할 경우

다차원 데이터를 다루는 경우

특정 요소를 빠르게 읽어야 할 경우

데이터 사이즈가 자주 바뀌지 않으며 요소의 삽입, 삭제가 자주 발생하지 않을 경우

 

배열의 시간 복잡도(Time complexity)

Operation	average case	worst case
read	O(1)	O(1)
insert	O(n)	O(n)
delete	O(n)	O(n)
search	O(n)	O(n)

---

Dynamic array

Dynamic array란?

size를 자동으로 resizing 하는 array이다.

기존에 고정된 size를 가진 static array의 한계점을 보완하고자 고안되었다.

dynamic array는 data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면,

size를 늘린 배열을 선언하고 그 곳으로 모든 데이터를 옮김으로서 늘어난 크기의 size를 가진 배열이 된다.(resize)

따라서 dynamic array는 size를 미리 고민할 필요가 없다는 장점이 있다.

 

resize의 대표적인 방법으로 doubling이 있다.

데이터를 추가(append O(1))하다가 메모리를 초과하게 되면 기존 배열의 size보다 두배 큰 배열을 선언하고,
데이터를 일일이 옮기는 (n개의 데이터를 일일이 옮겨야 하므로 O(n)) 것을 말한다.

 

dynamic array의 단점

• resize를 해야할 때, 예상치 못하게 현저히 낮은 퍼포먼스가 발생한다.
• resize에 시간이 많이걸리므로 필요한 것 이상의 memory 공간을 할당받기때문에,
  사용되지 못하고 낭비되는 메모리 공간이 발생한다.