[자료구조] Doubly Linked List

Aug 17, 2023

Contents

주요 연산

💡

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

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

시간복잡도

ㅤ	복잡도
삽입	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

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 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