원형연결리스트

원형연결리스트는 말 그대로 연결리스트가 원형 형태로 이루어진 것으로, 가장 큰 특징으로는 마지막 노드와 첫 번째 노드가 만난다는 점이다. 이러한 원형의 특징을 가졌기에 원형연결리스트, 다른 말로 순환연결리스트라고도 부른다.

이 원형 연결리스트는 시작과 끝이 없기 때문에 헤드 포인터를 설정해주지 않으면 무한히 순환할 수 있다. 그래서 이 부분에 주의해야 한다.

https://kangdy25.tistory.com/82

원형 연결 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다는 장점을 가지고 있다.

 

구현

코드에 주석을 달아놓았으니 이해하기 어렵지 않을 것이다.

# 노드를 정의하며,
# 각 노드는 데이터 (data)와 다음 노드를 가리키는 링크 (link)를 포함함
class ListNode:
    def __init__(self, data):
        self.data = data
        self.link = None

# 원형 연결 리스트를 출력
# 리스트의 끝에 도달할 때까지 노드를 순회하면서 각 노드의 데이터를 출력하고,
# 마지막 노드에서는 다시 처음 노드로 연결된 원형 특성을 고려하여 출력
def print_list(head):
    if head is None:
        return

    current = head
    while True:
        print(current.data, end=" -> ")
        current = current.link
        if current == head:
            break
    print()

# 리스트의 처음에 노드를 삽입
# 새로운 노드를 생성하고, 리스트가 비어있을 경우 자기 자신을 가리키게 하며, 
# 비어 있지 않을 경우 기존의 처음 노드를 가리키는 링크를 조정하여 새로운 노드를 연결
def insert_first(head, data):
    new_node = ListNode(data)
    if head is None:
        new_node.link = new_node
    else:
        new_node.link = head.link
        head.link = new_node
    return new_node  # 변경된 헤드 포인터 반환

# 리스트 끝에 노드를 삽입
# 앞선 함수와 반대
def insert_last(head, data):
    new_node = ListNode(data)
    if head is None:
        new_node.link = new_node
    else:
        new_node.link = head.link
        head.link = new_node
        head = new_node
    return head  # 변경된 헤드 포인터를 반환

# 원형 연결 리스트 테스트 프로그램
if __name__ == "__main__":
    head = None

    # list = 10 -> 20 -> 30 -> 40
    head = insert_last(head, 20)
    head = insert_last(head, 30)
    head = insert_last(head, 40)
    head = insert_first(head, 10)
    print_list(head)