연결 리스트가 힘을 발휘할 때

아이폰에서 백그라운드 앱이 주르륵 나열되어 있을 때, 순서 지어 연결된 무언가를 구현할 때 좋다. 사용자가 특정 앱을 삭제, 삽입하는 일이 빈번한 시나리오에는 연결 리스트가 적절할 수 있다.

• 삽입과 삭제가 유연하다는 것이 최대 장점

이러한 장점을 살리려면 새로운 메서드 두 개를 작성하려고 한다. position이 아니라 특정 노드를 주고, 그 노드의 앞, 뒤에 작업

• insertAfter(prev, newNode) --> 맨 앞은 어떻게?
• popAfter(prev) --> 맨 앞은 어떻게?

조금 변형된 연결 리스트

맨 앞에 dummy node를 추가한 형태

ㅁ -> 67 -> 34 -> 58 -> null

head                       tail

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

리스트 순회

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

k번째 원소 얻어내기

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

	i = 0
	curr = self.head
	while i < pos:
		curr = curr.next
		i += 1

	return curr

원소의 삽입

이미 구현한 insertAfter()를 호출하여 구현할 수 있다.

1. pos 범위 확인