🌐 
Array(배열)과 LinkedList(연결 리스트)는 서로 다른 특성을 가진 대표적인 자료구조입니다.
면접에서 자주 비교되는 주제이므로, 각 특성과 장단점을 명확히 이해하는 것이 중요합니다.
✅ Array란?
- 연속된 메모리 공간에 데이터를 저장
- 인덱스를 통해 빠른 접근(O(1)) 가능
- 삽입/삭제 시 많은 요소 이동이 필요 → 비효율적(O(n))
- 캐시 친화적(메모리 연속 배치 → CPU 캐시 효율 ↑)
예: int arr[5] = {1, 2, 3, 4, 5};
✅ LinkedList란?
- 각 노드가 데이터와 다음 노드의 포인터를 가짐
- 삽입/삭제는 포인터만 변경하면 되므로 빠름(O(1))
- 임의 접근(Random Access)은 불가능 → 처음부터 탐색 필요 (O(n))
- 메모리 연속성이 없어 캐시 효율이 떨어짐
종류:
- 단일 연결 리스트 (Singly Linked List)
- 이중 연결 리스트 (Doubly Linked List)
- 원형 연결 리스트 (Circular Linked List)
🔍 Array vs LinkedList 비교
| 항목 | Array | LinkedList |
|---|---|---|
| 메모리 구조 | 연속된 메모리 | 비연속, 노드+포인터 |
| 접근 속도 | O(1) (인덱스로 직접 접근) | O(n) (순차 탐색 필요) |
| 삽입/삭제 | O(n) (요소 이동 필요) | O(1) (포인터 변경) |
| 메모리 효율 | 효율적 | 포인터 저장으로 오버헤드 발생 |
| 캐시 친화도 | 높음 | 낮음 |
| 활용 예 | 검색/읽기 위주 | 삽입/삭제 빈번 |
🧠 추가 CS 지식
🔹 Array의 장점
- 빠른 인덱스 접근 (Random Access)
- 캐시 지역성(Locality) 효과 → 성능 향상
🔹 LinkedList의 장점
- 크기가 가변적 → 삽입/삭제 용이
- 중간에 데이터 추가/삭제가 많은 경우 유리
🔹 활용
- Array는 읽기 중심(검색, 인덱스 접근) 작업에서 효율적
- LinkedList는 삽입/삭제가 빈번한 큐(Queue), 스택(Stack), 그래프의 인접 리스트 표현 등에 자주 사용됨
🔹 변형 자료구조
- 동적 배열 (Dynamic Array, 예: C++ vector, Java ArrayList): 배열 기반 + 크기 자동 확장
- 해시 테이블 (Hash Table): 내부적으로 배열과 연결 리스트를 결합해 충돌 해결에 활용
🔹 빅오(Big-O) 복습
- Array: 접근 O(1), 삽입/삭제 O(n)
- LinkedList: 접근 O(n), 삽입/삭제 O(1)
🔹 언어별 활용
- Java:
ArrayList(배열 기반),LinkedList(연결 리스트 기반) - Python:
list(배열 기반),collections.deque(양방향 연결 리스트 유사 구조)
🎯 면접 대비 질문 예시
💬 Array와 LinkedList의 차이를 설명해주세요.
💬 삽입/삭제가 많은 경우 어떤 자료구조가 유리한가요?
💬 캐시 친화성(Cache Locality)은 왜 배열이 더 좋은가요?
💬 ArrayList와 LinkedList의 차이를 설명해보세요.
💬 해시 테이블에서 배열과 연결 리스트는 각각 어떤 역할을 하나요?
💬 Python의 list는 배열일까요, 연결 리스트일까요?
Hello