Algorithm Workbook
[Data Structure] 이중 연결 리스트, Doubly Linked-List
likepint
2025. 3. 27. 18:57
연결 리스트 (Linked-List)
추상적 자료형인 리스트를 구현한 자료구조
데이터를 저장 할 때 하나의 데이터와 다음 데이터의 위치를 함께 저장하여, 논리적으로 연결하는 방식으로 자료를 저장
❓ 리스트란
순열(Sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의
순서가 있다는 점에서 집합과는 구별되며,
갈림길 없이 일렬로 나열되어 처음과 끝이 하나만 존재한다는 점에서 그래프와도 구별된다.
이중 연결 리스트
각 노드가 이전(prev) 노드와 다음(next) 노드를 모두 가리키는 포인터를 가진 자료구조
단일 연결 리스트와 달리 양방향으로 이동할 수 있어, 리스트를 앞뒤로 자유롭게 탐색
단일 연결 리스트와 이중 연결 리스트
| 기준 | 단일 연결 리스트 (Singly Linked List) | 이중 연결 리스트 (Doubly Linked List) |
| 구조 | 각 노드가 다음 노드(`next`)만 가리키며, 마지막 노드는 `nullptr`로 끝남 |
각 노드가 이전 노드(`prev`)와 다음 노드(`next`)를 가리킴 |
| 탐색 | 단방향 탐색, O(n) 끝에서 멈춤 |
양방향 탐색, O(n) 끝에서 멈추지만 앞뒤로 이동 가능 |
| 삽입 (특정 위치) | 위치 탐색 O(n), 삽입 O(1) | 위치 탐색 O(n), 삽입 O(1) 이전/다음 연결 조정 필요 |
| 삭제 (특정 위치) | 위치 탐색 O(n), 삭제 O(1) 이전 노드 접근 어려움 |
위치 탐색 O(n), 삭제 O(1) 이전 노드 접근 용이 |
| 리스트 끝 접근 | O(n), 마지막 노드까지 순회 | O(1), `tail` 포인터로 즉시 접근 가능 |
| 장점 | - 구현이 단순 - 메모리 효율적 - 기본 순차 작업에 적합 |
- 양방향 탐색 가능 - 삭제 시 이전 노드 접근 쉬움 - 리스트 끝 접근 빠름 |
| 단점 | - 역방향 이동 불가 - 삭제 시 이전 노드 탐색 필요 |
- 메모리 사용량 많음 - 포인터 관리 복잡 |
| 사용 사례 | - 단순 순차 처리(스택, 큐) - 메모리 절약 필요한 경우 |
- 양방향 탐색 필요(브라우저 뒤로/앞으로) - 데이터 편집(undo/redo) |