Doubly Linked List

 

Class DoublyLinkedList:
	def __init__(self,item):
    	self.nodeCount = 0
        self.head = None
        self.tail = None
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

기존의 Linked List는 다음 노드를 가리키는 Link만 있었다면 양방향(이중 연결) 리스트는 이전 노드를 가리키는

Prev Link도 갖고 있다. 

 

 

Doubly Linked List는 Dummy Node가 head와 tail에 둘 다 있다. 이로 인해 노드의 변경에 작성되는 코드가 간결해진다.

하지만 한 노드에 Data와 두 개의 Link의 값을 가지므로 메모리 사용량은 더 늘어난다.

 

def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
        
def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
        
def popAfter(self, prev):
        result = prev.next
        prev.next = result.next
        result.next.prev = prev
        self.nodeCount -= 1
        
        return result.data

def popBefore(self, next):
        result = next.prev
        next.prev = result.prev
        result.prev.next = next
        self.nodeCount -= 1
        
        return result.data

def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        else:
            prev = self.getAt(pos+1)
            return self.popBefore(prev)

 

데이터를 삽입하거나 삭제할 때 두 개의 link 값을 변경해야 하지만 추후 활용할 수 있는 메서드(popAfter(), popBefore())가 많고, 이에 따라 코드는 더욱 간결해진다. (복잡한 알고리즘에서 유용)

 

 

 

출처 :

https://opentutorials.org/module/1335/8940

Doubly linked list (이중 연결 리스트) - Data Structure (자료구조)

https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.cpp.edu%2F~ftang%2Fcourses%2FCS240%2Flectures%2Fdlist.htm&psig=AOvVaw17FCoh4KJUyNMWh0I6OHBz&ust=1651371995141000&source=images&cd=vfe&ved=0CAwQjRxqFwoTCIDv3JzeuvcCFQAAAAAdAAAAABAD 

리디렉션 알림