연결 리스트 (Linked List)
데이터를 노드 단위로 묶어 포인터로 연결하는 자료구조
구조
- 데이터(값) + 포인터(다음 노드 주소) 로 구성
- 마지막 노드의 포인터 →
null
- 첫 번째 노드 →
head 포인터로 가리킴
- 배열과 달리 메모리 상 연속적으로 위치하지 않음
시간 복잡도
| 연산 |
복잡도 |
이유 |
| 조회 |
O(n) |
head부터 포인터를 순서대로 따라가야 함 |
| 삽입 |
O(1) |
포인터 정보만 변경 |
| 삭제 |
O(1) |
포인터 정보만 변경 |
단, 특정 위치에 삽입/삭제는 해당 위치를 찾는 O(n)이 선행됨
배열 vs 연결 리스트
| 비교 |
배열 |
연결 리스트 |
| 메모리 |
연속 할당, 효율적 |
비연속, 포인터 추가 메모리 |
| 조회 |
O(1) 인덱스 직접 접근 |
O(n) 순차 탐색 |
| 삽입/삭제 |
O(n) 요소 이동 필요 |
O(1) 포인터만 변경 |
유형
| 유형 |
설명 |
| 단일 연결 리스트 |
다음 노드 포인터만 존재 |
| 이중 연결 리스트 |
이전/다음 노드 포인터 모두 존재 |
| 원형 연결 리스트 |
마지막 노드가 head를 가리킴 |
Git과의 연관
- Git 커밋 이력이 연결 리스트 구조
- 각 커밋이 이전 커밋의 SHA-1 해시를 포인터로 보유 → 히스토리 체인 형성
관련 개념