배열

동일한 타입의 데이터를 메모리에 연속적으로 저장하는 가장 기본적인 자료구조입니다.

구조

index:  0    1    2    3    4
     [10] [20] [30] [40] [50]
      ↑ 시작 주소 기준으로 연속된 메모리 공간

핵심 연산

int[] arr = new int[5];      // 선언 - 크기 고정
arr[0] = 10;                 // 접근/수정 - O(1)

// 탐색 - O(n)
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
}

// 삽입 (중간) - O(n), 뒤 요소를 모두 밀어야 함
// [10, 20, 40, 50] → 30 삽입 → [10, 20, 30, 40, 50]

시간복잡도

Java에서의 배열

// 정적 배열 - 크기 고정
int[] arr = new int[5];
int[] arr2 = {1, 2, 3, 4, 5};

// 동적 배열 - 크기 자동 확장 (내부적으로 배열 사용)
ArrayList<Integer> list = new ArrayList<>();
list.add(1);   // O(1) 평균, 확장 시 O(n)
list.get(0);   // O(1)
list.remove(0); // O(n)

ArrayList는 공간이 부족하면 내부 배열을 1.5배 크기로 복사해 확장합니다.

배열 vs ArrayList