1. Array의 정의
- 개념: 연관된 데이터를 메모리상에 연속적이고 순차적으로 저장하며, 미리 할당된 크기를 사용하는 자료구조.
- 핵심 원리: 데이터가 메모리의 연속된 공간에 위치하여 인덱스(Index)를 통한 직접 접근이 가능.
2. Array의 주요 특징
- 고정된 크기(Fixed-size): 선언 시 데이터 저장 공간의 크기를 미리 결정해야 하는 특성.
- 순차적 데이터 저장(Order): 데이터가 입력된 순서대로 메모리에 정렬되어 저장되는 방식.
- 메모리 효율성: 데이터 외에 추가적인 메타데이터(포인터 등) 저장이 적어 메모리 사용이 효율적임.
3. 장점과 단점
| 구분 | 주요 내용 |
|---|---|
| 장점 | 인덱스를 이용한 빠른 조회(Lookup) 및 마지막 원소 추가(Append) 속도. |
| 단점 | 크기 변경이 불가능하여 메모리 낭비 혹은 추가적인 오버헤드 발생 가능성. |
4. 주요 연산의 시간 복잡도
데이터 접근 속도는 매우 빠르나, 중간 삽입/삭제 시 데이터 이동이 필요하여 효율이 저하됨.
| 연산 (Operation) | 시간 복잡도 | 비고 |
|---|---|---|
| Access | O(1) | 인덱스를 통해 즉시 접근 가능. |
| Append | O(1) | 마지막 위치에 데이터 추가. |
| Search | O(n) | 특정 값을 찾기 위해 전체 순회 필요. |
| Insertion | O(n) | 삽입 후 데이터 밀어내기 작업 발생. |
| Deletion | O(n) | 삭제 후 빈 공간을 채우기 위한 데이터 이동 발생. |
추가 정리
Q. 배열의 크기가 부족할 때 해결 방법은?
- Dynamic Array(동적 배열): 기존보다 더 큰 새로운 배열을 선언한 뒤 기존 데이터를 복사하여 옮기는 방식. 이후 기존 배열은 메모리에서 해제함.
- Linked List 활용: 데이터 추가 시마다 메모리 공간을 유연하게 할당받는 연결 리스트 구조로 변경 고려.
핵심 정리
Array vs Linked List의 결정적 차이
- 저장 방식: Array는 연속적(Contiguous) 저장, Linked List는 불연속적 저장 방식.
- 성능 차이: 조회 성능은 Array가 우수하나, 중간 데이터의 삽입 및 삭제 성능은 Linked List가 더 효율적임.
- Array 질문 시 높은 확률로 Linked List와 비교 질문이 나오므로, 메모리 저장 방식에 따른 시간 복잡도(O(1) vs O(n)) 차이를 명확히 답변하는 것이 핵심.