[자료구조/C언어] 원형 연결 리스트(Circular Linked List) 개념과 활용 사례 (시험 단골 주제)

이전에 다룬 단일 연결 리스트와 이중 연결 리스트에 이어, 시험에서 응용 문제로 매우 자주 등장하는 원형 연결 리스트(Circular Linked List)에 대해 알아보겠습니다.

"마지막 노드의 포인터가 NULL이 아니라면 어떻게 될까?"라는 아이디어에서 출발한 원형 연결 리스트의 핵심 개념, C언어 구현 방식, 그리고 운영체제(OS)와 실생활 활용 사례까지 한눈에 보기 쉽게 정리해 드립니다!

1. 원형 연결 리스트(Circular Linked List) 란?

원형 연결 리스트는 일반 연결 리스트와 달리 마지막 노드(Tail)의 next 포인터가 NULL을 가리키지 않고, 첫 번째 노드(Head)를 가리키도록 연결된 자료구조입니다.

• 특징:
  • 노드들이 끝없이 이어져 있어 '원형(Circular)' 고리 구조를 형성합니다.
  • 리스트의 끝(NULL)이 존재하지 않으므로, 한 노드에서 출발하여 포인터를 계속 따라가면 모든 노드를 무한히 순회할 수 있습니다.
• 구조적 이점:
  • 단일 연결 리스트에서는 리스트의 맨 뒤에 새로운 노드를 추가하려면 Head부터 Tail까지 전체를 탐색해야 했지만, 원형 연결 리스트에서는 Tail 포인터 하나만 유지하면 Head와 Tail 모두에 $O(1)$ 시간 만에 접근 및 삽입이 가능합니다.

C

 

// C언어 원형 연결 리스트의 노드 구조 (단일 연결 리스트와 동일)
typedef struct Node {
    int data;
    struct Node* next; // 마지막 노드의 next는 다시 Head를 가리킴!
} Node;

2. 원형 연결 리스트의 장점과 단점

시험 문제에서 서술형으로 단골 출제되는 장단점 포인트입니다.

⭕ 장점

1. 끝이 없는 연속 순회: 모든 노드가 연결되어 있어 어떤 노드에서 시작하더라도 전체 노드에 접근할 수 있습니다.
2. Head와 Tail 접근의 용이성: Tail의 next가 곧 Head이므로, Tail 포인터만 관리하면 리스트의 맨 앞과 맨 뒤에 노드를 추가하는 연산이 모두 $O(1)$로 매우 효율적입니다.
3. 메모리 절약: NULL 포인터를 사용하는 버리는 공간 없이 모든 포인터가 의미 있는 노드를 가리킵니다.

❌ 단점

1. 무한 루프(Infinite Loop) 주의: 리스트의 끝(NULL)이 없기 때문에, 탐색 조건(p == Head)을 잘못 설정하면 프로그램이 무한 루프에 빠지기 쉽습니다.
2. 구현 및 예외 처리 복잡: 노드가 1개만 남았을 때의 삭제 처리, 또는 삽입 시 포인터 재연결 조건이 일반 리스트보다 까다롭습니다.

3. 핵심 활용 사례 (시험 단골 문제!)

원형 연결 리스트는 "여러 대상이 순서대로 돌아가며 자원을 사용할 때" 최적의 자료구조로 사용됩니다.

① 운영체제(OS)의 라운드 로빈(Round Robin) CPU 스케줄링

운영체제가 여러 프로세스에게 CPU 사용 시간을 공정하게 할당할 때 사용합니다. 각 프로세스가 순서대로 CPU를 조금씩 사용한 뒤, 다시 맨 앞으로 돌아가 다음 순서를 기다리는 구조에 원형 연결 리스트가 그대로 사용됩니다.

② 플레이어 턴(Turn) 기반 게임

보드게임이나 턴제 RPG 게임에서 플레이어 1 $\rightarrow$ 플레이어 2 $\rightarrow$ 플레이어 3 $\rightarrow$ 다시 플레이어 1 순서로 턴이 계속 순환할 때 활용됩니다.

③ 멀티태스킹 작업 대기열 (Buffer)

스트리밍 서비스의 버퍼링 데이터 관리나, 컴퓨터에서 Alt + Tab을 눌러 실행 중인 창을 순환 선택할 때 내부적으로 원형 구조를 활용합니다.

4. 한눈에 비교하는 차이점 (시험 핵심 요약)

시험 직전 이것만 정리하면 끝나는 비교표입니다!

구분	일반 단일 연결 리스트	원형 연결 리스트 (Circular)
마지막 노드의 next	NULL	첫 번째 노드 (Head)
탐색 종료 조건	p == NULL	p == Head (시작 위치로 돌아왔는지 확인)
Tail 위치 삽입 시간	$O(N)$ (Head만 있을 때)	$O(1)$ (Tail 포인터 활용 시)
주요 활용 분야	일반적인 데이터 저장/관리	Round-Robin 스케줄링, 턴제 순환 시스템

5. 시험 단골 출제 유형 체크

1. Q. 원형 연결 리스트에서 순회를 종료할 때 사용해야 하는 올바른 조건식은?
2. 👉 NULL을 체크하는 것이 아니라, 포인터가 다시 시작 노드(Head)로 돌아왔는지(p == Head)를 확인해야 합니다.
3. Q. 운영체제의 라운드 로빈(Round Robin) 스케줄링 구현에 가장 적합한 자료구조는?
4. 👉 원형 연결 리스트(Circular Linked List)입니다.