[03-5] 연결 리스트(Linked List) - 환형 연결 리스트(Circular Linked List)

1. 개요 & 알고리즘

Circular linked list는 Simple linked list와 같은 노드 구조를 가지고 있지만, 제일 마지막 노드가 가장 처음의 노드를 가리키고 있다는 점이 다릅니다. 즉, Circular linked list에는 tail이라는 개념이 없습니다. ("C로 배우는 알고리즘"^[각주:1])

Circular linked list를 이용하는 문제는 "요셉의 문제"입니다. A에서 J까지 10명이 시계 방향으로 원모양을 만들어 순서대로 앉아 있다고 할 때, A부터 시작해서 4명 간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될까하는 문제입니다. 이 경우는 A, E, I, D, J, G, F, H, C, B의 순이됩니다.

2. 동작 코드

기본적인 코드는 Simple linked list와 거의 유사하지만, LinkedList class 초기화시 tail을 정의하지 않았습니다.

class LinkedList:
    def __init__(self, key):
        self.head = Node()
        self.head.key = key
        self.head.next = self.head

추가로 delete node 부분에서 header를 삭제하는 경우에 대해 보완을 했습니다.

def delete_node(self, key):
    p = self.head
    s = p.next
    # If we need to delete head
    if key == p.key:
        if s == self.head:
            return -1
        else:
            while True:
                if s.next == self.head:
                    s.next = self.head.next
                    self.head = s.next
                    return key
                else:
                    s = s.next
    # delete except head node
    while s.key != key and s != self.head:
        p = p.next
        s = p.next
    if s != self.head:
        p.next = s.next
        return key
    else:
        return -1

"요셉의 문제"도 LinkedList class내에서 수행하도록 했습니다.

def josephus(self, step):
    s = self.head
    while(True):
        print(s.key, "->", end=" ")
        self.delete_node(s.key)
        for i in range(step):
            s = s.next
        if s == self.head:
            print(s.key)
            break

3. 실행 코드

실행 코드는 LinkedList class를 정의하고, node를 입력 받은 수 만큼 생성한 후 "요셉의 문제"를 풀도록 하였습니다. ("C로 배우는 알고리즘" 리스트 3-5 : JOSEPH.C에 대응)

#main() function
if __name__ == "__main__":
    totalcount = int(input("Input total node's count : "))
    step = int(input("Input step for josephus's problem : "))

    list = LinkedList('A')
    # Already insert 'A' for header. So we only need to insert_node (totalcount-1)
    for i in range(totalcount-1):
        list.insert_node(chr(ord('B')+i))
    list.josephus(step)

4. Tips

1. LinkedList를 생성하면서 head node를 하나 생성하므로, 실제 insert_node()는 입력 받은 갯수-1만큼만 수행합니다.

2. Node의 key 값은 str type인데, for loop를 사용해서 integer 단위로 증가시키기 위해서는 변환이 필요^[각주:2]합니다. 이때 ord()를 사용했습니다.

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_5.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. https://stackoverflow.com/questions/704152/how-can-i-convert-a-character-to-a-integer-in-python-and-viceversa [본문으로]