[python] dummy node 활용한 Linked List

#맨 앞에 dummy node를 추가한 형태

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


class LinkedList:
    def __init__(self):
        self.nodeCount =0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result =[]
        cur= self.head.next
        while(cur is not None):
            result.append(cur.data)
            cur=cur.next


        return result
    

    def getAt(self, pos):
        if pos<0 or pos > self.nodeCount:
            return None
        i=0
        cur = self.head
        while(i<pos):
            cur = cur.next
            i+=1

        return cur
    
    def insertAfter(self, prev, newNode):
        #prev가 가리키는 node의 다음에 newNode를 삽입하고
        #성공/실패에 따라 True, False 반환
        newNode.next = prev.next

        if(prev.next== None):
            self.tail = newNode
    
        prev.next = newNode
        self.nodeCount+=1
        return True

    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 리턴

        #1. prev가 마지막 node인 경우(삭제할 노드 없기에 None 리턴)
        if(prev.next==None):
            return None
        delNode = prev.next

        #2. 리스트의 맨 끝 node 삭제할 경우
        if(prev.next==self.tail):
            self.tail = prev
        prev.next = delNode.next


        self.nodeCount-=1
        return delNode.data
    


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

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