이중 연결 리스트(Doubly Linked List)와 원형 연결 리스트(Circular Linked List)는 연결 리스트를 살짝 변형하여 단점을 개선한 자료구조이다.
연결 리스트를 배열과 비교했듯, 이들 역시 기본형인 단순 연결 리스트와 비교하면서 이해하는 게 효과적일 것 같다.
단순 연결 리스트 vs 이중 연결 리스트 vs 원형 연결 리스트
1. 개념
단순 연결 리스트: 일방향적. Head 노드 → Tail 노드 방향으로 포인터가 다음 노드 주소를 일방향적으로 가리킨다.
이중 연결 리스트: 양방향적. Head 노드 ↔ Tail 노드 양방향에서 다음 노드 주소를 양방향적으로 가리킨다.
원형 연결 리스트: 일방향적이나 순환적. Head 노드 → Tail 노드 일방향으로 포인터가 가리키지만, Tail 노드의 포인터는 다시 Head 노드의 주소를 가리킨다.
2. 데이터 안정성
단순 연결 리스트: 만약 Head 노드를 유실한다면 리스트 전체를 유실하게 된다.
이중 연결 리스트: 특정 노드의 한쪽 방향 포인터만 유실했다면 복구할 수 있다. Tail 노드에서부터 역으로 추적할 수 있기 때문.
원형 연결 리스트: 특정 노드의 포인터를 유실했을 경우, 순환적으로 추적할 수 있기 때문에 복구할 수 있다.
3. 비용
단순 연결 리스트의 노드는 [데이터 + 포인터] 조합으로 필요한 메모리가 가볍다.
이중 연결 리스트의 노드는 포인터가 2배로 필요하기 때문에 자료구조가 조금 더 무겁다.
원형 연결 리스트의 노드는 단순 연결 리스트와 마찬가지로 [데이터 + 포인터] 조합으로 필요한 메모리가 가볍다. 마지막 노드에서의 포인터는 단순 연결 리스트도 가지고 있다. 다만 차이점은 해당 포인터 값이 None인가 Head 노드를 가리키고 있는가의 여부.
4. 데이터 추가, 삭제 시간 복잡도
단순 연결 리스트: 맨 앞 O(1), 그 외 O(n)
이중 연결 리스트: 맨 앞과 맨 뒤 O(1), 그 외 O(n). 그러나 양방향 접근이 가능하므로 더 효율적일 것으로 기대가 가능하다.
원형 연결 리스트: 맨 앞 O(1), 그 외 O(n)
5. 특정 노드 탐색 시간 복잡도
단순 연결 리스트: O(n)
이중 연결 리스트: O(n). 그러나 양방향 접근이 가능하므로 더 효율적일 것으로 기대가 가능하다.
원형 연결 리스트: O(n)
6. 용도
단순 연결 리스트: 기본적인 리스트 구현, 데이터의 순차적인 접근이 주된 경우
이중 연결 리스트: 데이터의 양방향 탐색이 필요한 경우(ex. 스트리밍 사이트의 플레이리스트), 데이터의 앞 뒤 정보 맥락이 중요한 경우.
원형 연결 리스트: 데이터의 순환적인 구조가 필요한 상황 (ex. 순환 큐 구현, 시스템 자원을 순환적으로 할당하는 경우, 플레이어가 순환적으로 턴을 진행하는 경우)
'Computer Science > 자료구조 (Data Structure)' 카테고리의 다른 글
| 자료구조 | 이진 트리, 트리 순회(Tree Traversal) (0) | 2023.10.20 |
|---|---|
| 자료구조 | 트리(Tree) (1) | 2023.10.20 |
| 자료구조 | 해시 테이블(Hash Table) (1) | 2023.10.19 |
| 자료구조 | 연결 리스트(Linked List) (0) | 2023.10.17 |
| 자료구조 | 배열, 스택, 큐 (0) | 2023.10.16 |
