[Python 자료구조] 양뱡향 연결 리스트(Doubly Linked Lists)

 

#Node의 구조 확장

#<-[]->
class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

 

 

#Dummy node

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 traverse(self):
        result = []
        curr = self.head
        while curr.next.next: #Dummy Node가 head와 tail에 모두 있음
            curr = curr.next  #빈 리스트라도 순회
            result.append(curr.data)
        return result

 

 

#리스트 역순회

    def revese(self):
        result = []
        curr = self.head
        while curr.prev.prev: #prev > prev
            curr = curr.prev  #빈 리스트라도 반복하지 않고 빠져 나옴> 유효함
            result.append(curr.data)
        return result

 

 

#원소의 삽입

def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = prev.next
        newNode.prev = prev
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        
        return True

#링크만 조정하면 됨
	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 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.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

 

 

#양방향 연결 리스트 노드 삭제

def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        
        return curr.data

    def popBefore(self, next):
        curr = next.prev
        prev = curr.prev
        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

        prev = self.getAt(pos - 1)
        
        return self.popAfter(prev)

 

 

#양방향 연결 리스트의 병합

def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount