프로그래머스 강의_9

연결리스트가 힘을 발휘할 때

• 아이폰에서 여러 프로그램을 켜놨을 때 삭제할때
• 삽입과 삭제가 유연하다는 것이 가장 큰 장점
  ==> 새로운 메서드를 만들자
  insertAfter(prev, newNode) -> 맨 앞에는 어떻게?
  popAfter(prev) -> 맨 앞에서는 어떻게??

조금 변형된 연결 리스트

연결리스트 연산 - 맨 앞에 dummy node를 추가하는 것을 시작 함수로 삽입한다.

class LinkedList:
### dummy node 추가하는 방법
   def __init__(self) :
       self.nodeCount = 0
       self.head = Node(None)
       self.tail = None
       self.head.next = self.tail
       

연결리스트 연산 - 순회

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

연결리스트 연산 - k 번째 원소 얻어내기

def getAt(self,pos) :
    if pos < 1 or pos > self.nodeCount :
        return None
    ## head에 0번으로 추가했기 때문에 i = 0부터 시작
    i = 0
    curr = self.head
    while i < pos :
        curr = curr.next
        i += 1
    return curr

연결 리스트 연산 - 원소의 삽입

def insertAfter(self,prev,newNode) :
prev가 가리키는 node의 다음에 newNode를 삽입하고
성공/실패에 따라 True/False 출력

def insertAfter(self,prev,newNode) :
    newNode.next = prev.next
    ## Tail 뒤에 삽입하는 경우 
    if prev.next is None:
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

앞에 더미노드를 추가하는 방법을 통해 코드를 줄일 수 있다.

메서드 InsertAt()의 구현
(1) pos 범위 조건 확인
(2) pos == 1 인 경우에는 head 뒤에 새 node 삽입
(3) pos == nodeCount +1 인 경우 prev <- tail
(4) 그렇지 않은 경우에는 prev <-getAt(...)

def insertAt(self, pos, newNode) :
   if pos<1 or pos> self.nodeCount +1 :
       return False
   
   if pos != 1 and pos == self.nodeCount + 1 :
       prev = self.tail
   else :
       prev = self.getAt(pos -1)
   return self.insertAfter(prev, newNode)

연결리스트 연산 - 원소의 삭제
def popAfter(self, prev) :
prev의 다음 node를 삭제하고 그 node의 data를 리턴

r = L.popAfter(prev)
-> 코드 구현 주의사항
(1) prev가 마지막 node일 때 (prev.next == None)
=> 삭제할 node 없음
=> return None
(2) 리스트 맨 끝의 node를 삭제할 때 (curr.next == None)
=> Tail 조정필요

연결리스트 연산 - 두 리스트의 연결
L.concat(L2)
self.tail.next = L2.head.next
self.tail = L2.tail

def concat(self, L) :
   self.tail.next = L.head.next
   if L.tail :
       self.tail = L.tail
   self.nodeCount += L.nodeCount

연습문제

    def popAfter(self, prev):
        if prev.next == None :
            return None 
        curr = prev.next

        if curr.next == None : 
            self.tail = prev
            prev.next = None
                
        else :
                prev.next = curr.next
        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount +1 :
            return IndexError
        else :
            prev = self.getAt(pos-1)
        return self.popAter(prev)