자료구조 - 배열(Array)

1. 배열이란?

배열(Array)은 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조로 연속된 메모리 공간에 순차적으로 저장한다. 배열의 크기는 고정되어 있고, 선언할 때 크기를 정하고 후에 변경할 수는 없다.

 

2. 시간 복잡도

1) 삽입 / 삭제

- 배열의 맨 앞에 삽입 / 삭제하는 경우 : O(n)

- 배열의 맨 뒤에 삽입 / 삭제하는 경우 : O(1)

- 배열의 중간에 삽입 / 삭제하는 경우 : O(n)

 

2) 탐색

- O(n)

 

3. 장단점

1) 장점

- 인덱스를 가지고 있어 바로 접근 가능하다. (자료의 크기가 클수록 매우 유리)

- 연속된 메모리 공간에 존재하기 때문에 관리가 편리하다.

- 구조가 간단하여 프로그램 작성이 쉽다.

 

2) 단점

- 데이터 삽입 / 삭제가 어렵다. (삽입이나 삭제 시 해당 원소 이후의 모든 원소들을 한 칸 씩 밀거나 당겨야함)

- 배열의 크기를 바꿀 수 없다.

- 연속된 메모리라서 공간 낭비가 발생한다.

- 연속적인 메모리 할당이 필요하다.

 

4. 응용

- 데이터 개수가 확실하고 삭제/삽입이 적으며 검색을 해야할 경우