오늘은 연결 리스트에 이어 양방향 연결 리스트에 대해 포스팅 하겠습니다!

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

연결 리스트의 단점

• 한쪽 방향으로만 이동 가능
• 반대쪽 방향으로는 이동 불가능

양방향 연결 리스트

• 한 쪽으로만 Link를 연결하지 말고, 양쪽으로 연결! (next / prev)
• 앞으로도 (next node) 뒤로도 (prev node) 진행 가능

node 구조 확장

class Node:

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

dummy node 추가

• 리스트 처음과 끝에 dummy node를 두자!(head/tail)
• dummy node를 추가하게 되면, 모든 node들의 모양이 같아진다.
• 이건 매우 편리하게 만들어 준다.

원소의 삽입

(1) next 설정

• next = prev.next

(2) newNode와 연결 설정

• newNode.prev <- prev
• newNode.next <- next

(3) 기존 연결 해제

• prev.next <- newNode
• next.prev <- newNode

(4) nodeCount <- nodeCount + 1

기타 연산

• 특정 원소 얻어내기: 지난 번과 동일
• 원소의 삽입: getAt 활용 -> 리스트 마지막에 원소 삽입하려면 앞에서부터 찾아가서 삽입해야 한다.
  • 코드 개선: 위치가 nodeCount//2보다 크면 tail부터 찾기

구현

lass 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 __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    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

        return curr


    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 insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)