배열은 가장 기본적인 자료구조로, 메모리에 연속적으로 저장되는 동일한 타입의 데이터 집합을 의미한다.

구현은 다음과 같다.

int arr[5]; // 크기가 5인 정수형 배열
arr[0] = 1; //첫 번쨰 요소에 값 1 할당

배열의 크기는 고정되어 있고, 선언될 떄 크기가 정해진다.

배열에서의 주요 연산들에 대한 시간 복잡도는 다음과 같다.

• 접근 (Access): O(1)
  • 특정 인덱스에 있는 요소에 접근하는 데 필요한 시간은 상수 시간이다.
• 탐색 (Search): O(n)
  • 배열에서 특정 값을 찾기 위해서는 일반적으로 배열의 모든 요소를 순회해야 하므로 선형 시간 복잡도를 가진다. (이진 탐색을 사용하기 위해서는 배열이 정렬되어 있어야 하며, 이 경우 O(log n)의 시간 복잡도를 가진다.)
• 삽입 (Insertion): O(n)
  • 배열 중간에 새로운 요소를 삽입하려면, 그 요소 뒤의 모든 요소를 한 칸씩 뒤로 이동해야 합니다. 최악의 경우, 배열의 첫 번째 위치에 삽입하려면 모든 요소를 이동해야 하므로 시간 복잡도는 O(n)이다.
• 삭제 (Deletion): O(n)
  • 배열 중간에서 요소를 삭제하는 경우, 뒤에 있는 모든 요소를 앞으로 이동해야 하므로 삽입과 마찬가지로 시간 복잡도는 O(n)이다.

배열은, 빠른 접근, 정적 크기, 낮은 오버헤드일 경우 효율적이다.

반면 ,데이터의 크기가 자주 변화하거나, 빈번한 삽입, 삭제 그리고 고정된 메모리로 인해 할당한 메모리를 모두 사용하지 않으면 메모리가 낭비된다.

위 경우, 동적 배열을 사용하는 것이 유용하다.

동적 배열은 크기가 가변적인 배열로, 프로그램 실행 중에 크기를 동적으로 조정할 수 있는 자료구조이다.

동적 배열은 다음 방식을 통해 동작한다.

1. 초기할당
2. 자동확장
3. 메모리 관리