'N'개의 노드를 가진 원형 연결 리스트(circular linked list)를 만들고 노드 개수를 계산하려면 먼저 'Node' 클래스를 정의해야 합니다. 원형 리스트에 담긴 데이터 요소를 화면에 출력하기 위해 별도의 메서드를 추가로 정의할 수도 있습니다.
이 클래스에는 두 가지 속성이 있습니다. 하나는 노드에 저장된 데이터이고, 다른 하나는 연결 리스트에서 다음 노드에 접근하기 위한 참조입니다. 원형 연결 리스트에서는 head(머리)와 rear(꼬리)가 서로 인접해 있으며, 마지막 노드가 다시 첫 번째 노드와 연결되어 하나의 원을 이룹니다. 따라서 마지막 노드에 'NULL' 값이 존재하지 않는다는 점이 일반 선형 연결 리스트와의 가장 큰 차이입니다.
또한 초기화 함수를 포함하는 'linked_list' 클래스를 만들어야 하며, 이때 head는 'None'으로 초기화됩니다.
아래는 전체 동작 과정을 보여주는 예시입니다.
예제 코드
class Node:
def __init__(self, my_data):
self.data = my_data
self.next = None
def add_data(head_ref, my_data):
ptr_1 = Node(0)
temp = head_ref
ptr_1.data = my_data
ptr_1.next = head_ref
if (head_ref != None):
while (temp.next != head_ref):
temp = temp.next
temp.next = ptr_1
else:
ptr_1.next = ptr_1
head_ref = ptr_1
return head_ref
def count_node(head):
temp = head
result = 0
if (head != None):
while True:
temp = temp.next
result = result + 1
if (temp == head):
break
return result
if __name__ == '__main__':
head = None
head = add_data(head, 78)
head = add_data(head, 56)
head = add_data(head, 22)
print("Elements are added to list")
print("The number of nodes are : ")
print(count_node(head))
출력 결과
Elements are added to list
The number of nodes are :
3
코드 설명
- 'Node' 클래스가 정의됩니다. 각 노드는 자신이 담고 있는 데이터(data)와 다음 노드를 가리키는 참조(next)를 가집니다.
- 'add_data' 함수는 새로운 노드를 생성한 뒤, 기존의 마지막 노드를 찾아 새 노드와 연결하고 head를 갱신하여 원형 구조를 유지합니다. 리스트가 비어 있는 경우에는 노드가 자기 자신을 가리키도록 설정합니다.
- 'count_node' 함수는 head부터 출발해 한 바퀴를 돌며 다시 head에 도달할 때까지 노드 수를 세어 반환합니다.
- 메인 블록에서는 빈 리스트를 만든 후 78, 56, 22를 차례대로 추가합니다.
- 마지막으로 count_node 함수를 호출하면 노드 개수인 3이 출력됩니다.