자료구조 | doubly linked list | Linked List

doubly linked list

기존 SLL Singly Linked List는 단방향으로 연결되어있기에 뒷 노드에서 앞으로 탐색하는 것이 불가능하다.

이 문제를 해결하기 위해 doubly linked list가 제안되었다. 

 

DLL는 각 노드가 link를 left link, right link로 두 가지 가지고 있는 리스트를 의미한다. 

연결은 양방향으로 해줌으로써 삭제와 삽입이 용이해진다. 

 

각 노드는 data field, left link, right link로 구성되며

 

DLL은 Binary tree와 같은 구조에서 쓰인다 

 

 

스켈레톤 코드

class Node:
    def __init(self, data):
        pass
    
class DLL:
    def __init__(self):
        pass
    def insert(self, prev, item):
        pass

 

구현

class Node:
    def __init__(self, data):
        self.data = data
        self.rlink = None
        self.llink = None
    
class DLL:
    def __init__(self):
        self.head = None
        self.rear = None
        self.cnt = None
    def insert(self, item):
        tmp = Node(item)
        if self.head == None:
            self.head = tmp
        else:
            right = self.head.rlink
            self.head.rlink = tmp
            tmp.llink = self.head
            tmp.rlink = right
            
            
    def print(self):
        tmp = self.head
        while tmp != None:
            print(tmp.data)
            tmp = tmp.rlink

d = DLL()
d.insert(6)
d.insert(5)
d.insert(4)
d.print()