1. Linked List의 정의 및 논리적 구조
- 정의: 데이터 값과 다음 노드의 주소(Address)를 저장하는 Node라는 구조체로 이루어진 자료구조.
- 논리적 연속성: 각 노드가 다음 노드의 주소를 가리킴으로써, 물리적으로는 떨어져 있어도 논리적으로는 이어진 상태를 유지.
- 메모리 할당: 데이터가 추가되는 시점에 메모리를 할당하는 동적 할당 방식 사용.
2. 물리적 저장 방식의 특징
Array와의 결정적인 차이점은 메모리 저장의 비연속성
- 물리적 불연속성: 메모리상의 빈 공간 어디에나 노드를 배치할 수 있어 메모리 사용이 자유로움.
- 추가 메모리 소모: 데이터 외에 다음 노드의 주소 정보를 별도로 저장해야 하므로 데이터 하나당 차지하는 메모리 용량이 Array보다 큼.
- Array와의 비교: Array는 연속성을 위해 순차적으로 저장하는 반면, Linked List는 주소 참조를 통해 연결성을 확보.
3. 주요 연산의 시간 복잡도
물리적 이동 없이 포인터(주소)값만 변경하면 되므로 삽입과 삭제에 최적화.
| 연산 (Operation) | 시간 복잡도 | 설명 |
|---|---|---|
| Access | O(n) | 특정 인덱스 접근 시 Head부터 순차적 탐색 필요. |
| Search | O(n) | 특정 값을 찾기 위해 전체 리스트를 순회해야 함. |
| Insertion | O(1) | 이전 노드의 주소값만 변경하여 즉시 삽입 가능. |
| Deletion | O(1) | 삭제 대상 전후 노드의 연결 정보를 변경하여 즉시 삭제 가능. |
4. 추가 정리
Q. Linked List의 가장 큰 장점은 무엇인가?
- 삽입/삭제 효율성: 데이터 시프트(Shift) 과정이 필요한 Array와 달리 O(1)의 비용으로 작업 수행 가능.
- 메모리 효율성: 고정된 크기 없이 필요할 때마다 메모리를 할당받아 낭비를 최소화함.
Q. Linked List의 실제 활용 사례는?
- 다른 자료구조 구현: 트리(Tree), 그래프(Graph) 등 복잡한 비선형 자료구조를 구현하는 기본 틀로 사용됨.
- 동적 데이터 관리: 데이터의 개수를 미리 예측하기 어렵고 삽입/삭제가 빈번한 시스템 환경.
정리
Array vs Linked List 면접 포인트
- 메모리 저장: Array는 연속적 저장, Linked List는 불연속적 저장 방식.
- 연산 성능: 조회 위주 작업은 Array(O(1)), 삽입/삭제 위주 작업은 Linked List(O(1))가 유리함.
- 데이터 참조: Linked List는 논리적 연결을 위해 주소(Next Address)를 추가 저장해야 함을 명시.
출처
- 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/