Linked List (Dummy Node)

# 원소 삽입
def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1: # 삽입위치가 맨끝일 경우 바로 tail로 이동
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True

Linked List는 원소의 삽입과 삭제 등이 빠르다는 장점이 있었으나 그 위치가 Head나 Tail이 아닌 경우에는

처음부터 해당 위치까지 getAt 메서드를 통해 탐색해야 한다는 단점이 있었다.

따라서 해당 위치(pos)에 새로운 노드를 삽입하거나 삭제하는 것이 아니라 

그 이전 노드(prev) 다음 위치에 새로운 노드를 삽입하거나 삭제하는 방식으로 코드를 구현하면

소요시간을 줄일 수 있을 것이다.

이를 위해 Linked List의 맨 앞에 Dummy Node라고 하는 빈 노드를 추가할 것이다.

출처 : https://coderanch.com/t/605669/java/Dummy-Head-Singly-Linked-List

이렇게 하면 맨 앞에 노드를 삽입,삭제하는 경우에도 prev 값으로 dummy node를 지정할 수 있다.

# Dummy node 추가된 Linked List
class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

# Linked List 순회
	def traverse(self):
    	result = []
        curr = self.head # dummy node
        while curr.next: # curr.next가 None이 아닐 때 까지 ( curr.next = True )
        	curr = curr.next
            result.append(curr.data)
        return result
        
# Linked List 원소 찾기
	def getAt(self, pos):
    	if pos < 0 or pos > self.nodeCount:  # pos = 0일 경우 dummy node (self.head) return
        	return None
        i = 0
        curr = self.head
        while i < pos :
        	curr = curr.next
            i += 1
        return curr
 
 # Linked List 원소 삽입
 	def insertAfter(self, prev, newNode):
    	newNode.next = prev.next
        if prev.next is None:
        	self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True
    
    def inserAt(self, pos, newNode):
    	if pos < 1 or pos > self.nodeCount+1 :
        	return False
        if pos != 1 and pos == self.nodeCount+1 : # pos가 tail이면서 빈 리스트가 아닐 경우
        	prev = self.tail
        else:
        	prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)
        
  # Linked List 원소 삭제
  	def popAfter(self, prev):
        if prev.next is None: # 삭제할 노드가 없을 때(prev가 마지막 원소)
            return None
        elif self.tail == prev.next: # 맨 끝 노드를 삭제할 때
            curr = prev.next
            prev.next = None
            self.tail = prev
        else :
            curr = prev.next
            prev.next = curr.next
        self.nodeCount -= 1
        return curr.data

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

• dummy node를 사용할 경우 각각의 메서드에 조건식이 줄어들기 때문에 식이 간편해진다.