9강: 연결 리스트(Linked Lists) (3)

강의

Dummy Node

연결 리스트는 삽입과 삭제가 유연하다는 장점이 있습니다.

1. 특정 노드 다음에 삽입하기

2. 특정 노드 다음을 삭제하기

→ dummy node 사용하기

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

 

 

연결 리스트 연산

1 길이 얻어내기

2. 리스트 순회하기

def traverse(self):
    result = []
    
    curr = self.head
    
    while curr.next:	# 따라갈 노드가 존재할 경우
        curr = curr.next
        result.append(curr.data)
    
    return result

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

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None

    i = 0	# 시작 노드 = dummy node
    curr = self.head

    while i < pos:
        curr = curr.next
        i += 1

    return curr

4. 원소 삽입하기

def insertAfter(self, prev, newNode):
    newNode.next = prev.next
    
    if prev.next is None:	# tail 뒤에 삽입하는 경우
        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:	# 빈 리스트가 아니면서 tail 뒤에 삽입하는 경우
        prev = self.tail
    else:
        prev = self.getAt(pos - 1)
        
    return self.insertAfter(prev, newNode)

5. 원소 삭제하기

6. 두 리스트 합치기

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

 

 

9강 실습: dummy node를 가지는 연결 리스트 노드 삭제하기

⭐ dummy node를 이용해 간단하게 popAfter과 popAt 구현하는 문제!

⭐ tail 노드를 삭제하는 코너 케이스 주의!

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

    if curr is None:
        return False

    if curr.next is 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:
        raise IndexError

    prev = self.getAt(pos-1)

    if pos != 1 and pos == self.nodeCount:
        self.tail = prev

    return self.popAfter(prev)