학습용 공간

import sys


class SList:
    """Singly linked list implementation only with head."""
    class _Node:
        def __init__(self, element, next=None):
            self._element = element
            self._next = next

        def element(self):
            return self._element

        def next(self):
            return self._next

        def set_element(self, element):
            self._element = element

        def set_next(self, next):
            self._next = next

    def __init__(self, head=None): # SList 객체 생성하면, 노드 생성하기 전에 기본적으로 Head 먼저 생성됨
        """Create a singly linked list that contains only head, not size"""
        self._head = head

    def __len__(self):
        """len(SList) returns the number of elements in SList"""
        length = 0
        node = self._head # head노드부터 link hopping으로 노드 counting 시작
        while node: # 노드가 없을 때까지 hopping하면서 counting
            length += 1
            node = node.next()
        return length

    def __str__(self):
        """Returns the string representation and the number of elements"""
        count = 0
        p = self._head # p노드를 head 노드로 지정
        rep = f''
        while p: 
            rep += str(p.element()) + ' -> '
            p = p.next()
            count += 1
        rep += f'None: {count} element(s)'
        return rep

    def is_empty(self):
        return self._head is None # is 연산자는 "==" 연산자와 비슷 (== 성립 - true반환 / == 성립하지않음- false반환)
                                # head는 첫번째 노드이기 때문에 head가 비면 리스트 전체에 노드가 없는 것
                                # head가 비었으면 return true / 비지 않았으면 return false

    def head(self):
        return self._head

    def search(self, element):
        """Search an element in self by link hopping through next"""
        p = self._head # 탐색 시작점을 head(첫 노드)로 정하고 link hopping을 하면서 순서대로 탐색
        while p:
            if p.element() == element:
                return p  # found returns its position
            p = p.next()
        return None  # not found

    def insert_first(self, element):
        """Insert the node of element in front of head"""
        self._head = self._Node(element, self._head) # element를 갖고 next 주소로 head를 가리키는 새로운 노드를 생성
                                                    # 기존의 head 노드 앞에 노드가 생성하여 새로운 head가 됨

    def delete_first(self):
        """Delete the head node and return its element"""
        if self.is_empty():
            return None
        element = self._head.element()
        self._head = self._head.next() # 원래의 head 자리에 head 다음 순서의 노드의 정보를 덮어씌움
        return element      # 다음 노드를 가리키는 next 노드가 함께 head로 옮겨지기 때문에 뒤의 노드들과 상관없이 앞 노드 삭제 가능.

    # 과제 항목 1
    def insert_after(self, element, p):
        """Insert a node of element after p"""
        if p == None: # 지정한 노드가 없으면 실행하지않음
            print("해당 노드는 리스트에 없습니다.")
            return
        p.set_next(self._Node(element, p.next())) # p노드의 다음 노드 주소를 가리키는 element를 갖는 노드를 생성하고
                                                # p노드가 가리키는 주소를 생성한 노드의 주소로 바꾸어준다.

    # 과제 항목 2
    def delete_after(self, p):
        """Delete the node after p and return its element"""
        if p == None: # 지정한 노드가 없으면 실행하지 않음
            print("해당 노드는 리스트에 없습니다.")
            return None
        if p.next() is None: # 지우려고 하는 p노드 다음 노드가 존재하지 않을때 
            print("해당 노드 다음 순서의 노드가 존재하지 않습니다.")
            return None
        element = p.next().element() # 지우려는 노드의 element 값 저장
        t = p.next()
        p.set_next(t.next()) # 지우려는 노드의 다음 노드 주소를  p 노드가 가리키게 함
        return element
        

    # 과제 항목 3
    def insert_last(self, element):
        """Insert the node of element at tail"""
        if self.is_empty(): # 리스트가 비어있을 경우 노드 맨 앞에 노드를 생성하는 함수를 호출 -> 새로운 head 생성
            self.insert_first(element)
        else:
            tail = self._head # tail를 head로 지정하고 하나씩 link hopping 하며, 다음 노드가 없는 진짜 tail을 찾으면 while문 탈출
            while tail.next():
                tail = tail.next()
            self.insert_after(element, tail) # tail 다음에 새로운 노드 생성 -> 새로운 tail 노드

    # 과제 항목 4
    def delete_last(self):
        """Delete the tail node"""
        if self.is_empty():
            print("해당 리스트는 이미 비어 있습니다.")
        tail = self._head
        while tail.next():
            tail = tail.next()
        if tail is self._head: # 리스트가 1개의 노드로만 이루어져 있을때 (head = tail 일때)
            return self.delete_first() # 첫 노드 (head) 삭제
        p = self._head 
        while p.next() is not tail: # p에 tail 이전 순서의 노드 주소 값을 저장
            p = p.next()
        return self.delete_after(p) # p 다음 순서의 노드 삭제 (tail 삭제)

    # 과제 항목 5
    def reverse_recursively(self, current):
        """Recursively reverse the order of nodes from current to the end in self.
        Split the current node and its successors (remainders).
        Recursively reverse the successors and make its tail pointing current node.
        Make current node to point None."""
        if self.is_empty():
            print("해당 리스트는 비어 있습니다.")
            return
        if current is None:
            print("해당 노드는 리스트에 존재하지 않습니다.")
            return
        if current.next() is None: # base case는 current 노드가 리스트의 tail에 다다랐을 경우
            self._head = current # base case에 다다른 cuurent 노드는 tail 노드이다. reverse하면 tail이 head가 된다.
            return
        successor = current.next() 
        self.reverse_recursively(successor) # current 매개변수로 current.next() 값을 넣어서 Recursive 처리
        successor.set_next(current) # current.next() 노드가 current 노드를 가리키게 만듬
        current.set_next(None) # current 노드가 가리키는 주소가 없게 만듬

    def reverse_iteratively(self, current):
        """Iteratively reverse the order of nodes from current to the end in self."""
        predecessor = None
        while current:
            successor = current.next() 
            current.set_next(predecessor) # 반복문의 첫 실행에서는 (reverse를 시작하는 노드가) None을 가리키게 한다.(tail 노드로 만듬)
            predecessor = current         # 그 후로는 current 노드가 이전 노드를 가리키게 한다.
            current = successor # 다음 반복에서 같은 작업을 하기 위해 current에 다음 노드를 저장하고 원래의 cuurent를 pre로 옮간다.
        self._head = predecessor # 반복문이 끝나고 predecessor가 reverse의 첫 노드가 되어 head로 저장한다.

    # 과제 항목 6
    # 연습문제 2.12
    def find_middle(self):
        """단순연결리스트의 전체 노드들을 한번씩만 방문하는 시간에 연결리스트의 중간 노드를 찾아 반환하는 메써드를 작성하시오.
        ex1) 1->2->3->4->5->None: 5 element(s) 인 경우는 3을 가진 노드를 반환하야 함.
        ex2) 1->2->3->4->5->6->None: 6 element(s) 인 경우는 4을 가진 노드를 반환해야 함."""
        if self.is_empty():
            print("해당 리스트는 비어있습니다.")
            return None
        p = self._head # 1개씩 link hopping
        q = self._head # 2개씩 link hopping  -> two pass 사용
        while p and p.next(): # p의 다음이나 p가 가리키는 노드가 없을때까지 link hopping
            p = p.next().next()
            q = q.next()
        return q # 2개씩 lnk hopping한 포인터가 마지막 노드를 가리킬때 1개씩 link hopping한 포인터는 해당 리스트의 중간 노드를 가리킴
    
# 과제 항목 7
# 연습문제 2.7
def merge_list(s1, s2):
    """각각 정렬되어 있는 2개의 단일연결리스트 s1, s2를 하나의 정렬된 단일연결리스트로 만들어서 반환하는 함수를 작성하시오.
    각 노드에는 한개의 정수가 저장되어 있다.
    예) s1: 1->3->5->7->9->None: 5 element(s),
        s2: 0->2->4->6->8->None: 5 element(s) 인 경우에 s3 = merge_list(s1, s2)에 의하여 반환하는 새로운 단일연결리스트는
        s3: 0->1->2->3->4->5->6->7->8->9->None: 10 element(s) 와 같아야 함."""
    s3 = SList()
    if s1.is_empty(): # s1 리스트에 노드가 없을 경우 s2의 노드들로 s3를 구성하여 반환
        temp = s2._head
        while temp:
            s3.insert_last(temp.element())
            temp = temp.next()
        return s3
    if s2.is_empty(): # s2 리스트에 노드가 없을 경우 s1의 노드들로 s3를 구성하여 반환
        temp = s1._head
        while temp:
            s3.insert_last(temp.element())
            temp = temp.next()
        return s3
    p = s2._head # s2의 노드들 link hopping 할 변수
    q = s1._head # s1의 노드들 link hopping 할 변수
    while q: # 먼저 s1 리스트에 있는 노드의 element들이 모두 insert될때까지 수행
        if p: # s2의 element가 남아있는 동안, s1의 element와 비교연산하며 더 작은 값을 insert
            if q.element() <= p.element():
                s3.insert_last(q.element())
                q = q.next()
            else :
                s3.insert_last(p.element())
                p = p.next()
        else: # s2의 element들이 모두 insert 되었는데 s1에 element들이 남아있는 경우
            s3.insert_last(q.element())
            q = q.next()
    while p: # s1의 element들이 모두 insert 되었는데 s2의 element들이 남아있는 경우 (p가 아직 남아있을때 위의 "while q"를 탈출하게 됨)
        s3.insert_last(p.element())
        p = p.next()
    return s3
    
# s2부터 노드를 교차로 넣는 방법 (잘못된 방법)
#     s3 = SList()
#     if s1.is_empty(): # s1 리스트에 노드가 없을 경우 s2의 노드들로 s3를 구성하여 반환
#         temp = s2._head
#         while temp:
#             s3.insert_last(temp.element())
#             temp = temp.next()
#         return s3
#     if s2.is_empty(): # s2 리스트에 노드가 없을 경우 s1의 노드들로 s3를 구성하여 반환
#         temp = s1._head
#         while temp:
#             s3.insert_last(temp.element())
#             temp = temp.next()
#         return s3
#     temp = s2._head # s3 리스트에 s2 리스트의 노드들을 먼저 넣어준다.
#     while temp:
#         s3.insert_last(temp.element())
#         temp = temp.next()
#     p = s3._head
#     q = s1._head
#     while q: # s3에 들어간 s2 리스트의 각 노드들 다음 순서에 s1 리스트의 노드들을 하나씩 넣어주어 s3 생성
#         if p: # s1 리스트에 있는 노드들이 모두 insert 될 때까지 수행 
#             s3.insert_after(q.element(), p)
#             p = p.next().next()
#             q = q.next()
#         else: # 만약 s1 리스트의 노드들의 개수가 더 많으면 s2 리스트의 마지막 노드 뒤에 남은 s1 리스트의 노드들을 순차적으로 insert
#             s3.insert_last(q.element())
#             q = q.next()
#     return s3
    


class DList:
    """Doubly linked list implementation with dummy header and trailer."""
    class _Node:
        def __init__(self, element, prev, next):
            self._element = element
            self._prev = prev
            self._next = next

        def element(self):
            return self._element

        def next(self):
            return self._next

        def prev(self):
            return self._prev

        def set_element(self, element):
            self._element = element

        def set_next(self, next):
            self._next = next

        def set_prev(self, prev):
            self._prev = prev

    def __init__(self):
        self._header = self._Node(None, None, None) # dummy header 생성
        self._trailer = self._Node(None, None, None) # dummy trailer 생성
        self._header._next = self._trailer
        self._trailer._prev = self._header

    # 과제 항목 8
    def size(self, current):
        """Recursive count the number of nodes from current node to the end (just in front of trailer)."""
        if self.is_empty(): # 리스트가 비어있으면 노드의 개수는 0
            return 0
        if current is None:
            print("해당 노드는 리스트에 존재하지 않습니다.")
            return 0
        if current.next() is self._trailer: # base case는 current 노드의 순서가 trailer 바로 전일 경우
            return 1
        count = 1 # is_empty() 를 통과했기 때문에 적어도 1개의 노드에서 시작
        count += self.size(current.next()) # current가 base case에 다다를때 까지 recusrsion, recuresion 1회당 count + 1
        return count                       # current가 뒤에서 n번째 노드면 (n-1)번 recursion해야 base case(tail 노드)에 도달

    def __len__(self):
        return self.size(self.header().next()) # header의 다음 노드를 매개변수로 size함수를 실행하면 리스트의 전체 노드 개수가 반환됨

    def __str__(self):
        """Returns the string representation and the number of elements"""
        count = 0
        p = self.header().next()
        rep = f'Header <-> '
        while p is not self.trailer():
            rep += str(p.element()) + ' <-> '
            p = p.next()
            count += 1
        rep += f'Trailer: {count} element(s)'
        return rep

    def is_empty(self):
        return self.header().next() == self.trailer() # header 노드 바로 다음 순서가 trailer면 유의미한 데이터를 지닌 노드가 없는 것

    def header(self):
        return self._header

    def trailer(self):
        return self._trailer

    def search(self, element):
        """Search a node containing element in self."""
        p = self.header().next() # 더미 노드 header 다음 노드부터 차례로 검색
        while p is not self.trailer(): # p가 trailer 노드에 다다를 때까지 link hopping 하며 같은 element를 지닌 노드가 있는지 탐색
            if p.element() == element:
                return p
            p = p.next()
        return None

    def insert_between(self, element, predecessor, successor):
        """Add an element between predecessor and successor, and return a new node"""
        new_node = self._Node(element, predecessor, successor) # 앞, 뒤 노드가 서로 양방향으로 연결되어 있기 때문에 constant time으로
        predecessor.set_next(new_node)                         # 수행이 가능함
        successor.set_prev(new_node) # 각 노드 사이에 새로운 노드를 삽입하고 양방향으로 주소를 가리키도록 연결시킴
        return new_node

    def insert_after(self, element, p):
        if p is self._trailer: # trailer 노드가 가장 뒷 순서에 있어야하기 때문에 insert하지 않음
            return None
        else:
            return self.insert_between(element, p, p.next()) 

    def insert_before(self, element, p):
        if p is self._header: # header 노드가 가장 앞 순서에 있어야하기 때문에 insert하지 않음
            return None
        else:
            return self.insert_between(element, p.prev(), p)

    def insert_first(self, element):
        return self.insert_after(element, self._header) # header 뒤에 insert

    def insert_last(self, element):
        return self.insert_before(element, self._trailer) # trailer 앞에 insert

    def delete_node(self, node):
        """Delete non-sentinel node and return its element"""
        if (node is self._header) or (node is self._trailer):
            return None

        predecessor = node.prev() 
        successor = node.next()
        predecessor.set_next(successor) # 삭제할 노드의 앞 뒤 노드를 서로 양방향으로 연결시켜준다
        successor.set_prev(predecessor)
        element = node.element() # 삭제할 노드의 element 
        node._prev = node._next = node._element = None # 삭제할 노드와 앞 뒤 노드와의 연결를 끊어버림 -> 노드 삭제됨(행방불명)
        return element