양방향 연결 리스트

링크를 두 개 가진 연결 리스트

링크를 두 개 가진 연결 리스트

앞으로도(다음 노드) 뒤로도(이전 노드) 진행 가능

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

head의 next, tail의 prev를 서로 연결시킴으로써 리스트를 순회할 때 앞 뒤로 이동할 수 있어 리스트 역순회도 가능해졌다.

리스트 순회

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

특정 노드 뒤에 삽입

def insertAfter(self, prev, newNode):
    next = self.next
    newNode.prev = prev
    newNode.next = next
    prev.next = newNode
    next.prev = newNode

    self.nodeCount += 1
    return True

k 번째 원소 얻기