원형 이중 연결 리스트

이번 단원도 연결리스트이기 때문에 어려운 내용없이 잘 공부했던 것 같다. 중간중간 헷갈리는 부분도 있었지만 내가 궁금했던 질문을 적어놓고 다시 책을 읽어보니 쉽게 풀렸다.

 

이제 이 책도 내일이면 다 끝날 것 같은데 이제 곧 개강이기도 하니 조금 더 흥미를 가지고 있는 html를 공부 할 예정이다.

---

원형 이중 연결 리스트 

 

꼬리노드의 다음이 다시 머리노드인 리스트

 

특징으로는 뒤쪽 노드를 찾기 쉬운 장점이 있는 반면 앞쪽 노드를 찾기 어렵다는 단점이 존재한다. 하지만 이런 단점을 보완한 방법이 이중 연결 리스트이다. 

 

기존 연결리스트는 모두 자신의 다음 노드의 주소만 가지고 있을 뿐 이전 노드의 주소는 없었지만 이중 연결리스트는 양방향으로 이동이 가능하다. 

 

다음은 원형 이중 연결리스트의 코드이다.

from __future__ import  annotations
from typing import Any, Type

class Node:
    def __init__(self, data: None, prev: None, next:None):
        self.data = data
        self.prev = prev or self    # prev가 None이 아니면 prev를 대입 None일시 self대입
        self.next = next or self    # 위와 같음

class DoubleLinkedList:
    '''원형 이중 연결리스트 클래스'''
    def __init__(self):
        self.head = self.current = Node(1,1,1)   # 더미 노드 생성
        self.no = 0

    def __len__(self):
        return self.no

    def is_empty(self):
        '''리스트가 비어있는지 확인'''
        return self.head.next is self.head      # 헤드의 다음이 헤드인지 True/False

    def search(self, data):
        '''검색'''
        cnt = 0                             # 해당 노드가 몇 번째에 있는지
        ptr = self.head.next                # 현재 스캔중인 노드에 head.next 대입
        while ptr is not self.head:         # 현재 스캔중인 노드가 더미가 아니라면 (리스트가 비어있다면 head.next도 head일 것)
            if data == ptr.data:                # 데이터가 찾으려는 데이터와 일치
                self.current = ptr                  # 주목노드를 ptr로
                return cnt                          # 카운트 리턴
            cnt += 1                            # 데이터가 일치하지않았으므로 카운트 +1
            ptr += ptr.next                     # 주목 노드를 다음으로 이동
        return -1

    def __contains__(self, data):
        '''연결리스트에 data가 포함되어 있는지 판단'''
        return self.search(data) >= 0

    def print_current_print(self):
        '''주목 노드 출력'''
        if self.is_empty():
            print('주목노드가 없습니다. ^^')
        else:
            print(self.current.data)

    def prnit(self):
        '''전체 노드 출력'''
        ptr = self.head.next
        if self.is_empty():
            print('노드가 없습니다. ^^')
        else:
            while ptr is not self.head:
                print(ptr.data)
                ptr = ptr.prev

    def next(self):
        '''주목노드를 한 칸 뒤로 이동'''
        if self.is_empty() or self.current.next is self.head:   # 만약 리스트가 비어있거나 노드가 1개밖에없다면
            return False
        self.current = self.current.next
        return True

    def prev(self):
        '''주목노드를 한 칸 앞으로 이동'''
        if self.is_empty() or self.current.next is self.head:  # 만약 리스트가 비어있다면 혹은 한 개밖에 없다면
            return False
        self.current = self.current.prev
        return True

    def add(self, data):
        '''주목노드 바로 뒤에 노드 (데이터) 추가'''
        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):
        '''맨 앞에 노드 삽입'''
        self.current = self.head        # current를 head로 이동
        self.add(data)                  # 더미인 head 뒤에 (실질적으로 데이터의 첫 번째째)데이터 삽입

    def add_last(self, data):
        '''맨 뒤에 노드 삽입'''
        self.current = self.head.prev()
        self.add(data)

    def remove_current_node(self):
        '''노드 삭제'''
        if not self.is_empty():
            self.current.next.prev = self.current.prev
            self.current.prev.next = self.current.next
            self.current = self.current.prev
            self.no -= 1
            if self.current is self.head:
                self.current = self.head.next

    def remove(self, p):
        '''노드 p 삭제'''
        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):
        '''머리노드 삭제'''
        self.current = self.head.next
        self.remove_current_node()

    def remove_last(self):
        '''꼬리 노드 삭제'''
        self.current = self.head.prev
        self.remove_current_node()

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

코드의 특징으로는 prev 라는 앞으로 이동할 수 있는 방법이 있으므로 가장 끝 노드를 찾는 방법이나 검색 등 여러 상황에서 유용하게 사용할 수 있다.