양방향 연결 리스트 구현

https://www.youtube.com/watch?v=zWrFVf9_YTQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=16 

교수님 자료를 보고 리뷰한 포스팅

단방향 연결 리스트의 단점

- 만약 tail 노드를 지우고 싶다고 했을 때, tail 노드를 안다고 하더라도 tail 노드 앞의 prev 노드를 알지 못하기 때문에

결국 head부터 끝까지 search 하며 찾아야 한다. O( n ) 시간 소요

- 이를 해결하기 위해 왼쪽 방향 오른쪽 방향의 양방향 연결 리스트가 필요하게 됨.

- 단점 : 링크가 양쪽으로 있어서 복잡성이 증가함

 

Splice 연산

def splice(self, a, b, x) :

조건 1 : a ->.. -> b : a에서 앞으로 가다 보면 b가 나옴

조건 2 : a와 b 사이에 head X

목적 : a와 b 사이 만큼을 컷 해서 x 뒤에다가 붙임

 

class Node:
    def __init__(self, key=None):
        self.key = key
        self.next = self
        self.prev = self
    def __str__(self):
        return self.key

class DoublyLinkedList:
    def __init__(self):
        self.head = Node()
        self.size = 0
    def __iter__(self):
        v = self.head
        while v != None:
            yield v
            v = v.next
        return None
    def __len__(self):
        return self.size
    
    def splice(self, a, b, x):
        # 6개의 링크 수정 O(1)
        # a와 b 사이 만큼을 컷해서 x 뒤에다가 붙이는 연산
        ap = a.prev
        bn = b.next
        xn = x.next

        # cut
        ap.next = bn
        bn.prev = ap

        x.next = a
        a.prev = x
        b.next = xn
        xn.prev = b

    def moveAfter(self,a,x):
        # Splice 사용 O(1)
        self.splice(a,a,x)

    def moveBefore(self,a,x):
        # Splice 사용 O(1)
        self.splice(a,a,x.prev)

    def insertAfter(self,x,key):
        # Splice 사용 O(1)
        # x 다음에 key를 가진 노드 삽입
        self.moveAfter(Node(key),x)

    def insertBefore(self,x,key):
        # Splice 사용 O(1)
        # x 전에 key를 가진 노드 삽입
        self.moveBefore(Node(key),x)
    
    def pushFront(self,key):
        # Splice 사용 O(1)
        self.insertAfter(self.head,key)

    def pushBack(self,key):
        # Splice 사용 O(1)
        self.insertBefore(self.head,key)
    
    def search(self,key):
        # O(n)
        v = self.head
        while v.next != self.head:
            if v.key == key:
                return v
            v = v.next
        return None
    
    def remove(self,x): # 노드 x 를 삭제
        # 2개의 링크 수정 O(1)
        if x == None or x == self.head:
            return False
        x.prev.next = x.next
        x.next.prev = x.prev
        del x
        return True
    
    def remove_key(self,key): # key를 가지고 있는 노드를 삭제
        # search를 사용하므로 O(n)
        x = self.search(key)
        if x:
            self.remove(x)
        else:
            print('해당하는 key를 가진 노드가 없음')
            return

    def popFront(self):
        # head(헤드는 더미노드) 오른쪽 노드 pop
        key = self.head.next.key
        if self.remove(self.head.next):
            return key
        return
    
    def popBack(self):
        # head(헤드는 더미노드) 왼쪽 노드 pop
        key = self.head.prev.key
        if self.remove(self.head.prev):
            return key
        return

    def join(self,a,b):
        # 두 연결리스트를 하나로 합침
        a.head.prev.next = b.head.next
        b.head.next.prev = a.head.prev
        b.head.prev.next = a.head
        a.size += len(b)
        del b
        return a

    def split(self,x):
        # 두 연결리스트로 쪼갬, x라는 key 기준
        pass