원형 이중 연결 리스트

Preface

 

이번 장에선 연결 리스트의 단점을 보완한 원형 이중 연결 리스트를 공부했다.

 

코드의 구성 면에선 포인터와 커서를 이용한 연결 리스트와 크게 다른 부분이 없어 손쉽게 코드를 작성할 수 있었다.

 

나는 왜 지금껏 연결 리스트를 공부하며 노드를 역순으로 스캔할 생각을 하지 않았을까?

 

코드의 효율성은 단순히 얻어지는 것이 아니라 끝없이 더 나은 방법을 모색해야만 떠올릴 수 있는 것인데, 나는 책에 나온 방법에 한해서만 고민하는 것 같다.

 

아마도 '우물 안의 개구리'는 이럴 때 쓰는 말이 아닐까 싶다.

 

더 넓게 더 멀리 봐야 하는데 주어진 내용이 전부라 생각하고 그 이상은 생각하지 않게 된다.

 

공부를 하면 할 수록 책에 나온 내용만을 공부하는 것이 아닌, 개인 프로젝트를 통해 나만의 코드를 작성하며 이런 저런 방법을 고민해보는 것이 정말 중요한 것 같다는 생각이 든다.

---

 

- 원형 리스트 : 연결 리스트의 꼬리 노드가 다시 머리 노드를 가리키는 구조

 

 

- 연결 리스트의 단점 : 앞쪽 노드를 찾기 어려움

 

 

- 이중 연결 리스트 : 각 노드에 뒤쪽 노드의 포인터뿐만 아니라 앞쪽 노드의 포인터도 주어지는 구조

→ 연결 리스트의 단점을 개선한 것이다.

 

 

- 원형 이중 연결 리스트 : 원형 리스트와 이중 연결 리스트를 결합한 구조

 

 

- 원형 이중 연결 리스트 코드

# 원형 이중 연결 리스트 구현하기

from __future__ import annotations
from typing import Any, Type


class Node:  # 원형 이중 연결 리스트용 노드 클래스
    def __init__(self, data: Any = None, prev: Node = None,
                 next: Node = None) -> None:
        self.data = data
        self.prev = prev or self
        self.next = next or self
        # 파이썬 논리 연산자 참고


class DoubleLinkedList:
    def __init__(self) -> None:
        self.head = self.current = Node()
        self.no = 0

    def __len__(self) -> int:
        return self.no

    def is_empty(self) -> bool:  # 더미 노드를 참조하므로 비어있는 것
        return self.head.next is self.head

    def search(self, data: Any) -> Any:  # 맨 앞에 더미 노드가 있으므로 다음 노드부터 검색
        cnt = 0
        ptr = self.head.next
        while ptr is not self.head:
            if data == ptr.data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1

    def __contains__(self, data: Any) -> bool:
        return self.search(data) >= 0

    def print_current_node(self) -> None:
        if self.is_empty():
            print('주목 노드는 없습니다.')
        else:
            print(self.current.data)

    def print(self) -> None:
        ptr = self.head.next
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.next

    def print_reverse(self) -> None:
        ptr = self.head.prev
        while ptr is not self.head:
            print(ptr.data)
            ptr = ptr.prev

    def next(self) -> bool:
        if self.is_empty() or self.current.next is self.head:
            return False
        self.current = self.current.next
        return True

    def prev(self) -> bool:
        if self.is_empty() or self.current.prev is not self.head:
            return False
        self.current = self.current.prev
        return True

    def add(self, data: Any) -> None:
        node = Node(data, self.current, self.current.next)
        self.current.next.prev = node
        self.current.next = node
        self.current = node
        self.no += 1

    def add_first(self, data: Any) -> None:
        self.current = self.head
        self.add(data)

    def add_last(self, data: Any) -> None:
        self.current = self.head.prev
        self.add(data)

    def remove_current_node(self) -> None:
        if not self.is_empty():
            self.current.prev.next = self.current.next
            self.current.next.prev = self.current.prev
            self.current = self.current.prev
            self.no -= 1
            if self.current is self.head:
                self.current = self.head.next

    def remove(self, p: Node) -> None:
        ptr = self.head.next

        while ptr is not self.head:
            if ptr is p:
                self.current = p
                self.remove_current_node()
                break
            ptr = ptr.next

    def remove_first(self) -> None:
        self.current = self.head.next
        self.remove_current_node()

    def remove_last(self) -> None:
        self.current = self.head.prev
        self.remove_current_node()

    def clear(self) -> None:
        while not self.is_empty():
            self.remove_first()
        self.no = 0

    def __iter__(self) -> DoubleLinkedListIterator:
        return DoubleLinkedListIterator(self.head)

    def __reversed__(self) -> DoubleLinkedListReverseIterator:
        return DoubleLinkedListReverseIterator(self.head)


class DoubleLinkedListIterator:
    def __init__(self, head: Node):
        self.head = head
        self.current = head.next

    def __iter__(self) -> DoubleLinkedListIterator:
        return self

    def __next__(self) -> Any:
        if self.current is self.head:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return data


class DoubleLinkedListReverseIterator:
    def __init__(self, head: Node):
        self.head = head
        self.current = head.prev

    def __iter__(self) -> DoubleLinkedListReverseIterator:
        return self

    def __next__(self) -> Any:
        if self.current is self.head:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.prev
            return data

 

※  파이썬에서 '='은 연산자가 아니라 변수에 대한 단순 참조를 나타낼 뿐이다.

 

 

- 원형 이중 연결 리스트 프로그램 코드

from enum import Enum
from double_list import DoubleLinkedList

Menu = Enum('Menu', ['머리에노드삽입', '꼬리에노드삽입', '주목노드바로뒤삽입',
                     '머리노드삭제', '꼬리노드삭제', '주목노드출력',
                     '주목노드이동', '주목노드역순이동', '주목노드삭제',
                     '모든노드삭제', '검색', '멤버십판단', '모든노드출력',
                     '모든노드역순출력', '모든노드스캔', '모든노드역순스캔', '종료'])


def select_menu() -> Menu:
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)


lst = DoubleLinkedList()

while True:
    menu = select_menu()

    if menu == Menu.머리에노드삽입:
        lst.add_first(int(input('머리 노드에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.꼬리에노드삽입:
        lst.add_last(int(input('꼬리 노드에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.주목노드바로뒤삽입:
        lst.add(int(input('주목 노드 바로 뒤에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.머리노드삭제:
        lst.remove_first()

    elif menu == Menu.꼬리노드삭제:
        lst.remove_last()

    elif menu == Menu.주목노드출력:
        lst.print_current_node()

    elif menu == Menu.주목노드이동:
        lst.next()

    elif menu == Menu.주목노드역순이동:
        lst.prev()

    elif menu == Menu.주목노드삭제:
        lst.remove_current_node()

    elif menu == Menu.모든노드삭제:
        lst.clear()

    elif menu == Menu.검색:
        pos = lst.search(int(input('검색할 값을 입력하세요.: ')))
        if pos >= 0:
            print(f'이 키를 갖는 데이터는 {pos + 1}번째에 있습니다.')
        else:
            print('해당 데이터가 없습니다.')

    elif menu == Menu.멤버십판단:
        print('그 값의 데잉터는 포함되어'
              + (' 있습니다.' if int(input('판단할 값을 입력하세요.: ')) in lst
                 else '있지 않습니다.'))

    elif menu == Menu.모든노드출력:
        lst.print()

    elif menu == Menu.모든노드역순출력:
        lst.print_reverse()

    elif menu == Menu.모든노드스캔:
        for e in lst:
            print(e)

    elif menu == Menu.모든노드역순스캔:
        for e in reversed(lst):
            print(e)

    else:
        break