Array

Array의 특징

• 메모리 공간에 할당할 사이즈를 미리 정해 놓고 사용한다.
• 논리적 저장 순서와 물리적 저장 순서가 일치한다.
• 연속된 메모리 공간을 할당받기가 어려운 경우가 존재한다.
• 사용하지 않는 공간까지 전부 예약해두고 있어야 하므로 공간 낭비가 생긴다.
• index로 해당 원소(element)에 접근할 수 있다.
• 찾고자 하는 원소의 index 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다.
• Random Access가 가능하다

삽입 O(N)

삽입 시에는 해당 원소에 접근하여 삽입 하면된다.-O(1) 하지만 한가지 작업이 더 필요하다.

• 배열의 중간 위치에 추가하는 경우 배열의 중간 위치에 새로운 원소를 추가하고자 한다면 모든 원소들의 index를 1씩 shift해 주어야 하기 때문에 O(N)의 비용이 발생한다.
• 기존 배열의 크기를 넘어가는 경우 현재 배열의 크기의 2배가 할당되고 이전 배열이 새로 복사되어야 한다. (Array-Doubling) 때문에 이 경우도 O(N)의 비용이 발생한다.

삭제 O(N)

배열의 원소중 어느 원소를 삭제한다면, 배열의 연속적인 특징이 깨지게 된다. 즉, 빈공간이 생긴다. 따라서 삭제한 원소 뒤에있는 원소들을 shift해 주어야 하는 비용(cost)가 발생한다. 이 경우 시간 복잡도가 O(N)이 된다. 그렇기 때문에 Array 자료구조에서 삭제에 대한 time Complexity는 worst case의 경우 O(N)이 된다.

=> 삽입/삭제 시 배열의 빈 공간을 생성/제거하기 위해 나머지 원소들을 shift해야한다.O(N)

사용하지 말아야 하는 경우

• 계속 해서 데이터가 늘어나는 경우
• 최대 사이즈를 알수 없을 경우
• 중간에 데이터를 삽입하거나 삭제하는 경우

사용해야하는 경우

• 최대 사이즈를 알고 있는 경우