프로그래머스 강의_10

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

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

Node 의 구조 확장

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

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

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

1. 새로운 노드의 이전노드를 prev노드로 설정
2. 새로운 노드의 다음 노드를 next노드로 설정
   => 기존의 링크를 끊어줄 준비가 됨.
3. 이전 노드의 다음 노드를 새로운 노드로 설정
4. 다음 노드의 이전 노드를 새로운 노드로 설정

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 getAt(self, pos):
   if pos < 0 or pos > self.nodeCount:
       return None
   i = 0
   curr = self.head
   while i < pos:
       curr = curr.next
       i += 1
   return curr

원소의 삽입(L.insertAt(pos, newNode))

def insertAt(self, pos, newNode):
    if pos < 0 or pos > self.nodeCount:
        return False
    prev = self.getAt(pos-1)
    return self.insertAfter(prev,newNode)

잠깐! 리스트 마지막에 원소 삽입하면?

def insertAt(self, pos, newNode):
    if pos < 0 or pos > self.nodeCount:
        return False
    if pos > self.nodeCount//2:
        i = 0
        curr = self.tail
        while i < self.nodeCount-pos + 1:
            curr = curr.prev
            i += 1

연습문제 - 양방향 연결 리스트 메서드 구현

def insertBefore(self,next,newNode)
def popAfter(self,prev)
def popBefore(self,next)
def popAt(self,post)

def insertBefore(self, next, newNode):
       prev = next.prev
       newNode.next = prev.next
       newNode.prev = prev
       prev.next = newNode
       next.prev = newNode
       self.nodeCount += 1 
       return True
def popAfter(self, prev):
       curr = prev.next
       next = curr.next
       prev.next = next
       next.prev = prev
       self.nodeCount -= 1
       result = curr.data
       del(curr)
       return result
   def popBefore(self, next):
       curr = next.prev
       prev = curr.prev
       prev.next = next
       next.prev = prev
       self.nodeCount -= 1
       result = curr.data
       del(curr)
       return result
   def popAt(self, pos):
       if pos < 1 or pos > self.nodeCount : 
           rasie IndexError
       prev = self.getAt(pos-1)
       return self.popAfter(prev)
   def concat(self, L):
       self.tail.prev.next = L.head.next
       L.head.next.prev = self.tail.prev
       self.tail = L.tail
       self.nodeCount += L.nodeCount