Chapter 7: Linked List Challenges
Challenge 1: Print in reverse
연결 리스트(Linked List)를 역순(revese)로 출력하는 함수를 만든다. 예를 들면 다음과 같다.
1 -> 2 -> 3 -> nil
// should print out the following:
3
2
1
Solution
재귀(recursion)로 간단하게 구현할 수 있다. 재귀를 사용하면, 함수 호출을 Stack 으로 작성할 수 있다. 이 호출 Stack이 unwind 될 때 print구문을 출력해 주면 된다. 먼저, 연결 리스트의 끝까지 재귀적으로 순회한다.
private func printInReverse<T>(_ node: Node<T>?) {
guard let node = node else { return } //재귀 종료 조건
//node가 nil 이면(list의 마지막) 재귀호출을 종료한다.
printInReverse(node.next)
//LinkedList의 끝까지 재귀적으로 순회한다.
print(node.value) //printInReverse가 재귀적으로 호출되므로, 리스트의 끝에 도달한 이후 호출된다.
//LinkedList의 역순으로 print되며 해당 구문이 완료된다.
}
Printing
마지막으로, printInReverse 함수에서 helper 메서드를 호출해야 한다.
func printInReverse<T>(_ list: LinkedList<T>) {
printInReverse(list.head)
}
Test it out!
example(of: "printing in reverse") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Original list: \(list)") // Original list: 1 -> 2 -> 3
print("Printing in reverse:")
printInReverse(list)
// 3
// 2
// 1
}출력 결과는 다음과 같다.
---Example of printing in reverse---
Original list: 1 -> 2 -> 3
Printing in reverse:
3
2
1
List의 각 node를 순회해야 하기 때문에 이 알고리즘의 시간 복잡도는 O(n) 이다. 함수 호출 Stack을 사용하여 각 요소를 처리하므로, 공간 복잡도 또한 O(n) 이다.
Challenge 2: Find the middle node
연결 리스트(Linked List)의 중간 노드(node)를 찾는 함수를 만든다. 예를 들면 다음과 같다.
1 -> 2 -> 3 -> 4 -> nil
// middle is 3
1 -> 2 -> 3 -> nil
// middle is 2
Solution
해결 방법 중 하나는 2개의 참조를 사용해, Node를 순회하는 것이다. 하나의 참조는 다른 것 보다 2배 빠르게 설정한다. 빠른 참조가 끝에 도달하면, 느린 참조는 리스트의 중간에 있게 된다.
func getMiddle<T>(_ list: LinkedList<T>) -> Node<T>? {
var slow = list.head
var fast = list.head
while let nextFast = fast?.next {
fast = nextFast.next
//다음 node가 있는 경우, 해당 node는 nextFast가 되어 slow보다 2배 빠르게 순회한다.
//fast는 두 번 업데이트 된다.
slow = slow?.next //slow는 한 번만 업데이트 된다.
}
return slow
}이러한 구현 방법을 runner’s technique 라고 한다.
Try it out!
example(of: "getting the middle node") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print(list) // 1 -> 2 -> 3
if let middleNode = getMiddle(list) {
print(middleNode) // 2 -> 3
}
}출력은 다음과 같다.
---Example of getting the middle node---
1 -> 2 -> 3
2 -> 3
리스트의 끝까지 순회 하기 때문에 이 알고리즘의 시간 복잡도는 O(n) 이다. runner’s technique은 LinkedList와 관련된 다양한 문제를 해결하는 데 도움이 된다.
Challenge 3: Reverse a linked list
연결 리스트(Linked List)를 반대로 하는 함수를 생성한다. 노드(node)가 반대 방향으로 연결되도록 구현하면 된다. 예를 들면 다음과 같다.
// before
1 -> 2 -> 3 -> nil
// after
3 -> 2 -> 1 -> nil
Solution
연결 리스트(Linked List)를 reverse 하려면, 각 node의 next참조가 반대 방향의 node를 가리키도록 업데이트해야 한다. 여러 node에 대한 참조를 관리해야 하므로 까다로운 작업이 될 수 있다.
The easy way
새로운 임시(temp) LinkedList와, push를 사용하면 간단하게 List를 reverse할 수 있다.
extension LinkedList {
mutating func reverse() {
var tempList = LinkedList<Value>() //임시 LinkedList
for value in self {
tempList.push(value)
//현재 LinkedList에서 tempList로 push(앞에서 삽입)한다. List가 역순으로 생성된다.
}
head = tempList.head //head가 reverse된 list의 node를 가리키도록 한다.
}
}시간 복잡도는 O(n) 이다.
But wait...
O(n) 는 list를 reverse하기 위한 최적의 시간 복잡도이지만, 이 알고리즘에는 상당한 리소스가 사용된다. 위에서 구현한 reverse()는 임시 list에 각 value를 push할 때마다, 새 node를 생성하고 할당한다. 하지만, 임시 list를 완전히 사용하지 않고도, 각 node의 다음 포인터를 조작하여 list를 reverse할 수 있다. 코드는 더 복잡해 지지만, 성능은 상당히 개선된다. reverse() 메서드를 수정해 준다.
extension LinkedList {
mutating func reverse() {
tail = head //tail에 head를 할당한다.
//순회를 추적하기 위한 두 개의 참조를 생성한다.
var prev = head
var current = head?.next
prev?.next = nil
//각 node는 list에서 다음 node를 가리키고 있다.
//list를 순회하면서, 각 node가 이전 node를 가리키게 하도록 업데이트 한다.
while current != nil {
let next = current?.next
current?.next = prev //current node에 새로운 참조 작성
prev = current //포인터 이동
current = next //포인터 이동
} //next node에 대한 새로운 참조가 작성된다.
head = prev //모든 참조를 reverse한 후, head를 list의 마지막 node로 설정한다.
}
}각 node는 list에서 다음 node를 가리키고 있다. list를 순회하면서, 각 node가 이전 node를 가리키게 하도록 업데이트 한다.
current를 prev로 할당하면, 나머지 list에 대한 참조가 사라지게 된다. 따라서 세 번째 참조(next)를 관리해야 한다. reverse가 진행될 때마다, 다음 node에 대한 새로운 참조가 작성된다. 모든 reverse 절차 이후에 두 포인터(prev, current)를 이동해 준다.
Try it out!
example(of: "reversing a list") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
print("Original list: \(list)") // Original list: 1 -> 2 -> 3
list.reverse2()
print("Reversed list: \(list)") // Reversed list: 3 -> 2 -> 1
}출력은 다음과 같다.
---Example of reversing a list---
Original list: 1 -> 2 -> 3
Reversed list: 3 -> 2 -> 1
새로운 reverse() 메서드의 시간 복잡도는 여전히 O(n) 이다. 하지만, tempList를 사용하거나 새 node 객체를 생성할 필요가 없어 성능은 크게 향상된다.
Challenge 4: Merge two lists
두 개의 정렬된 연결 리스트(Linked List)를 가져와서 하나의 정렬된 연결 리스트로 병합하는 함수는 만든다. 두 리스트의 모든 노드가 순서대로 연결된 새로운 연결 리스트를 반환하면 된다. 정렬 순서는 오름차순(ascending)으로 구현한다. 예를 들면 다음과 같다.
// list1
1 -> 4 -> 10 -> 11
// list2
-1 -> 2 -> 3 -> 6
// merged list
-1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 10 -> 11
solution
두 개의 정렬된 list에서 노드를 계속 가져와 새 list에 추가한다. 두 list가 정렬되어 있으므로, 각 list의 next node를 비교하여 어느 것이 새 list에 추가되어야 하는지 확인할 수 있다.
Setting up
양쪽의 list가 비어 있는지 확인하는 것 부터 시작한다.
guard !left.isEmpty else {
return right
}
guard !right.isEmpty else {
return left
}
var newHead: Node<T>? //정렬된 list에 사용할 새로운 node
양쪽의 list가 비어 있는지 확인한다. 비어 있다면, 다른 list를 반환한다. 또한, 정렬된 Node 객체 목록을 보유하기 위해 새로운 참조(newHead)를 선언한다. left와 right의 node를 정렬된 순서로 newHead에 병합한다.
var tail: Node<T>? //새 list의 tail node. //상수 시간(constant-time)의 append 연산을 허용한다.
var currentLeft = left.head
var currentRight = right.head
if let leftNode = currentLeft, let rightNode = currentRight {
//left와 right의 첫 node를 비교하여 newHead에 할당한다.
if leftNode.value < rightNode.value {
newHead = leftNode
currentLeft = leftNode.next
} else {
newHead = rightNode
currentRight = rightNode.next
}
tail = newHead
}
Merging
위의 첫 node에 대해 작업한 것 처럼, left와 right를 iterate 해서 필요한 node를 선택해 새 list로 정렬되도록 한다.
while let leftNode = currentLeft, let rightNode = currentRight {
//while loop는 list 중 하나의 끝에 도달할 때까지 반복된다.
if leftNode.value < rightNode.value {
//첫 node에서 한 작업과 같이, left와 right의 첫 node를 비교하여 tail에 연결한다.
tail?.next = leftNode
currentLeft = leftNode.next
} else {
tail?.next = rightNode
currentRight = rightNode.next
}
tail = tail?.next
}while 조건을 보면, 두 list 중 한 쪽에 아직 node가 남아 있더라도, 한 개의 list의 순회가 끝나면 loop가 종료된다. 나머지 node를 처리하는 코드를 추가한다.
if let leftNode = currentLeft {
tail?.next = leftNode
}
if let rightNodes = currentRight {
tail?.next = rightNodes
}새 list를 인스턴스화 한다. append() 또는 insert() 메서드로 요소를 삽입하는 대신, list의 head와 tail에 대한 참조를 직접 설정해 주면 된다.
var list = LinkedList<T>()
list.head = newHead
list.tail = { //append() 또는 insert()를 사용하지 않고, tail에 대한 참조를 직접 설정해 준다.
while let next = tail?.next {
tail = next
}
return tail
}()
return list전체 코드를 정리하면 다음과 같다.
func mergeSorted<T: Comparable>(_ left: LinkedList<T>,
_ right: LinkedList<T>) -> LinkedList<T> {
guard !left.isEmpty else {
return right
}
guard !right.isEmpty else {
return left
}
//양쪽의 list가 비어 있는지 확인한다. 비어 있다면, 다른 list를 반환한다.
var newHead: Node<T>? //정렬된 list에 사용할 새로운 node
//left와 right의 node를 정렬된 순서로 newHead에 병합한다.
var tail: Node<T>? //새 list의 tail node. //상수 시간(constant-time)의 append 연산을 허용한다.
var currentLeft = left.head
var currentRight = right.head
if let leftNode = currentLeft, let rightNode = currentRight {
//left와 right의 첫 node를 비교하여 newHead에 할당한다.
if leftNode.value < rightNode.value {
newHead = leftNode
currentLeft = leftNode.next
} else {
newHead = rightNode
currentRight = rightNode.next
}
tail = newHead
}
//위의 첫 node에 대해 작업한 것 처럼, left와 right를 iterate 해서 필요한 node를 선택해 새 list로 정렬되도록 한다.
while let leftNode = currentLeft, let rightNode = currentRight {
//while loop는 list 중 하나의 끝에 도달할 때까지 반복된다.
if leftNode.value < rightNode.value {
//첫 node에서 한 작업과 같이, left와 right의 첫 node를 비교하여 tail에 연결한다.
tail?.next = leftNode
currentLeft = leftNode.next
} else {
tail?.next = rightNode
currentRight = rightNode.next
}
tail = tail?.next
}
//while 조건을 보면, 두 list 중 한 쪽에 아직 node가 남아 있더라도, 한 개의 list의 순회가 끝나면 loop가 종료된다.
if let leftNode = currentLeft {
tail?.next = leftNode
}
if let rightNodes = currentRight {
tail?.next = rightNodes
}
//나머지 남은 list의 node들을 추가한다.
//새 list를 인스턴스화 한다. append() 또는 insert() 메서드로 요소를 삽입하는 대신,
//list의 head와 tail에 대한 참조를 직접 설정해 주면 된다.
var list = LinkedList<T>()
list.head = newHead
list.tail = { //append() 또는 insert()를 사용하지 않고, tail에 대한 참조를 직접 설정해 준다.
while let next = tail?.next {
tail = next
}
return tail
}()
return list
}
Try it out!
example(of: "merging two lists") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(1)
var anotherList = LinkedList<Int>()
anotherList.push(-1)
anotherList.push(-2)
anotherList.push(-3)
print("First list: \(list)") // First list: 1 -> 2 -> 3
print("Second list: \(anotherList)") // Second list: -3 -> -2 -> -1
let mergedList = mergeSorted(list, anotherList)
print("Merged list: \(mergedList)") // Merged list: -3 -> -2 -> -1 -> 1 -> 2 -> 3
}출력은 다음과 같다.
---Example of merging two lists---
First list: 1 -> 2 -> 3
Second list: -3 -> -2 -> -1
Merged list: -3 -> -2 -> -1 -> 1 -> 2 -> 3
이 알고리즘의 시간 복잡도는 O(m + n) 이다. m의 첫 번째 list의 node 수 이고, n은 두 번째 list의 node 수 이다.
Challenge 5: Remove all occurrences
연결 리스트(Linked List)에서 특정 요소를 모두 제거하는 함수를 작성한다. 이 구현은 연결 리스트의 remove(at:) 메서드와 유사하다. 예를 들면 다음과 같다.
// original list
1 -> 3 -> 3 -> 3 -> 4
// list after removing all occurrences of 3
1 -> 4
solution
list를 순회하여 제거하려는 요소와 일치하는 모든 node를 제거한다. 제거 할 때마다, 선행 node와 후속 node를 다시 연결해야 해야 하므로 복잡해질 수 있다. 많은 자료구조(Data Struct)와 알고리즘(Algorithm)은 포인터 연산을 다루는 경우가 많으므로, 충분한 연습이 필요하다. 구현에 고려해야 할 몇 가지 경우(case)가 있다. 첫 번째는 list의 앞부분에서 node를 제거하는 것이다.
Trimming the head
head에 제거하려는 value가 포함되어 있는 경우를 고려해 봐야 한다. 다음 리스트에서 1을 제거한다고 가정한다.
새 head가 2를 가리키도록 해야 한다. remove 함수에 다음 코드를 추가한다.
while let head = head, head.value == value {
self.head = head.next
}리스트의 head에 제거하려는 value가 포함된 경우를 처리한다. 같은 value를 가진 node가 head부터 여러 개 연달아 있을 수 있으므로, loop를 사용해 모두 제거한다.
Unlinking the nodes
연결 리스트와 관련된 많은 알고리즘과 마찬가지로 포인터 연산을 사용해 node 연결을 해제한다.
var prev = head
var current = head?.next
while let currentNode = current {
guard currentNode.value != value else {
//node를 제거해야하는 경우 guard 블록이 실행된다.
prev?.next = currentNode.next
current = prev?.next
continue
}
//more to come
}두 개의 포인터를 사용해 목록을 순회한다. guard-else 블록에서 node가 제거된다. 원하지 않은 node(제거한 node)를 우회하도록 리스트의 참조를 수정해야 한다.
Keep traveling...
위의 구현은 while 구문이 무한 loop가 될 수 있다. loop를 종료하려면, prev와 current 참조를 이동해야 한다. while-loop의 guard 구문 다음에 코드를 추가한다.
prev = current
current = current?.next마지막으로 연결 리스트의 tail을 업데이트해야 한다. 이는 tail의 value가 제거하려는 value인 경우 필요하다.
tail = prev전체 코드를 정리하면 다음과 같다.
extension LinkedList where Value: Equatable {
mutating func removeAll(_ value: Value) {
//list의 head에 제거하려는 value가 포함된 경우를 처리해야 한다.
while let head = head, head.value == value {
//같은 value를 가진 node가 head부터 여러 개 연달아 있을 수 있으므로, loop를 사용해 모두 제거한다.
self.head = head.next
}
//중복되는 node를 찾아 연결을 해제한다.
var prev = head
var current = head?.next
//두 개의 포인터로 목록을 순회한다.
while let currentNode = current {
if currentNode.next == nil {
tail
}
guard currentNode.value != value else {
//node를 제거해야하는 경우 guard 블록이 실행된다.
prev?.next = currentNode.next
current = prev?.next
//제거한 node를 우회하도록 list의 참조를 수정한다.
continue
}
//이렇게만 구현하면, while 구문이 무한 loop가 될 수 있다.
//prev와 current 참조를 이동해야 한다.
prev = current
current = current?.next
}
tail = prev
//마지막으로, tail을 업데이트 한다. tail의 value가 제거하려는 value인 경우 필요하다.
}
}
Try it out!
example(of: "deleting duplicate nodes") {
var list = LinkedList<Int>()
list.push(3)
list.push(2)
list.push(2)
list.push(1)
list.push(1)
list.removeAll(3)
print(list) // 1 -> 1 -> 2 -> 2
}출력은 다음과 같다.
---Example of deleting duplicate nodes---
1 -> 1 -> 2 -> 2
이 알고리즘은 모든 요소를 순회하므로 시간복잡도는 O(n) 이다. 이 알고리즘은 정렬되어 있는 연결 리스트(Linked List)에서만 가능하다.