이중 연결 리스트 구조

---

• (데이터 값, 다음 노드 주소)로 구성되어 있던 연결리스트와 다르게
  (이전 노드 주소, 데이터 값, 다음 노드 주소)로 구성되어 있어 양방향 탐색이 가능하다.

이중 연결 리스트 장단점

---

• 장점
  • 연속적인 탐색과 액세스가 이루어져야 하는 경우 탐색 시간이 절감된다.
• 단점
  • 이전 노드를 지정해줘야 하므로 변수를 추가해줘야 하기 때문에 메모리를 더 많이 사용한다.
  • 구현이 복잡하다.

이중 연결 리스트 구현

---

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


class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head  # 이중연결리스트의 맨 마지막 노드를 가리키는 변수이다.

    # 이중연결리스트 맨 마지막에 노드를 추가하는 함수
    def addLastNode(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        if self.head.next == None:
            new_node = Node(data)
            self.head.next = new_node
            self.tail = new_node
        else:
            node = self.tail
            new_node = Node(data)
            node.next = new_node
            new_node.prev = node
            self.tail = new_node

    # 이중연결리스트 중간에 노드를 추가하는 함수(head쪽에서 찾아서 추가)
    def addNodeInsideFromHead(self, data, pre_node_data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head

        new_node = Node(data)
        pre_node = self.findNodeFromHead(pre_node_data)

        if pre_node == None:
            return print("해당 값을 가진노드가 존재하지 않습니다.")
        elif pre_node.next == None: # 이전 노드가 맨 뒤일 경우
            pre_node.next = new_node
            new_node.prev = pre_node
            self.tail = new_node
        else:
            node = pre_node.next
            pre_node.next = new_node
            node.prev = new_node
            new_node.prev = pre_node
            new_node.next = node

    # 이중연결리스트 중간에 노드를 추가하는 함수(tail쪽에서 찾아서 추가)
    def addNodeInsideFromTail(self, data, pre_node_data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head

        new_node = Node(data)
        pre_node = self.findNodeFromTail(pre_node_data)

        if pre_node == None:
            return print("해당 값을 가진노드가 존재하지 않습니다.")
        elif pre_node.prev == None: # 이전 노드가 맨 앞일 경우
            pre_node.prev = new_node
            new_node.next = pre_node
            self.head = new_node
        else:
            node = pre_node.prev
            pre_node.prev = new_node
            node.next = new_node
            new_node.next = pre_node
            new_node.prev = node

    # 이중연결리스트의 노드를 삭제하는 함수(head 쪽에서 찾아서 삭제)
    def deleteNodeFromHead(self, data):
        if self.head == None:
            return print("리스트가 비어있습니다.")
        if self.head.data == data: # 삭제할 노드가 맨 앞에 있을 경우
            temp = self.head
            if self.tail == self.head: # 이중연결리스트의 노드가 1개일 경우
                self.tail = None
            self.head = self.head.next
            self.head.prev = None
            del temp
        elif self.tail.data == data: # 삭제할 노드가 맨 뒤에 있을 경우
            temp = self.tail
            if self.head == self.tail: # 이중연결리스트의 노드가 1개일 경우
                self.head = None
            self.tail = self.tail.prev
            self.tail.next = None
            del temp
        else:
            delete_node = self.findNodeFromHead(data)
            delete_node.prev.next = delete_node.next
            delete_node.next.prev = delete_node.prev
            del delete_node
    
    # 이중연결리스트의 노드를 삭제하는 함수(tail 쪽에서 찾아서 삭제)
    def deleteNodeFromTail(self, data):
        if self.head == None:
            return print("리스트가 비어있습니다.")
        if self.head.data == data: # 삭제할 노드가 맨 앞에 있을 경우
            temp = self.head
            if self.tail == self.head: # 이중연결리스트의 노드가 1개일 경우
                self.tail = None
            self.head = self.head.next
            self.head.prev = None
            del temp
        elif self.tail.data == data: # 삭제할 노드가 맨 뒤에 있을 경우
            temp = self.tail
            if self.head == self.tail: # 이중연결리스트의 노드가 1개일 경우
                self.head = None
            self.tail = self.tail.prev
            self.tail.next = None
            del temp
        else:
            delete_node = self.findNodeFromTail(data)
            delete_node.prev.next = delete_node.next
            delete_node.next.prev = delete_node.prev
            del delete_node

    # head쪽에서 부터 노드를 찾는 함수
    def findNodeFromHead(self, data):
        if self.head == None:
            return None
        if self.head.data == data:
            return self.head
        else:
            node = self.head
            while node:
                if node.data == data:
                    return node
                else:
                    node = node.next
            return None

    # tail쪽에서 부터 노드를 찾는 함수
    def findNodeFromTail(self, data):
        if self.head == None:
            return None
        if self.tail.data == data:
            return self.tail
        else:
            node = self.tail
            while node:
                if node.data == data:
                    return node
                else:
                    node = node.prev
            return None

    # 이중연결리스트를 순회하며 값을 출력하는 함수
    def printAll(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next