[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트 도전과제

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트  도전과제

Raywenderlich.com 에서 나온 Data Structures & Algorithms in Swift 책의 데모 공개본을 번역하였습니다. 즐겁게 봐주세요. 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift

---

 

섹션 2. 기초 자료구조 Elementary Data Structure

챕터 7. 연결 리스트 도전과제 Linked Lists Challenges

이번 챕터에서 연결리스트로 자주 사용되는 다섯가지 문제들을 다뤄볼 겁니다. 이 문제들은 다른 도전과제에 비해서는 상대적으로 쉽고, 자료 구조에 대한 여러분의 지식을 공고하게 해줄 것입니다.

 

Start project를 열면 아래 도전과제들을 볼 수 있습니다.

도전과제 1: 거꾸로 출력하기

연결리스트의 노드를 거꾸로 출력하는 함수를 만들어봅니다.

 

// 예제 
1 -> 2 -> 3 -> nil

// 아래와 같은 형태로 출력이 되어야 합니다.
3
2
1

 

도전과제 2: 가운데 노드 찾기 

연결리스트에서 중앙에 위치한 노드를 찾는 함수를 만들어봅니다.

 

// 예제

1 -> 2 -> 3 -> 4 -> nil
// 여기서 가운데 노드는 3입니다.

1 -> 2 -> 3 -> nil
// 여기서 가운데 노드는 2입니다.

 

도전과제 3: 연결리스트 뒤집기 

연결리스트의 순서를 뒤집는 함수를 만들어봅니다. 노드를 직접 다루어서 반대방향으로 연결되게 합니다.

 

// 예시 
// 전
1 -> 2 -> 3 -> nil

// 후 
3 -> 2 -> 1 -> nil

 

도전과제 4: 연결리스트 2개 합치기 

두개의 정렬된 연결리스트를 합쳐서 하나의 정렬된 연결리스트로 만드는 함수를 만들어봅니다. 목표는 두개의 연결리스트에 있는 요소를 정렬된 순서로 가지고 있는 새로운 연결리스트를 반환하는 것입니다. 정렬순서는 오름차순으로 가정할 수 있습니다.

 

// 예시

// 연결리스트 1
1 -> 4 -> 10 -> 11

// 연결리스트 2
-1 -> 2 -> 3 -> 6

// 합쳐진 연결리스트 
-1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 10 -> 11

 

 

도전과제 5: 특정 요소와 일치하는 모든 대상을 제거 

연결리스트의 특정 요소와 일치하는 모든 노드를 제거하는 함수를 만들어봅니다. 이전에 연결리스트에 구현해본 remove(at:)  메서드와 유사합니다.

 

// 예시 

// 원본 리스트 
1 -> 3 -> 3 -> 3 -> 4

// 모든 3을 제거한 리스트 
1 -> 4

---

해결책

도전 과제 1 해결책 

보다 간단하게 해결하는 방법은 재귀를 이용하는 것입니다. 재귀를 이용하면 콜 스택(Call Stack)을 빌드할 수 있으므로 콜 스택이 해제될 때 출력문을 호출하기만 하면 됩니다.

 

첫번째 과업은 노드의 끝까지 재귀적으로 순회하는 것입니다. 이를 도와주는 다음 함수를 플레이그라운드에 추가합니다.

 

private func printInReverse<T>(_ node: Node<T>?) {

  // 1
  guard let node = node else { return }

  // 2
  printInReverse(node.next)
}

 

1. 먼저 재귀를 종료하는 조건인 기본 케이스부터 시작합니다. 만약 node 가 nil이면 리스트 마지막에 도달했다는 뜻이므로 종료조건이 됩니다.
2. 재귀호출이므로 다음 노드를 매개변수로 동일한 함수를 호출합니다.

출력

print 문을 추가하는 위치에 따라 역순으로 리스트를 출력할 지 여부가 결정됩니다.

함수를 아래와 같이 업데이트 합니다.

 

private func printInReverse<T>(_ node: Node<T>?) {
  guard let node = node else { return }
  printInReverse(node.next)
  print(node.value)
}

 

재귀호출 다음으로 오는 코드는 기본 케이스가 발동(여기서는 재귀호출이 리스트의 마지막까지 갔을 때)되었을 때 호출됩니다. 재귀 문이 풀리게 되면서 노드 데이터가 출력됩니다.

마지막으로 원래의 printInReverse 안에 이 함수를 호출합니다.

 

func printInReverse<T>(_ list: LinkedList<T>) {
  printInReverse(list.head)
}

 

시도해보기

다음 코드를 플레이그라운드 아래에 작성해봅시다.

 

example(of: "printing in reverse") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Original list: \(list)")
  print("Printing in reverse:")
  printInReverse(list)
}

 

아래 결과물을 볼 수 있습니다.

 

---Example of printing in reverse---
Original list: 1 -> 2 -> 3
Printing in reverse:
3
2
1

 

리스트의 모든 노드를 순회해야하므로 알고리즘의 시간 복잡도는 O(n) 입니다. 묵시적으로 함수 호출 스택을 사용하여 각 요소를 처리하므로 공간복잡도 역시 O(n) 입니다.

 

---

 

도전 과제 2 해결책 

이 해결책은 두 개의 포인터가 리스트의 노드를 모두 순회하는 것입니다. 둘 중 한 포인터는 다른 포인터보다 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
    slow = slow?.next
  }

  return slow
}

 

 while 을 선언할 때 다음 노드를 nextFast에 바인딩합니다. 만약 다음 노드가 있으면 fast 포인터를 nextFast 의 다음 노드로 업데이트하여 효과적으로 리스트를 두번 순회하게 합니다.  slow 참조는 한번만 업데이트 합니다. 이러한 방식을 러너 기법 runner’s technique 이라고 합니다.

 

 

시도해보기

다음 코드를 플레이그라운드 아래에 작성해봅시다.

 

example(of: "getting the middle node") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print(list)

  if let middleNode = getMiddle(list) {
    print(middleNode)
  }
}

 

아래 결과물을 볼 수 있습니다.

 

---Example of getting the middle node---
1 -> 2 -> 3
2 -> 3

 

한 번의 패스로 리스트를 순회하였으므로 이 알고리즘의 시간 복잡도는  O(n)  입니다. 러너 기법 runner’s technique 은 연결리스트와 연관되어 있는 다양한 문제를 해결하는 데 도움이 됩니다.

 

 

---

도전 과제 3 해결책 

연결리스트를 뒤집기 위해서 모든 노드에 방문하여 next 참조를 반대 방향으로 업데이트해야합니다. 여러 노드의 참조들을 관리해야하므로 까다로운 작업이 될 수 있습니다.

 

쉬운 방법

새 빈 리스트로 push 메서드를 이용해 간단하게 리스트를 뒤집을 수 있습니다. 아래 코드를 플레이그라운드에 업데이트하세요.

 

extension LinkedList {

  mutating func reverse() {

    // 1
    let tmpList = LinkedList<Value>()
    for value in self {
      tmpList.push(value)
    }

    // 2
    head = tmpList.head
  }
}

 

1. 먼저 현재 값을 모두 새 tmpList 리스트에 푸시합니다. 이렇게 하면 역순의 리스트를 만들게 됩니다.
2. head 참조를 새로 만들어진 리스트로 바꿔줍니다.

O(n)의 시간 복잡도인데다 쉽고 간편하지요.

 

하지만 잠깐...

리스트를 뒤집는 데에 O(n) 은 최적의 시간복잡도지만, 이전 방식은 상당한 리소스 비용이 있습니다. reverse 는 새 리스트에 새로운 노드를 각각 push 메서드로 할당해야합니다. 새 리스트를 사용하지 않고도 각 노드의 next 포인터를 조작하여 리스트를 뒤집을 수 있습니다. 코드는 좀 더 복잡해지겠지만 성능 면에서 상당한 이점을 얻게 됩니다.

 

reverse() 메서드를 아래와 같이 업데이트합니다.

 

mutating func reverse() {
  tail = head
  var prev = head
  var current = head?.next
  prev?.next = nil

  // ...
}

 

먼저 head 를 tail 에 할당합니다. 다음으로 두개의 참조 prev 와 current 를 만들어 순회를 추적합니다. 이 전략은 꽤 직관적입니다. 각 노드는 리스트에서 다음 노드를 가리키고 있습니다. 리스트를 탐색하면서 각 노드가 이전 노드를 가리키도록 합니다.

 

다이어그램에서 보이는 것처럼, 이 과정은 꽤 복잡합니다. current 를 prev 로 가리키게 되면 리스트의 나머지에 대한 링크를 잃게 됩니다. 때문에 세번째 포인터를 관리해야 합니다. reverse 메서드 아래에 다음 코드를 추가하세요.

 

while current != nil {
  let next = current?.next
  current?.next = prev
  prev = current
  current = next
}

 

리스트를 뒤집을 때마다, 다음 노드에 대한 새로운 참조를 생성합니다. 모든 과정이 끝나면 두개의 포인터를 다음 두개의 노드로 이동합니다.

모든 참조를 뒤집었다면, head 를 리스트의 마지막으로 설정합니다. reverse 메서드 맨 끝에 다음을 추가하세요.

 

head = prev

 

시도해보기

다음 코드를 플레이그라운드 아래에 작성해봅시다.

 

example(of: "reversing a list") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Original list: \(list)")
  list.reverse()
  print("Reversed list: \(list)")
}

 

아래 결과물을 볼 수 있습니다.

 

---Example of reversing a list---
Original list: 1 -> 2 -> 3
Reversed list: 3 -> 2 -> 1

 

이 reverse 메서드의 시간복잡도는 여전히 O(n) 입니다. 이전에 다루었던 쉬운 구현과 동일합니다. 하지만 임시 리스트를 사용하거나 새로운 Node 오브젝트를 할당할 필요가 없으므로 알고리즘의 성능을 상당히 향상시킬 수 있습니다.

 

---

도전 과제 4 해결책 

이 문제의 해결책은 두개의 정렬된 리스트에서 노드를 계속해서 뽑아서 새로운 리스트에 추가하는 것입니다. 두 리스트가 정렬되어 있으므로 두 리스트의 next노드를 비교하여 새 리스트에 다음으로 추가될 것이 무엇인지 확인할 수 있습니다.

 

설정하기

두 리스트가 비었는지 여부를 체크하는 것으로 시작합니다. 아래 코드를  mergeSorted에 추가합니다.

guard !left.isEmpty else {
  return right
}

guard !right.isEmpty else {
  return left
}

var newHead: Node<T>?

만약 하나가 비었다면 다른 하나를 반환합니다. Node 오브젝트의 정렬된 리스트를 가지도록 하는 새 참조를 선언합니다. 이 전략은 left 와 right 의 노드들을 newHead 에 정렬된 순서로 병합하는 것입니다.

 

다음 코드를 newHead 아래에 작성합니다.

 

// 1
var tail: Node<T>?
var currentLeft = left.head
var currentRight = right.head
// 2
if let leftNode = currentLeft, let rightNode = currentRight {
  if leftNode.value < rightNode.value {
    newHead = leftNode
    currentLeft = leftNode.next
  } else {
    newHead = rightNode
    currentRight = rightNode.next
  }
  tail = newHead
}

 

1. 추가하려는 새 목록의 tail 포인터를 만듭니다. 
2. newHead 에 할당하기 위해 left 와 right 의 첫번째 노드들을 비교합니다.

 

병합하기

다음으로 새 리스트가 정렬되었는지 확인하기 위해 추가할 노드를 선택하여 left 와 right 모두를 반복합니다. 함수 끝에 다음을 추가하세요.

// 1
while let leftNode = currentLeft, let rightNode = currentRight {
  // 2
  if leftNode.value < rightNode.value {
    tail?.next = leftNode
    currentLeft = leftNode.next
  } else {
    tail?.next = rightNode
    currentRight = rightNode.next
  }
  tail = tail?.next
}

 

1. while 반복문은 리스트 중 하나가 끝에 도달할 때까지 반복됩니다.
2. 이전과 마찬가지로 노드들을 비교하여 tail 에 연결할 노드를 찾습니다.

 

이 반복문은 currentLeft 와 currentRight 에 의존하기 때문에 리스트 중에 노드가 남아있어도 종료될 수 있습니다.

남은 노드들을 관리하기 위해 아래를 추가합니다.

 

if let leftNodes = currentLeft {
  tail?.next = leftNodes
}

if let rightNodes = currentRight {
  tail?.next = rightNodes
}

 

남은 노드들을 붙이는 코드입니다.

 

마무리 하기 위해서, 새로운 리스트를 초기화합니다. 리스트에 append 나 insert 메서드를 이용해 요소를 삽입하는 대신 리스트의 head 와 tail 의 참조를 직접적으로 설정하면 됩니다.

 

var list = LinkedList<T>()
list.head = newHead
list.tail = {
  while let next = tail?.next {
    tail = next
  }
  return tail
}()
return list

 

시도해보기

다음 코드를 플레이그라운드 아래에 작성해봅시다.

 

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)")
  print("Second list: \(anotherList)")
  let mergedList = mergeSorted(list, anotherList)
  print("Merged list: \(mergedList)")
}

 

아래 출력 결과물을 볼 수 있습니다.

 

---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 은 첫번째 리스트의 노드 개수이고 n 은 두번째 리스트의 드 개수입니다.

 

 

---

 

도전 과제 5 해결책 

이 해결책은 리스트를 순회하여 제거하고자 하는 요소와 일치하는 모든 노드를 삭제합니다. 제거할 때마다 선행 노드를 후속노드와 재연결해주어야 합니다. 복잡할 수 있지만 이 기법을 연습할 가치는 충분합니다. 많은 자료구조와 알고리즘이 포인터 산술을 잘 사용하는 것에 의존합니다.

 

몇 가지 고려할 것이 있습니다. 첫번째는 리스트의 앞부분에서 노드를 지우는 것입니다.

 

헤드를 잘라내기

 

첫번째로 고려할 케이스는 리스트의 헤드가 여러분이 제거하고자 하는 값을 가지고 있을 때 입니다. 예를 들어 아래 리스트에서 1을 제거하고 싶다고 가정해봅니다.

 

헤드 → 1 → 1 → 2

 

그렇다면 여러분은 새로운 헤드가 2를 가리키도록 할 것입니다.

다음 코드를  remove 함수에 삽입합니다.

 

 

while let head = head, head.value == value {
  head = head?.next
}

 

먼저 리스트의 헤드에 제거하는 값이 있을 경우를 처리합니다. 동일한 값을 가진 일련의 노드가 있을 수 있으므로 while 반복문을 이용하여 모두 제거하였는지 확인합니다.

 

 

노드의 연결을 끊어내기

 

연결리스트와 관련된 다른 많은 알고리즘처럼 포인터 산술 연산을 이용하여 노드를 해제합니다. 다음 코드를  remove의 아래쪽에 추가하세요.

 

var prev = head
var current = head?.next
while let currentNode = current {
  guard currentNode.value != value else {
    prev?.next = currentNode.next
    current = prev?.next
    continue
  }
  // more to come
}

 

 

두개의 포인터를 이용해 리스트를 순회해야합니다. guard 문의 else 블럭은 노드를 삭제해야하는 경우 동작됩니다.

원하지 않는 노드를 우회하도록 리스트를 수정합니다.

 

계속 작업하기

뭘 깜박했을까요? 위의 경우 while 문은 절대 종료되지 않습니다. prev 와 current 포인터를 함께 이동해야합니다. while 반복문 하단 guard 문 뒤쪽에 다음을 추가하세요.

 

prev = current
current = current?.next

 

 

마지막으로 연결리스트의 tail 을 업데이트합니다. 이는 원래의 tail 이 제거하려는 값이 있는 노드일 경우 필요한 작업입니다. 다음을 removeAll 끝에 추가합니다.

 

tail = prev

 

 

시도해보기

다음 코드를 플레이그라운드 아래에 작성해봅시다.

 

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)
}

아래 출력 결과물을 볼 수 있습니다.

 

---Example of deleting duplicate nodes---
1 -> 1 -> 2 -> 2

이 알고리즘은 모든 요소를 지나가야 하므로 시간복잡도는 O(n) 입니다.

 

 

🔗 번역 시리즈 링크

0️⃣ 섹션 0. 시작하기전에

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 0. 시작하기 전에

1️⃣ 섹션 1. 소개 Introduction

> 챕터 1.왜 자료구조와 알고리즘을 배워야할까요? / 챕터 2. 복잡도  Complexity

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터1. 왜 자료구조와 알고리즘을

> 챕터3. 스위프트 표준 라이브러리 Swift Standard Library

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 1. 소개 - 챕터3. 스위프트 표준 라이브러리 S

 

1️⃣ 섹션 2. 기초 자료구조 Elementary Data Structure

> 챕터 4. 스택 Stacks /  챕터 5. 스택 도전과제 Stack Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터4~5. 스택, 스택 도전

> 챕터 6-1. 연결리스트 Linked List (연결리스트 정의, 요소 추가, 삭제)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-1. 연결리스트 (정

> 챕터 6-2. 연결리스트 Linked List (스위프트 표준 라이브러리의 콜렉션 프로토콜, 카우 Copy-On-Write,  밸류 시맨틱)

 

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터6-2. 연결리스트

 

> 챕터 7. 연결리스트 도전과제 Linked List Challenges

[Swift][번역] 스위프트의 자료구조와 알고리즘 - 섹션 2. 기초 자료구조 - 챕터7. 연결리스트 도전

 

 

---

마치며 

 

오늘도 읽어주셔서 감사합니다.

 

궁금한 점이 있다면 댓글로, 도움이 되셨다면 공감 부탁드립니다.

혹시 수정하거나 피드백하실  내용 있다면 언제든 댓글로 부탁드립니다.

 

감사합니다.