[python] 자료구조 - 더블 링크드 리스트(Doubly Linked List)

더블 링크드 리스트(Doubly Linked List)

 

출처: https://en.wikipedia.org/wiki/Doubly_linked_list

 

더블 링크드 리스트는 포인터가 다음 주소 뿐만 아니라 이전 주소도 갖는다.

 

링크드 리스트 구조에서 이전 주소값을 저장할 멤버를 추가로 만들어주면 된다.

 

 

 

class Node:
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.prev = prev
        self.next = next

class DLinkedList:
    def __init__(self):
        self.head = None
    
    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            
            while node.next:
                node = node.next
                
            temp = Node(data)
            node.next = temp
            temp.prev = node
    
    def descend(self):
        node = self.head
        
        while node:
            print(node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == None:
            return False
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            self.head.prev = None
            del temp
        
        else:
            node = self.head

            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    
                    if node.next == None:
                        pass
                    else:
                        node.next.prev = node
                    
                    del temp
                
                else:
                    node = node.next


#Test Code
dLinked_list = DLinkedList()

for a in range(1, 10):
    dLinked_list.insert(a)

dLinked_list.descend()

dLinked_list.delete(1)
dLinked_list.delete(9)
dLinked_list.delete(8)
dLinked_list.delete(101)


print()
dLinked_list.descend()

print(dLinked_list.head.next.prev.data)