연결 리스트의 주요 유형
연결 리스트(Linked List)는 각 노드가 데이터와 함께 다른 노드를 가리키는 참조(포인터)를 담고 있는 선형 자료구조입니다. 구현 방식에 따라 크게 세 가지 형태로 나뉘며, 각 유형은 탐색 방향과 구조에서 차이를 보입니다.
1. 단일 연결 리스트 (Singly Linked List)
각 노드가 다음 노드만을 가리키는 가장 기본적인 형태입니다. 탐색이 오직 앞쪽에서 뒤쪽으로 한 방향으로만 진행되기 때문에, 특정 노드의 이전 노드에 접근하려면 처음부터 다시 순회해야 합니다.
2. 이중 연결 리스트 (Doubly Linked List)
각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조입니다. 덕분에 앞뒤 양방향 탐색이 자유롭고, 역방향 순회나 중간 노드 삭제 시 효율적입니다. 대신 노드 하나당 참조가 두 개 필요해 메모리 사용량이 더 많습니다.
3. 원형 연결 리스트 (Circular Linked List)
마지막 노드가 첫 번째 노드를 next로 가리키고, 첫 번째 노드가 마지막 노드를 prev로 가리켜 순환 구조를 이루는 형태입니다. 끝이 없이 계속 순회할 수 있어 음악 재생 목록, 라운드 로빈 스케줄링 등 순환이 필요한 상황에 적합합니다.
유형별 비교 요약
- 단일 연결 리스트: 한 방향 탐색만 가능하며, 구조가 단순하고 메모리 효율이 좋습니다.
- 이중 연결 리스트: 양방향 탐색이 가능하지만, 추가 참조 저장을 위해 더 많은 메모리가 필요합니다.
- 원형 연결 리스트: 마지막 노드와 첫 노드가 서로 연결되어 무한 순회가 가능합니다.
상황에 맞는 연결 리스트 유형을 선택하면 데이터 삽입·삭제·탐색 작업의 성능을 크게 개선할 수 있습니다.