1. 개요 및 저장 구조
데이터의 저장 방식과 메모리상의 배치 형태에 따른 근본적 차이.
- Array(배열): 메모리상에 연속적으로 데이터를 저장하는 구조.
- Linked List(연결 리스트): 물리적 메모리상에서는 불연속적이나, 각 원소가 다음 원소의 주소값을 저장하여 논리적 연속성을 유지하는 구조.
2. 연산별 시간 복잡도(Time Complexity) 비교
메모리 구조의 차이로 인해 각 연산의 효율성이 상이하게 나타남.
| 연산(Operation) | Array | Linked List | 설명 |
|---|---|---|---|
| 조회 (Lookup) | O(1) | O(n) | Array는 임의 접근(Random Access)이 가능함. |
| 삽입/삭제 (중간) | O(n) | O(1) | Linked List는 포인터 변경만으로 작업 수행 가능함. |
| 삽입/삭제 (끝) | O(1) | O(1) | 두 구조 모두 마지막 원소 처리는 효율적임. |
- 참고: Linked List의 삽입/삭제 시 해당 인덱스까지 도달하는 탐색 비용(O(n))이 추가로 발생할 수 있음.
3. 메모리 할당 및 관리 체계
시스템 자원 활용 방식의 차이.
- 할당 시점 및 영역:
- Array: 컴파일 단계에서 정적 할당(Static Allocation) 수행. 주로 Stack 영역에 할당됨.
- Linked List: 런타임 단계에서 노드 추가 시 동적 할당(Dynamic Allocation) 수행. Heap 영역에 할당됨.
- 자원 효율성:
- Array: 고정된 크기로 인해 실제 데이터가 없어도 메모리를 차지하여 낭비 발생 가능함.
- Linked List: 필요한 만큼만 할당받아 사용하므로 메모리 낭비가 적음.
4. 추가 정리
Q. 어느 상황에 Linked List를 쓰는 것이 유리한가?
- 삽입과 삭제 작업이 빈번하게 일어나는 경우.
- 저장할 데이터의 총량을 사전에 예측하기 어려운 경우.
- 조회 작업의 비중이 상대적으로 낮은 경우.
Q. 어느 상황에 Array를 쓰는 것이 유리한가?
- 데이터 조회(Lookup) 작업을 자주 수행하는 경우.
- 데이터의 개수가 사전에 고정되어 있거나 명확히 알고 있는 경우.
- 메모리 사용량을 최소화해야 하는 경우(추가 포인터 공간 불필요).
정리
- Array: 인덱스를 통한 빠른 데이터 접근(O(1))이 최대 장점이나, 중간 삽입/삭제 시 데이터 이동 비용(O(n))이 발생함.
- Linked List: 동적 크기 조절과 삽입/삭제의 논리적 간결함이 강점이나, 특정 위치 탐색 시 순차 접근(O(n))으로 인해 느림.
- 결론: 데이터의 성격(정적/동적)과 주요 연산(조회/수정)의 빈도에 따라 적절한 자료구조를 선택하는 것이 필수적임.
출처
- Pat Morin, Open Data Structures - Array-Based Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html
- Pat Morin, Open Data Structures - Linked Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/3_Linked_Lists.html
- MIT OpenCourseWare 6.006, Data Structures and Dynamic Arrays https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-2-data-structures-and-dynamic-arrays/