[python_dataStructure] 5. 원형연결리스트

🧩 원형연결리스트(CircularLinkedList)

• 단순연결리스트의 마지막과 끝이 서로 연결 → 원을 이루고 있는 리스트
• 마지막노드 ~ 첫노드 접근 → O(n)에서 O(1)로 단축됨

소프트웨어에서 원형연결리스트가 쓰이는경우
📎 CPU 클럭

• 클럭속도 높으면 CPU 속도 빠른 것
• CPU가 초당 실행하는 사이클 수를 측정
  

---

1 원형연결리스트

1️⃣ 형태

• 노드 끝 → 처음을 가리키는 형태
• 원(circle)형태로 구성 ➡️ 계속 회전하며 리스트 탐색

2️⃣ 특징

• 단순연결리스트와 비슷한 형태
• 처음과 끝과의 거리를 오가는 탐색 가능 → O(1)
  • 단순연결리스트 취약점 보완 ✅
• 노드 마지막 링크 : Head

---

2 원형연결리스트 구현

1️⃣ 노드의 정의

📍 Node 데이터형정의를 위한 class 생성
>>> class Node():
		def __init__(self): # 생성자
        	self.data = None # 데이터공간
            self.link = None # 링크공간

📍 첫번째노드
>>> node1 = Node()
>>> node1.data = "서울"
>>> node1.link = node1

2️⃣ 노드의 연결

📍 두번째노드
>>> node2 = Node()
>>> node2.data = "대구"

📍 첫번째 두번째노드 연결
>>> node1.link = node2
>>> node2.link = node1

3️⃣ 노드가 3개인 원형연결리스트

📍 세번째노드
>>> node3 = Node()
>>> node3.data = "부산"

📍 노드 최종연결
>>> node2.link = node3
>>> node3.link = node1

4️⃣ 노드순회

📍 노드순회
>>> current = node1
>>> print(current.data, end = '')

>>> while current.link != node1:
		current = current.link
        print(current.data, end = '')

---

3 원형연결리스트 일반적형태

• 헤드(Head) : 첫번째 노드
• 현재(Current) : 지금 처리중인 노드
• 이전(Pre) : 현재노드 앞 노드
• 마지막노드 : 첫번째 노드

---

4 원형연결리스트 데이터삽입(첫번째)

1️⃣ 동작순서

• 추가할 데이터 → Head로 지정
• 마지막 데이터 링크 → Head를 가리키게 함

2️⃣ 코드구현

📍 새노드생성
>>> newNode = Node()
>>> newNode.link = head # 링크우선연결
>>> newNode.data = "파주"

📍 Head 새노드로 지정하기
>>> last = head # 마지막노드를 첫번째노드로 우선지정 (서울)

>>> while last.link != head: # 마지막노드까지 반복
		last = last.link # 한칸씩 이동
        
>>> last.link = newNode # 마지막노드링크 -> 새노드지정
>>> head = newNode

📍 출력하기
>>> current = head
>>> print(current.data, end = '')
>>> while current.link != head:
		current = current.link
        print(current.data, end = '')
        # 파주 서울 대구 부산

---

5 원형연결리스트 데이터삽입(중간)

1️⃣ 동작순서

• 데이터를 끼워넣고자하는 2개의 노드를 찾을 때까지 → Current Pre 이동
• Pre노드 링크 → 새로운 노드를 가리키게 함
• 새로운 노드 링크 → Current 가리키게 함

2️⃣ 코드구현

📍 데이터삽입(중간)
>>> current = head

>>> while current.link != head:
		pre = current
        current = current.link
        
        if current.data = "부산":
        	node = Node() # 새로운노드생성
            node.data = "포항"
            
            # 연결하기
            node.link = current
            pre.link = current

📍 출력하기
>>> current = head
>>> print(current.data, end = '')
>>> while current.link != head:
		current = current.link
        print(current.data, end = '')
        # 파주, 서울, 대구, 포항, 부산

---

6 원형연결리스트 데이터삽입(마지막)

1️⃣ 동작순서

• 추가할노드 생성 → 마지막노드 링크가 추가할노드 데이터를 가리키게함
• 추가한노드 링크 → 첫번째노드

2️⃣ 코드구현

📍 데이터삽입(마지막)
	# current 마지막노드로 지정
>>> current = head

>>> while current.link != head:
		current = current.link

>>> newNode = Node()
>>> newNode.data = "제주"

>>> current.link = newNode
>>> newNode.link = head

📍 출력하기
>>> current = head
>>> print(current.data, end = '')
>>> while current.link != head:
		current = current.link
        print(current.data, end='')
        # 파주 서울 대구 포항 부산 제주

---

7 원형연결리스트 데이터삭제(첫번째)

1️⃣ 동작순서

• Current노드, Head 동시에 → 첫번째
• 기존 두번째노드 → Head로 지정
• Current노드를 가리키는 마지막노드를 찾음
• 마지막노드가 Head를 가리키게 함
• Current노드 삭제

2️⃣ 코드구현

📍 데이터삭제(첫번째)
>>> current = head

>>> head = head.link

>>> last = head

>>> while last.link != current:
		last = last.link

>>> last.link = head
>>> del(current)

📍 출력하기
>>> current = head
>>> print(current.data, end = '')
>>> while current.link != head:
		current = current.link
        print(current.data, end= '')
        # 서울 대구 포항 부산 제주

---

8 원형연결리스트 데이터삭제(첫번째노드외)

1️⃣ 동작순서

• 삭제할 데이터 → Current노드로 지정
• Pre노드 링크 → Current노드 링크로 저장
• Current 노드 삭제

2️⃣ 코드구현

📍 데이터삭제(첫번째노드외)
>>> current = head

>>> while current.link != head:
		pre = current
        current = current.link
        
        if current.data = "대구":
        	pre.link = current.link
            del(current)
            
📍 출력하기
>>> current = head
>>> print(current.data, end='')
>>> while current.link != head:
		current = current.link
        print(current.data, end = '')
        # 서울 포항 부산 제주

---

9 노드검색

1️⃣ 동작순서

• 현재노드 → 첫번째노드 (Head) 지정
• 현재노드 = 검색할노드 ➡️ 현재노드 반환

2️⃣ 코드구현

📍 노드검색
>>> current = head

>>> if current.data == "부산":
		print(current.data)
        
>>> while current.link != head:
		current = current.link
        
        if current.data == "부산":
        	print(current.data)
            # 부산

---

10 시간복잡도

항목	조회	삽입	삭제
선형리스트	O(1)	O(n)	O(n)
단순연결리스트	O(n)	O(1)	O(1)
원형연결리스트	O(n)	O(1)	O(1)