[Data Structure] 단일 환형 연결 리스트, Singly Circular Linked-List

---

연결 리스트 (Linked-List)

추상적 자료형인 리스트를 구현한 자료구조
데이터를 저장 할 때 하나의 데이터와 다음 데이터의 위치를 함께 저장하여, 논리적으로 연결하는 방식으로 자료를 저장

❓ 리스트란
순열(Sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의
순서가 있다는 점에서 집합과는 구별되며,
갈림길 없이 일렬로 나열되어 처음과 끝이 하나만 존재한다는 점에서 그래프와도 구별된다.

---

단일 환형 연결 리스트 (Singly Circular Linked-List)

단일 연결 리스트의 변형으로, 마지막 노드의 next 포인터가 첫 노드(head)를 가리키는 순환 구조를 가진 자료구조

단일 연결 리스트와 단일 환형 연결 리스트

	단일 연결 리스트 (Singly Linked-List)	단일 환형 연결 리스트 (Singly Circular Linked-List)
구조	각 노드가 다음 노드(`next`)만 가리키며, 마지막 노드는 `nullptr`로 끝남	각 노드가 다음 노드(`next`)를 가리키며, 마지막 노드가 첫 노드(`head`)로 연결
연결 방향	단방향(앞에서 뒤로만 이동 가능)	단방향(순환 구조로 끝없이 이동 가능)
탐색	마지막 노드의 `next`가 `nullptr`로 종료	마지막 노드의 `next`가 `head`를 가리켜 순환
탐색	단방향 탐색, O(n) 끝에서 멈춤	단방향 순환 탐색, O(n) 순환 종료 조건 필요
삽입 (특정 위치)	위치 탐색 O(n), 삽입 O(1)	위치 탐색 O(n), 삽입 O(1) 순환 유지 필요
삭제 (특정 위치)	위치 탐색 O(n), 삭제 O(1) 이전 노드 접근 어려움	위치 탐색 O(n), 삭제 O(1) 순환 구조 유지 필요
리스트 끝 접근	O(n) 마지막 노드까지 순회	O(n) 마지막 노드 탐색 후 `head`로 연결

---

구현 코드 (C++)