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

지금까지 연결 리스트에서는 링크가 한 방향으로, 다시 말하자면 먼저 오는 데이터 원소를 담은 노드로부터 그 뒤에 오는 데이터 원소를 담은 노드를 향하는 방향으로만 연결되어 있었다. 양방향 연결 리스트는 노드들이 앞/뒤로 연결되어있다. 앞(다음 node)으로도 뒤(이전 node)로도 진행이 가능하다.

 

 

 

 

 

Node의 구조확장

# Node 클래스
class Node:
    def __init__(self, itme):
        self.date = item
        self.prev = None
        self.next = None

 

 

 

 

양방향 연결 리스트 구조

리스트의 처음과 끝에 dummy node를 둔다. 이렇게 하면 뭐가 좋은가? 데이터를 담고있는 node들이 모두 같은 모양이 된다. 코드를 작성하는데 있어 상당히 편안해지게 된다.

 

# 양방향 연결 리스트 클래스
class DoublyLinkedList:
    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

 

 

 

 

리스트 순회

while문 안에서 현재 노드의 다음다음이 유효할 때 까지 반복한다. 리스트가 비어있는 경우에서도 유효한 코드가 된다.

# 리스트 순회
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

 

 

 

 

원소의 삽입 insertAfter()

처음 상태

새로운 노드의 링크조절

앞 노드의 링크 조절

뒷 노드의 링크 조절

노드개수 조절

 

 

 

원소의 삽입 코드 구현

    # 원소의 삽입
    def insertAfter(self, prev, newNode):
        next = prev.next
        nextNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

 

 

 

 

 

특정 원소 얻어내기 getAt()

특정 원소 얻어내는것은 단순 연결 리스트와 동일하다. 

    # 특정 원소 얻어내기
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
    
   	    i = 0
        curr = self.head
        
        while i < pos:
       	    curr = curr.next
            i += 1
    
   	    return curr

 

 

 

 

 

원소의 삽입 insertAt()

    # 원소의 삽입
    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)

리스트 마지막에 원소를 삽입하려면 getAt을 수정해서 구현한다.

 

 

 

 

getAt() 코드의 개선

    # 특정 원소 얻어내기
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        
        # pos가 오른쪽으로 치우쳐있는 경우 tail쪽에서 계산
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail

            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        
        # pos가 왼쪽으로 치우쳐 있는 경우 head에서 계산
        else:
            i = 0
            curr = self.head
            
            while i < pos:
       	        curr = curr.next
                i += 1

        return curr

특정 원소의 위치가 왼쪽으로 치우쳐있으면 head로 부터, 오른쪽으로 치우쳐있다면 tail로 부터 탐색하여 삽입을 할 수 있도록 코드를 개선을 해주어서 조금 더 효율적이게 만들었다. 하지만 여전히 리스트가 길어지면 길어질수록 시간이 오래걸리는 선형 탐색 알고리즘이다.

 

 

 

원소의 삭제

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