[자료구조] Doubly Linked List

주요 연산

• 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