prev에 노드를 삽입/삭제 하는 기능 추가

• insertAfter(prev, newNode)
  → 맨 앞에는 어떻게 삽입할까?
• popAfter(prev)
  → 맨 앞에는 어떻게 삭제할까?

⇒ Dummy Linked List가 필요

---

Dummy Linked List

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

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

연산 정의

1. 길이 얻어내기

2. 리스트 순회

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

4. 원소 삽입

5. 원소 삭제

6. 두 리스트 합치기

---

리스트 순회

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

특정 원소 참조(K 번째 원소 얻어내기)

def getAt(self, pos): # getAt(0) -> head
	if pos < 1 or pos > self.nodeCount:
    		return None
		
        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 를 리턴

중간에 노드가 생성되는 경우(맨 처음도 같은 케이스)

tail 뒤에 새로운 노드가 추가되는 경우

메서드 insertAt()의 구현

• def insertAt(self, pos, newNode):
• 이미 구현한 insertAfter()를 호출하여 이용하는 것

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

코드의 구현 주의 사항

1. prev가 마지막 node 일 때 (prev.next == None)

   → 삭제할 node가 없음

   → return None

2. 리스트 맨 끝의 node를 삭제할 때 (curr.next == None)

   → Tail 조정 필요

두 리스트의 연결

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

[실습] dummy head를 가지는 연결 리스트 노드 삭제

문제

어서와! 자료구조와 알고리즘은 처음이지? 9강 실습: dummy head 를 가지는 연결 리스트 노드 삭제

문제 설명

제 9 강에서 소개된 추상적 자료구조 LinkedList 는 dummy head node 를 가지는 연결 리스트입니다. 이 클래스의 아래와 같은 메서드들을, 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

popAfter() popAt()

이 때, popAt() 메서드의 구현에서는 popAfter() 를 호출하여 이용하도록 합니다. (그렇게 하지 않을 수도 있지만, 여기에서는 popAfter() 의 이용에 의해서 코드 구현이 보다 쉬워지는 것을 확인하기 위함입니다.)

초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, def popAfter(self, prev): 와 def popAt(self, pos): 의 메서드 몸체만 구현하세요.

만약, popAt() 메서드에 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.

---

나의 풀이

def popAt(self, pos):

• pos < 1 or pos > self.nodeCount 라면,
  • IndexError
• 나머지 로직은 def popAfter(self, prev)에서
• 따라서 prev 변수를 만듬
  • self.getAt(pos - 1)

def popAfter(self, prev):

• 삭제할 curr 노드 지정
  • curr = prev.next
• prev.next 에 노드가 없는 경우
  • 리턴 None
• curr 노드가 마지막 노드인 경우
  • curr 노드 밖에 없는 경우
    • self.tail = None
  • curr 노드 밖에 없지 않은 경우
    • self.tail = prev
• 리펙토링

solution.py

def popAfter(self, prev):
        # 삭제하려는 노드를 curr에 담기
        curr = prev.next

		# prev다음에 노드가 없는 경우 삭제할 노드가 없으니 None 리턴
        if prev.next == None:
            return None

        # 삭제할 노드가 없는 경우
        if curr.next == None:
            # 유일한 노드일 때
            if self.nodeCount == 1:
                self.tail = None
            # 유일한 노드가 아닐 때
            else:
                self.tail = prev
        
        # 링크 조정
        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)
        
        return self.popAfter(prev)

실행 결과

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.7MB)
테스트 2 〉	통과 (0.06ms, 10.6MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.06ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.8MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0