원형 연결 리스트 (Circular Linked List)

원형 연결 리스트 (Circular Linked List)

마지막 노드가 첫 번째 노드를 가리켜 순환 구조를 형성하는 연결 리스트로, 끝이 없는 반복적 순회가 필요한 경우에 활용

목적: 순환 순회, 끝없는 반복, 라운드 로빈, 순환 버퍼 대체

특징: 순환 구조, NULL 없음, 어느 노드든 시작점, 무한 순회 가능

종류

• •단순 원형 연결 리스트: 각 노드가 다음 노드만 가리킴, tail→head 연결
• •이중 원형 연결 리스트: 양방향 순환, head↔tail 연결

동작

• •삽입(맨 앞): 새 노드→head, tail→새 노드, O(1) (tail 유지 시)
• •삽입(맨 뒤): tail→새 노드, 새 노드→head, tail 갱신, O(1)
• •삭제: 이전 노드→다음 노드 연결, O(n) (이전 노드 탐색)
• •순회: 시작 노드 기록 후 한 바퀴 돌 때까지 반복

시간 복잡도: 삽입(앞/뒤) O(1), 삭제 O(n), 검색 O(n)

공간 복잡도: O(n)

장점: 순환 순회, 어느 노드든 접근 가능, 라운드 로빈 구현

단점: 무한 루프 위험, 종료 조건 필수, 삽입/삭제 주의

적용사례: 라운드 로빈 스케줄링, 멀티플레이어 게임 턴, 음악 재생 목록, 원형 큐

비교: 원형(순환/무한순회) vs 단순(끝존재/NULL) vs 이중(양방향/메모리↑)

연관: 연결 리스트, 이중 연결 리스트, 라운드 로빈, 큐