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

강의

"양방향 연결 리스트"는 앞뒤 모두 진행 가능한 연결 리스트입니다.

기존의 연결 리스트와 다르게 Node의 구조 확장이 필요합니다.

 

 

 

 

 

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

 

 

10강 실습: (1) 양방향 연결 리스트 역방향 순회

⭐ 시작 노드를 tail로 설정하여 순회하는 문제!

def reverse(self):
    rev = []

    curr = self.tail

    while curr.prev.prev:
        curr = curr.prev

        rev.append(curr.data)

    return rev

 

10강 실습: (2) 양방향 연결 리스트 노드 삽입

⭐ head, tail의 앞뒤를 고민하지 않고 바로 삽입하는 문제!

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

 

10강 실습: (3) 양방향 연결 리스트 노드 삭제

def popAfter(self, prev):
    curr = prev.next
    next = curr.next

    prev.next = next
    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

    curr = self.getAt(pos)
    return self.popAfter(curr.prev);

 

10강 실습: (4) 양방향 연결 리스트의 병합

⭐ 필요없는 dummy node를 먼저 제거한 후에 리스트 합치는 문제!

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

    self.tail.next = L.head
    L.head.prev = self.tail

    self.tail = L.tail

    self.nodeCount += L.nodeCount