양방향 연결 리스트

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

한 쪽으로만 링크를 연결하지 않고 양쪽으로 연결한다.
다음 node, 이전 node로도 진행 가능하다. 메모리 공간은 많이 차지하지만 코드 작성이 용이하다.

리스트 처음과 끝에 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

• 리스트 순회

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

while문의 조건 curr.next.next는 빈 리스트를 순회할 때도 유효하다.
head - tail로 구성되어있고 curr인 head의 next.next는 None이기때문에 순환문을 돌지 않고 빠져나온다.

• 리스트 역순회
  curr를 tail로 지정하고 모든 next를 prev로 바꾸면 완성!

• 원소의 삽입
  L.insertAfter(prev, newNode)

 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

• 특정 원소 찾기
  포지션이 현 리스트의 절반보다 뒷쪽이면 curr을 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:
  원래코드와 동일하게 앞에서부터 찾아가는 조건