배열(Array)

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다. 각 데이터 요소는 인덱스(index)를 통해 접근할 수 있다.

표준적인 배열의 특징

• 연속된 메모리 배치: 기준 주소부터 연속된 위치에 요소가 저장된다.
• 상수 시간 접근(O(1)): 인덱스를 통해 원하는 요소에 직접 접근 가능하다.
• 고정 크기: 선언 시 크기를 지정하며, 이후 크기를 변경할 수 없다.

메모리 구조

배열은 기준 주소에서 시작하여, 각 요소는 타입 크기만큼 떨어진 메모리에 저장된다.

int arr[5] = {10, 20, 30, 40, 50};

arr[1] == *(arr + 1) // true

한계

• 표준적인 배열은 선언 이후 크기 변경이 불가능하다.
• 앞(front)에서 요소가 삽입/삭제될 경우, 뒤의 요소들을 당겨서 이동해야 하므로 O(n)의 시간복잡도가 발생한다.
• 범위를 초과하여 인덱스로 접근하는 것을 주의해야 한다.

구현 코드

int arr[5] = {10, 20, 30, 40, 50};

for (int i = 0; i < 5; i++) {
  std::cout << arr[i] << std::endl;
}

10
20
30
40
50