단일, 이중, 환형 연결 리스트는 어떻게 다른가

연결 리스트는 노드가 다음 노드를 참조하는 방식으로 이어지는 자료구조다. 구현 방식에 따라 단일 연결 리스트, 이중 연결 리스트, 환형 연결 리스트로 나뉜다.

단일 연결 리스트

각 노드가 다음 노드만 가리키는 구조다.

• 구현이 단순하다
• 메모리 오버헤드가 적다
• 뒤로 이동은 어렵다

앞에서 순차적으로 순회하는 용도에는 충분하지만, 이전 노드로 되돌아가야 하는 경우에는 불편하다.

이중 연결 리스트

각 노드가 다음 노드와 이전 노드를 모두 가진다.

• 양방향 탐색이 가능하다
• 삭제와 삽입 위치 조정이 더 유연하다
• 메모리 사용량이 더 크다

Deque 같은 구조를 구현할 때 이중 연결 리스트가 자주 등장하는 이유도 여기에 있다.

환형 연결 리스트

마지막 노드가 다시 처음 노드를 가리키는 구조다.

• 끝과 처음이 이어져 있다
• 순환 구조를 표현하기 쉽다
• 종료 조건을 잘못 두면 무한 순회에 빠지기 쉽다

스케줄링, 라운드 로빈, 순환 버퍼와 비슷한 문제를 생각할 때 개념적으로 자주 등장한다.

어떻게 고를 것인가

• 단순 순차 처리: 단일 연결 리스트
• 양방향 이동과 양끝 조작: 이중 연결 리스트
• 순환 구조 표현: 환형 연결 리스트

실무에서는 직접 구현보다 표준 컬렉션을 더 자주 쓰지만, 각 연결 리스트의 차이를 이해하면 자료구조 선택 이유를 설명하기 쉬워진다.