Array
배열 (Array)
연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 가장 기본적인 자료구조
구조
- 메모리 상 연속적으로 할당
- 인덱스를 통해 임의 위치에 직접 접근 가능
- 크기가 선언 시 고정 (정적 배열 기준)
시간 복잡도
| 연산 | 복잡도 | 이유 |
|---|---|---|
| 조회 | O(1) | 인덱스로 직접 주소 계산 |
| 삽입 | O(n) | 삽입 위치 이후 요소를 모두 이동 |
| 삭제 | O(n) | 삭제 위치 이후 요소를 모두 이동 |
배열 vs 연결 리스트
| 비교 | 배열 | 연결 리스트 |
|---|---|---|
| 메모리 | 연속 할당, 캐시 효율 높음 | 비연속, 포인터 추가 메모리 |
| 조회 | O(1) 인덱스 직접 접근 | O(n) 순차 탐색 |
| 삽입/삭제 | O(n) 요소 이동 필요 | O(1) 포인터만 변경 |
| 크기 | 고정 (일반적) | 동적 확장 가능 |
면접 포인트
- 배열을 선택할 때: 조회가 잦고, 크기가 고정적일 때 (랜덤 접근 필요)
- 연결 리스트를 선택할 때: 삽입/삭제가 잦고, 크기가 동적으로 변할 때
- 캐시 지역성: 배열은 연속 메모리라 캐시 효율이 높아 실제 성능이 더 좋은 경우 多