Python으로 구현하는 Linked List (3) 양방향 Linked List

https://uding.tistory.com/106?category=995002 

Python으로 구현하는 Linked List (2) 단방향 Linked List

 

이전의 단방향 연결 리스트를 개선한 양방향 연결 리스트를 구현해보자.

양방향 연결 리스트는 말 그대로 앞으로 or 뒤로 이동할 수 있다.

 

개선된 노드는 아래 그림과 같이 prev & next 링크를 가지고 있는 형태이다.

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

 

양방향 연결 리스트의 맨 앞과 맨 뒤에 각각 head 그리고 tail 이름의 dummy node를 두어 좀 더 일반적인 형태를 갖도록 만든다.

 

기본적인 모습의 양방향 자료구조

head & tail의 prev & next를 모두 조정해 주어야 한다.

class DublyLinkedList:
    def __init__(self, item):
        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

 

아래는 순회 및 역순회 메소드이다.

순회는 리스트의 head에서 tail로 향하는 것이고 역순회는 tail에서 head로 향하는 것이다.

순회의 경우 빈 리스트이면 head.next.next가 None이 되버리고 역순회의 경우 빈 리스트이면 tail.prev.prev가 None이 되버려 []를 반납한다.

    # 순회 메소드    
    def traverse(self):
        
        result = []
        
        curr = self.head
        
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
            
        return result
    
    # 역 순회 메소드
    def reverse(self):
        
        result = []
        
        curr = self.tail
        
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
            
        return result

 

양방향 연결 리스트에서 prev 다음에 newNode를 삽입하는 insertAfter를 알아보자.

next는 prev.next로 정보를 얻을 수 있다.

 

newNode를 중심으로 양쪽 기존의 prev 노드와 next 노드의 링크를 다음과 같이 조정한다.

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

 

pos 위치의 원소를 얻어내는 getAt 메소드는 다음과 같다.

pos가 범위를 벗어나는 경우 None을 반환한다.

그리고 pos가 head 보다 tail 쪽에 더 가까운 경우 tail에서부터 pos 원소를 찾도록 한다.

    def getAt(self, pos):
        
        # 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
            
        return curr

 

pos를 지정해 newNode를 삽입하는 inserAt 메소드는 다음과 같다.

    def insertAt(self, pos, newNode):
        # pos가 범위를 벗어나는 경우
        if pos<1 or pos>self.nodeCount:
            return False
        
        prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)

 

next 노드 전에 newNode를 삽입하는 insertBefore 메소드는 다음과 같다.

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

 

다음은 insert 메소드들과 유사한 pop 관련 메소드이다.

    def popAfter(self, prev):
        # prev - curr(prev.next) - curr.next
        # prev - curr.next
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        return curr.data
    
    def popBefore(self, next):
        # curr.prev - curr(next.prev) - next
        # curr.prev - next
        curr = next.prev
        next.prev = curr.prev
        curr.prev.next = next
        self.nodeCount -= 1
        return curr.data
    
    def popAt(self, pos):
        
        if pos<1 or pos>self.nodeCount:
            return False
        
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

 

다음은 두 연결 리스트를 연결하는 concat 메소드이다.

    def concat(self, L):
        # L1: head - node - node - tail
        # L2: head - node - node - tail
        # => L1: head - node - node
        # => L2: node - node - tail
        L1_last = self.tail.prev
        L2_first = L.head.next
        
        L1_last.next = L2_first
        L2_first.prev = L1_last
        
        self.tail = L.tail
        
        self.nodeCount += L.nodeCount