[Python] 더블 링크드 리스트 구현하기

💡 링크드 리스트의 탐색 기능을 개선한 자료구조

링크드 리스트는 헤더에서 테일 방향으로만 탐색이 가능하지만, 더블 링크드 리스트에서는 양방향으로 탐색이 가능하다.

시간복잡도

	복잡도
삽입	O(1)
삭제	O(1)
추가	O(1)
탐색	O(N)

---

주요 연산

• CreateNode(노드 생성), DestroyNode(노드 소멸)
• AppendNode 노드 추가
• GetNodeAt 노드 탐색
• RemoveNode 노드 제거
• InsertAfter 노드 삽입

노드생성

링크드 리스트 노드 생성과 비교하면 양방향 노드를 위한 prev 추가됨

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

노드 추가

새로운 테일의 prev 가 기존 테일을 가르키도록 해야한다.

def append(self, newNode):
        if self.head == None:
            self.head = newNode 
        else:
            tail = self.head
            while tail.next != None:
                tail = tail.next
            
            tail.next = newNode
            newNode.prev = tail

노드 탐색

링크드 리스트와 같은 노드 탐색 → 역시 느림

def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index :
            cnt +=1
            node = node.next
        return node

노드 제거

def removeNode(self, removeNode):
        if self.head == removeNode:
            self.head = removeNode.next
            if(self.head != None):
                self.head.prev = None
            
            removeNode.prev = None
            removeNode.next = None
        else:
            temp = removeNode
            if removeNode.prev != None:
                removeNode.prev.next = temp.next

            if removeNode.next != None:
                removeNode.next.prev = temp.prev
            
            removeNode.prev = None
            removeNode.next = None

노드 삽입

노드 삽입

def insertAfter(self, current, newNode):
        newNode.next = current.next
        newNode.prev = current

        if current.next != None:
            current.next.prev = newNode
            current.next = newNode
        # 노드 추가시 마지막 Tail 인 경우 
        # else:
        #     current.next = newNode