연결리스트 level 2 (Dummy Head Linked List)

연결리스트

---

2) Dummy Head를 가지는 연결 리스트

  ① Dummy Head 개요

  - 연결 리스트는 삽입 및 삭제가 유연하게 이뤄질 수 있다는 장점 있음

  - 하지만, 리스트의 길이가 길어질수록 실행 시간이 늘어난다

  - 이러한 단점을 보완하기 insertAfter(prev, newNode), popAfter(prev)와 같은 메소드를 만든다 

  - insertAfter(prev, newNode), popAfter(prev)는 prev가 Head일 시 어떻게 처리해야할 지에 대한 문제가 생김

  - 이러한 문제를 해결하기 위해 Dummy Node를 추가하고 Dummy Node를 '0'번으로 정함

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

  → Dummy Node가 추가됨에 따라 연결 리스트 연산과 관련된 메소드들도 조금씩 수정이 되어야 함

 

  ② 수정된 연결 리스트 연산

    1. 특정 원소 참조(k 번째)

def getAt(self, pos):
	if pos < 0 or pos > self.nodeCount:
		return None
	i = 0				# Dummy Node 추가 후 i가 초기값이 1 -> 0 으로 변경
	curr = self.head		# getAt(00 -> Head
	while i < pos:
		curr = curr.next
		i += 1
		return curr

    2. 리스트 순회

 

	def traverse(self):
		result = []
		curr = self.head
		while curr.next:			# 링크가 살아있는 한 계속해서 쫓아가는 형식
			curr = curr.next
			result.append(curr.data)
		return result

    3. 길이 얻어내기 

self.nodeCount()	# 기존과 동일

    4. 원소 삽입

	def insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:				# pos가 nodeCount + 1인 경우
			self.tail = newNode
		prev.next = newNode
		self.nodeCount += 1
		return True


	def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:		# pos 범위 조건 확인
			return False

		if pos != 1 and pos == self.nodeCount + 1:	# pos가 nodeCount + 1인 경우 prev -> tail
			prev = self.tail
		else:
			prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)

    5. 원소 삭제

    def popAfter(self, prev):
        result = 0
        curr = prev.next
        
        if prev.next == self.tail :
            prev.next = None
            self.tail = prev
        else : prev.next = curr.next
        result = curr.data
        self.nodeCount -= 1
        return result
    

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount :
            raise IndexError

        prev = self.getAt(pos - 1)
        
        return self.popAfter(prev)

    6. 두 리스트 합치기

 

 

def concat(self, L):
	self.tail.next = L.head.next	# L.head는 Dummy node이므로 self.tail.next -> L.head.next
	if L.tail:
		self.tail = L.tail
	self.nodeCount += L.nodeCount