양방향 연결 리스트 (Doubly Linked Lists)

앞서 배운 연결리스트의 link를 앞뒤(prev, next)로 구현.
코드 해석의 편의를 위해 dummy node를 head와 tail에 초기화.

1. 일단 구현!

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None
        
        
class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None
        
    def reverse(self):
    	result = []
        curr = self.tail
        while curr.prev.prev:
        	curr = curr.prev
            	result.append(curr.data)
        return result
    # 양방향이라 끝에서부터 거꾸로 순회할 수 있다.
    
    def getAt(self, pos):
        if pos<0 or pos>self.nodeCount:
            return None
        if pos > self.nodeCount//2:
            i = 0
            curr = self.tail
            while i < self.nomdeCount-pos+1:
                curr = curr.prev
                i += 1
        else:
        	i = 0
        	curr = self.head
        	while i<pos:
        		curr = curr.next
        		i += 1
        return curr
    # 양방향이라 끝에서 찾는 게 유리할 때는 끝에서부터 탐색
    
    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.prev = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
        
    def insertAt(self, pos, newNode):
        if pos<1 or pos > self.nodeCount+1:
        	return False
        prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)
        
    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data
    
    def popAt(self, pos):
        if pos<1 or pos>self.nodeCount:
        	raise IndexError
        else:
        	prev = self.getAt(pos-1)
        return self.popAfter(prev)
    # 코드가 엄청 쉬워짐. 이거 배울려고 그렇게 머리 아팠나보다.
    
    def concat(self, L):
        selfLast = self.tail.prev
        LFirst = L.head.next
        selfLast.next = LFirst
        LFirst.prev = selfLast
        self.tail = L.tail
        self.nodeCount += L.nodeCount
        return True

한줄평

dummy node는 천사다(?) 그래도 연결리스트는 어렵다(?)