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

양방향 연결리스트란?

한쪽으로만 링크를 연결하지 말고 양쪽으로 - 앞으로도(다음node) 뒤로도(이전node)진행가능

node의 구조 확장

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

리스트 처음과 끝에 dummy node를 두자
-> 데이터를 담고 있는node들은 모두 같은 모양

L.insertAfter 
next = prev.next
newNode.prev <- prev
newNode.next <- next
next.prev <-newNode


리스트 마지막에 원소 삽입하는 경우는 어떻게?
getAt메서드를 개선하자!
포지션이 nodecount 절반보다 뒷쪽이면 tail기준으로 역방향으로 돌아오면 됨! 

 

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

즉 , 
지금까지는(단방향 연결리스트) tail이 마지막 노드를 가리키고 있다고 해도
앞쪽에서부터 하나하나 했기 때문에 시간이 리스트의 길이에 비례했다.
양방향은 마지막을 먼저가고 앞 노드를 찾아가는 방식이다.

 

- insertAfter메서드

 

  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

 

 

---

양방향 연결리스트 전체 코드

class Node:

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


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


    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)

---

연습문제 1 : 양방향 연결 리스트 역방향 순회

def reverse(self):
        result =[]
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
            
        return result

정방향 순회의 반대로 tail에서 시작해주면 됨

---

연습문제 2 : 양방향 연결 리스트 노드 삽입 

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

inserAfter와 똑같은 알고리즘. prev만 재정의해주면 됨