연결 리스트 (Linked List) 4 - 원형 연결 리스트 (Circular Linked List)

원형 연결 리스트(Circular Linked List)

연결 리스트에서는 첫 노드와 마지막 노드에 접근성이 극적으로 차이난다. 첫 노드에는 단번에 연결 가능하고, 두번째 노드에는 링크를 끝까지 따라가야 접근할 수 있다. 그 결과 원소를 삽입/삭제할 때, 맨 앞, 맨 끝에 따라서 차이가 난다. 따라서, 이 차이는 마지막 노드가 첫 번째 노드를 링크하도록 바꾸면 해소될 수 있고, 이런 구조의 연결 리스트를 원형 연결 리스트라 한다. 

레퍼런스 __head 대신 마지막 노드에 대한 레퍼런스 __tail을 두고, 마지막 노드가 맨 앞의 더미 헤드 노드를 링크하게 만든다. 빈 원형 연결 리스트는 더미 헤드 노드가 자신을 링크한다. __tail을 마지막 노드를 가리키게 만들었을 때, 맨 뒤와맨 앞에 대한 접근성의 차이는 업서진다.

 

원형 연결 리스트 구현 및 개선점

원형 연결 리스트

리스트의 맨 앞을 레퍼런스 __head 대신 맨 끝을 레퍼런스 __tail을 가리키도록 함으로써, 리스트의 맨 앞과 맨 뒤에 접근성의 차이가 없어졌다. 

 

가변 파라미터

기존에 pop, get 같은 함수는 인자가 없거나 -1인 경우는 처리하지 않았다. 하지만 원형 연결 리스트를 사용하면, 맨 끝 원소에 접근을 용이하게 해서 처리할 수 있다. 

def pop(self, *args):
	if self.isEmpty():
    	return None
    
    if len(args) != 0: # 인자가 있으면 인가 값을 i에 할당
    	i = args[0]
    if len(args) == 0 or i == -1: # 인자 값이 -1일 경우 맨 끝 원소의 인덱스 할당
    	i = self.__numItems -1 
    if (i>=0 and i <= self.__numItems-1): 
    	prev = self.getNode(i-1)
        retItem = prev.next.item
        prev.next = prev.next.next
        self.__numItems -= 1
        return retItem
    else:
    	return None

 

순회자(Iterator)

원형 연결 리스트를 사용하면 클래스를 순회 가능한 클래스로 만들어줄 수 있다. 순회 가능 클래스가 되려면 __iter__()와 __next__()가 준비되어 있어야 한다. 

def count(self, x) -> int:
	cnt = 0
    for element in self:
    	if element == x:
        	cnt += 1
    return cnt
    
def extend(self, a):
	for element in a:
    	self.append(element)

def copy(self) 'CircularLinkedList' :
	a = CircularLinkedList()
    for element in self:
    	a.append(element)
    return a

 

전체 코드

class ListNode:
    def __init__(self, item, link):
        self.item = item
        self.next = link

class CircularLinkedListIterator:
    def __init__(self, alist):
        self.__head = alist.getNode(-1)
        self.iterPosition = self.__head.next

    def __next__(self):
        if self.iterPosition == self.__head:
            raise StopIteration
        else:
            item = self.iterPosition.item
            self.iterPosition = self.iterPosition.next
            return item

class CircularLinkedList:
    def __init__(self):
        self.__tail = ListNode("dummy", None)
        self.__tail.next = self.__tail
        self.__numItems = 0

    def insert(self, i:int, newItem)-> None:
        if(i>=0 and i <= self.__numItems):
            prev = self.getNode(i-1)
            newNode = ListNode(newItem, prev.next)
            prev.next = newNode
            if i == self.numItems:
                self.__tail = newNode
            self.__numItems += 1
        else:
            print("out of bound in insert")

    def append(self, newItem) -> None:
        newNode = ListNode(newItem, self.__tail.next)
        self.__tail.next = newNode
        self.__tail = newNode
        self.__numItems += 1

    def pop(self, *args):
        if self.isEmpty():
            return None
        if len(args) != 0:
            i = args[0]
        if len(args) == 0 or i == -1:
            i = self.__numItems-1
        if(i>=0 and i<=self.__numItems-1):
            prev = self.getNode(i-1)
            retItem = prev.next.item
            prev.next = prev.next.next
            if i == self.__numItems-1:
                self.__tail = prev
            self.__numItems -= 1
            return retItem
        else:
            return None

    def remove(self, x):
        (prev, curr) = self.__findNode(x)
        if curr != None:
            prev.next = curr.next
            if curr == self.__tail:
                self.__tail = prev
            self.__numItems -= 1
            return x
        else:
            return None

    def get(self, *args):
        if self.isEmpty():
            return None
        if len(args) != 0:
            i = args[0]
        if len(args) == 0 or i == -1:
            i = self.__numItems - 1
        if (i>= 0 and i<=self.__numItems-1):
            return self.getNode(i).item
        else:
            return

    def index(self, x) -> int:
        cnt = 0
        for element in self:
            if element == x:
                cnt+=1
        return -12345

    def isEmpty(self) -> bool:
        return self.__numItems == 0

    def size(self) -> int:
        return self.__numItems

    def clear(self):
        self.__tail = ListNode("dummy", None)
        self.__tail.next = self.__tail
        self.__numItems = 0

    def count(self, x):
        cnt = 0
        for element in self:
            if element == x:
                cnt+= 1
        return cnt

    def extend(self, a):
        for x in a:
            self.append(a)

    def copy(self) -> b'CircularLinkedList':
        a = CircularLinkedList()
        for element in self:
            a.append(element)
        return a

    def reverse(self) -> None:
        __head = self.__tail.next  # dummy head
        prev = __head
        curr = prev.next
        next_node = curr.next

        curr.next = __head
        __head.next = self.__tail
        self.__tail = curr

        for _ in range(self.__numItems - 1):
            prev = curr
            curr = next_node
            next_node = next_node.next
            curr.next = prev

    def sort(self) -> None:
        a = []
        for element in self:
            a.append(element)
        a.sort()
        self.clear()
        for element in a:
            self.append(element)

    def __findNode(self, x):
        __head = prev = self.__tail.next
        curr = prev.next
        while curr != __head:
            if curr.item == x:
                return(prev, curr)
            else:
                prev = curr; curr = curr.next
        return (None, None)

    def getNode(self, i:int) -> ListNode:
        curr = self.__tail.next
        for index in range(i+1):
            curr = curr.next
        return curr

    def printList(self) -> None:
        for element in self:
            print(element, end = ' ')
        print()

    def __iter__(self):
        return CircularLinkedListIterator(self)