이중 연결 리스트 구현

# 객체지향 프로그래밍으로 이중 연결 리스트 구현

# set up
class DoubleNode:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

class DoubleNodeList:
    def __init__(self, data):
        self.head = DoubleNode(data)
        self.tail = self.head
        
    def add(self, data):
        if self.head == None:
            self.head = DoubleNode(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next      
            new = DoubleNode(data)
            node.next = new
            new.prev = node
            self.tail = new

    def showAll(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == None:
            print("현재 노드가 없습니다")
            return
        if self.head.data == data:
            temp = self.head
            self.head = temp.next
            del temp
        else:
            node = self.head                   
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node_new_next = node.next.next
                    node.next = node_new_next
                    if node_new_next != None:
                        node_new_next.prev = node
                    else:
                        self.tail = node
                    del temp
                    return
                else:
                    node = node.next
    
    def search_from_head(self, data):
        if self.head == None:
            return False
        
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data):
        if self.head == None:
            return False
        
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False
    
    def insert_before(self, old_data, new_data):
        if self.head == None:
            self.head = DoubleNode(new_data)
            return True
        else:
            node = self.tail
            while node.data != old_data:
                node = node.prev
                if node == None:
                    return False
            new = DoubleNode(new_data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True
        
    def insert_after(self, old_data, new_data):
        if self.head == None:
            self.head = DoubleNode(new_data)
            return True
        else:
            node = self.head
            while node.data != old_data:
                node = node.next
                if node == None:
                    return False
            new = DoubleNode(new_data)
            new.prev = node
            new.next = node.next
            node.next = new
            node.next.prev = new
            return True
    
# 실행
double_linkedlist = DoubleNodeList(1)
double_linkedlist.add(2)
double_linkedlist.add(3)
double_linkedlist.showAll() # 1, 2, 3

double_linkedlist.delete(2) # 2 삭제
double_linkedlist.showAll() # 1, 3

# search_from_head() test
node_from_head = double_linkedlist.search_from_head(3)
print(node_from_head.data) # 3

invalid_node = double_linkedlist.search_from_head(4)
print(invalid_node) # False

# search_from_tail() test
node_from_tail = double_linkedlist.search_from_tail(1)
print(node_from_tail.data) # 1

invalid_node = double_linkedlist.search_from_tail(4)
print(invalid_node) # False

# insert_before() test
double_linkedlist.showAll() # 1, 3
double_linkedlist.insert_before(3, 2)
double_linkedlist.showAll() # 1, 2, 3

# insert_after() test
double_linkedlist.showAll() # 1, 2, 3
double_linkedlist.insert_after(3, 4)
double_linkedlist.showAll() # 1, 2, 3, 4