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

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

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

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

 

 

---

 

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

챕터 6. 연결 리스트 Linked Lists 

연결리스트는 값들이 선형적이고 일방향적인 시퀀스로 배치된 콜렉션입니다. 연결리스트는 스위프트 배열과 같은 연속저장 옵션에 비해 이론적인 우위를 가지고 있습니다.

• 리스트의 앞부분에서 삽입 삭제는 상수시간(constant time)이 걸림
• 신뢰할 수 있는 성능 특성

 

 

 

위 다이어그램에서 보이는 것처럼 연결리스트는 노드들의 체인입니다. 노드에는 두가지 의무가 있습니다.

1. 값을 보유
2. 다음 노드의 레퍼런스를 보유. 다음 노드 레퍼런스가 nil 일 경우 리스트의 끝을 의미

이번 챕터에서는 연결리스트를 구현하고 연결리스트와 관련된 일반적인 작업에 대해 배울 것입니다. 각 작업의 시간 복잡도를 배우고 스위프트의 멋진 기능인 Copy On Write(COW, 암시적 공유) 을 구현할 것입니다.

이번 챕터의 스타터 플레이그라운드를 열어 코드로 빠져봅시다.

 

 

 

---

 

노드 Node

Sources 디렉토리에 Node.swift 을 생성하고 아래 코드를 파일에 추가합니다.

public class Node<Value> {

  public var value: Value
  public var next: Node?

  public init(value: Value, next: Node? = nil) {
    self.value = value
    self.next = next
  }
}

extension Node: CustomStringConvertible {

  public var description: String {
    guard let next = next else {
      return "\(value)"
    }
    return "\(value) -> " + String(describing: next) + " "
  }
}

플레이그라운드 페이지로 이동하여 다음을 추가합니다.

 

example(of: "creating and linking nodes") {
  let node1 = Node(value: 1)
  let node2 = Node(value: 2)
  let node3 = Node(value: 3)

  node1.next = node2
  node2.next = node3

  print(node1)
}

여러분은 방금 세개의 노드를 만들고 이들을 연결하였습니다.

 

1,2,3 값을 가지고 있는 연결리스트

콘솔 창에서 아래 아웃풋을 볼 수 있습니다.

---Example of creating and linking nodes---
1 -> 2 -> 3

리스트를 만드는 이 방법은 실용성에 관해서는 아직 많이 부족합니다. 이 방법으로 긴 리스트를 만든다면 실용적이지 못한 것을 바로 알 수 있을 것입니다. 이 문제를 줄이는 일반적인 방법은 LinkedList 를 빌드해서 Node 오브젝트를 관리하는 것입니다. 그냥 하면 됩니다.

 

 

 

연결리스트 LinkedList

LinkedList.swift 를 생성하고 아래를 파일에 추가합니다.

public struct LinkedList<Value> {

  public var head: Node<Value>?
  public var tail: Node<Value>?

  public init() {}

  public var isEmpty: Bool {
    head == nil
  }
}

extension LinkedList: CustomStringConvertible {

  public var description: String {
    guard let head = head else {
      return "Empty list"
    }
    return String(describing: head)
  }
}

링크드리스트는 head 와 tail 이라는 개념이 있습니다. 각각 리스트의 첫번째 노드와 마지막 노드를 의미합니다.

 

 

 

 

리스트에 값(요소) 추가하기

앞서 언급한 바와 같이, Node 개체를 관리하는 인터페이스가 제공됩니다. 먼저 요소를 추가해봅시다. 연결리스트에 값을 추가하는 데는 각각 다른 성능 특성을 가지고 있는 3가지 방법이 있습니다.

1. push: 값을 리스트 앞에 추가하기
2. append: 값을 리스트 끝에 추가하기ㅣ
3. insert(after:): 값을 특정 노드 다음에 추가하기

앞으로 우리는 이 세가지를 다음 섹션에서 구현해보고 각각의 성능특성을 분석할 것입니다.

 

 

푸시 작업 push operations

리스트의 맨 앞에 값을 추가하는  push 작업은  head-first insertion 이라고도 합니다. 코드는 굉장히 단순합니다.

아래 메서드를  LinkedList에 추가하세요.

 

public mutating func push(_ value: Value) {
  head = Node(value: value, next: head)
  if tail == nil {
    tail = head
  }
}

빈 리스트에 값을 푸시하면, 새로운 노드는 리스트의 head 이자 tail 이 됩니다.

플레이그라운드에서 아래를 추가하세요.

 

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

  print(list)
}

 

콘솔창에서 아래와 같이 출력됩니다.

---Example of push---
1 -> 2 -> 3

push 와 pop 은 둘 다 시간복잡도가 O(1) 입니다.

 

append 작업

다음으로 살펴볼 작업은 append 입니다. 리스트의 가장 끝에 값을 추가하며, tail-end insertion 이라고 합니다.

LinkedList.swift 에서 아래 코드를  push 아래에 입력하세요.

 

public mutating func append(_ value: Value) {

  // 1
  guard !isEmpty else {
    push(value)
    return
  }

  // 2
  tail!.next = Node(value: value)

  // 3
  tail = tail!.next
}

 

이 코드들은 비교적 간단합니다.

1. 이전에 얘기한 것처럼 리스트가 비어있다면 head 와 tail 을 새 노드로 업데이트 해주어야합니다. 빈 리스트에 append 는 기능적으로 push 와 동일하므로 push 를 호출하여 작업을 수행합니다.
2. 그 외 모든 경우 여러분은 tail 뒤에 새 노드를 만들게 됩니다. guard 문을 이용하여 isEmpty 케이스를 푸시하므로 명시적 언래핑은 Force unwrapping 은 잘 수행됩니다.
3. tail-end insertion 이므로 여러분의 새 노드는 리스트의 tail이 됩니다.

플레이그라운드로 돌아가서 다음 코드를 아래에 작성합니다.

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

  print(list)
}

 

아래 결과가 콘솔창에서 출력됩니다.

---Example of append---
1 -> 2 -> 3

 

insert(after:) 작업

리스트에 값을 추가하는 세번째이자 마지막 작업은 insert(after:) 입니다. 이 작업은 리스트의 특정 위치에 값을 삽입하는 작업으로 두가지 단계가 필요합니다.

1. 리스트의 특정 노드를 찾는다.
2. 새로운 노드를 삽입한다.

먼저 값을 삽입하고자 하는 노드를 찾는 코드를 구현합니다. LinkedList.swift, 에서 append 아래에 다음 코드를 추가합니다.

 

public func node(at index: Int) -> Node<Value>? {
  // 1
  var currentNode = head
  var currentIndex = 0

  // 2
  while currentNode != nil && currentIndex < index {
    currentNode = currentNode!.next
    currentIndex += 1
  }

  return currentNode
}

 

node(at:) 은 주어진 인덱스에 따라 리스트 안의 노드를 검색합니다. 리스트의 노드는 head 노드에서부터밖에 접근할 수 없으므로 반복적인 순회를 해야합니다. 하나씩 따라가봅시다.

1. head 의 새로운 레퍼런스를 생성하고 현재 순회하고 있는 위치를 추적합니다.
2. while 반복문을 이용하여 원하는 인덱스까지 리스트의 아랫쪽으로 레퍼런스를 이동합니다. 빈 리스트이거나 리스트의 범위를 초과하는 인덱스는 nil 을 반환합니다.

이제 새로운 노드를 삽입해야 합니다. 아래 메서드를 node(at:) 아래에 추가합니다.

 

// 1
@discardableResult
public mutating func insert(_ value: Value,
                            after node: Node<Value>)
                            -> Node<Value> {
  // 2
  guard tail !== node else {
    append(value)
    return tail!
  }
  // 3
  node.next = Node(value: value, next: node.next)
  return node.next!
}

여러분이 한 것은 다음과 같습니다.

1. @discardableResult 는 컴파일러가 경고하지 않고도 호출자가 메서드의 반환값을 무시할 수 있습니다.
2. 이 메서드가 tail 메서드와 함께 호출되는 경우 기능적으로 동등한 append 메서드를 호출하게 됩니다. 이는 tail 노드를 업데이트합니다.
3. 그 외에는 새 노드를 리스트의 나머지와 연결하고 새 노드를 반환합니다.

플레이그라운드 페이지로 돌아가 테스트합니다. 아래 코드를 플레이그라운드 아래에 추가합니다.

 

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

  print("Before inserting: \(list)")
  var middleNode = list.node(at: 1)!
  for _ in 1...4 {
    middleNode = list.insert(-1, after: middleNode)
  }
  print("After inserting: \(list)")
}

아래 결과물을 확인할 수 있습니다.

 

---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3

성능평가

 

휴! 이제까지 잘 해왔습니다. 요약하면 우리는 연결리스트에 값을 추가하는 세가지 작업과 특정 인덱스에 위치한 노드를 찾는 메서드를 구현하였습니다.

 

	push	append	insert(after:)	node(at:)
동작 Behaviour	head에 삽입	tail에 삽입	특정 노드 다음에 삽입	주어진 인덱스의 노드를 반환
시간복잡도 Time complexity	O(1)	O(1)	O(1)	O(i), i 는 주어진 인덱스

 

다음으로 이와 반대되는 삭제 작업을 살펴봅시다.

 

---

리스트에서 값(요소) 삭제하기

노드 삭제에는 세가지 방식의 주요 작업이 있습니다.

1. pop: 리스트 맨 앞의 값을 삭제
2. removeLast: 리스트 맨 마지막 값을 삭제
3. remove(at:): 리스트 특정 위치의 값을 삭제

위 세가지를 구현하고 성능 특성을 평가해봅시다.

 

pop 작업

리스트의 앞에 있는 값을 삭제하는 것은 pop 입니다. 이 작업은 push 만큼 간단합니다.바로 시작합시다.

아래 메서드를  LinkedList 에 추가합니다.

@discardableResult
public mutating func pop() -> Value? {
  defer {
    head = head?.next
    if isEmpty {
      tail = nil
    }
  }
  return head?.value
}

pop 은 리스트에서 삭제되니 값을 반홥환합니다. 리스트가 비어있을 수도 있으므로 이 값은 옵셔널입니다.

head 노드를 아래로 이동하여 리스트의 첫번째 노드를 효과적으로 제거하였습니다. ARC는 어느 레퍼런스도 붙어 있지 않으므로 메서드가 종료되면 메모리에서 오래된 노드를 제거합니다. 만약 리스트가 비게 되면 tail 을 nil 로 설정합니다.

플레이그라운드 페이지로 돌아가서 아래 코드를 밑에 추가하여 테스트합니다.

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

  print("Before popping list: \(list)")
  let poppedValue = list.pop()
  print("After popping list: \(list)")
  print("Popped value: " + String(describing: poppedValue))
}

아래 결과를 콘솔창에서 볼 수 있습니다.

---Example of pop---
Before popping list: 1 -> 2 -> 3
After popping list: 2 -> 3
Popped value: Optional(1)

 

removeLast 작업

 

리스트의 마지막 노드를 제거하는 것은 약간 불편합니다. tail 노드에 대한 참조가 있어도 그 앞에 있는 노드에 대한 참조가 없으면 잘라낼 수 없습니다. 때문에 여러분은 수고스러운 탐색을 해야합니다. 아래 코드를 pop 밑에 추가합니다.

 

@discardableResult
public mutating func removeLast() -> Value? {
  // 1
  guard let head = head else {
    return nil
  }
  // 2
  guard head.next != nil else {
    return pop()
  }
  // 3
  var prev = head
  var current = head

  while let next = current.next {
    prev = current
    current = next
  }
  // 4
  prev.next = nil
  tail = prev
  return current.value
}

코드에서 일어나는 일은 다음과 같습니다.

1. 만약 head 가 nil일 경우 아무것도 제거되지 않습니다. nil 을 반환합니다.
2. 만약 리스트가 한 개의 노드로만 구성되어 있다면 removeLast 는 기능적으로 pop 과 동일합니다. pop 은 head 와 tail 의 레퍼런스 업데이트를 처리하므로, 작업을 위임하기만 하면 됩니다.
3. current.next 가 nil 일 때까지 계속 다음 노드를 검색합니다. 즉 current 가 리스트의 마지막 노드를 의미하는 작업입니다.
4. current 가 마지막 노드이면, prev.next 의 레퍼런스를 이용하여 끊어내면 됩니다. tail 레퍼런스를 꼭 업데이트 해야합니다.

플레이그라운드 페이지로 돌아가서 다음 코드를 아래에 추가합니다.

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

  print("Before removing last node: \(list)")
  let removedValue = list.removeLast()

  print("After removing last node: \(list)")
  print("Removed value: " + String(describing: removedValue))
}

아래 콘솔 창에서 이러한 결과물을 볼 수 있습니다.

---Example of removing the last node---
Before removing last node: 1 -> 2 -> 3
After removing last node: 1 -> 2
Removed value: Optional(3)

removeLast 는 리스트의 끝까지 순회해야 합니다. 이는 O(n) 작업으로 상대적으로 비용이 많이 드는 작업입니다.

remove(after:) 작업

마지막 제거 작업은 리스트의 특정 위치에 있는 특정 노드를 삭제하는 것입니다. insert(after:) 와 매우 유사합니다. 먼저 여러분은 제거하고자 하는 노드의 바로 앞 노드를 찾고, 다음으로는 연결을 끊을 것입니다.

가운데 노드를 제거

LinkedList.swift 로 돌아가서 removeLast 아래에 다음 메서드를 추가합니다.

 

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
  defer {
    if node.next === tail {
      tail = node
    }
    node.next = node.next?.next
  }
  return node.next?.value
}

노드의 연결을 해제하면 defer 블록이 실행됩니다. 만약 삭제된 노드가 tail 노드일 경우, tail 레퍼런스가 반드시 업데이트 되어야하므로 특별한 처리가 필요합니다.

플레이그라운드로 돌아갑시다. 여러분은 방법을 알고 있어요.

 

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

  print("Before removing at particular index: \(list)")
  let index = 1
  let node = list.node(at: index - 1)!
  let removedValue = list.remove(after: node)

  print("After removing at index \(index): \(list)")
  print("Removed value: " + String(describing: removedValue))
}

콘솔 창에서 아래 출력을 볼 수 있습니다.

---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: Optional(2)

더 많은 요소를 추가하고 인덱스 값을 가지고 놀아보세요. insert(at:) 과 유사하게 이 작업의 시간 복잡도는 O(1) 입니다. 하지만 그전에 특정 노드의 레퍼런스가 있어야 합니다.

 

성능 평가

이제 또다른 체크포인트에 도착했네요! 요약하자면 여러분은 연결리스트에서 값을 삭제하는 세가지 작업을 구현하였습니다.

 

	pop	removeLast	remove(after:)
동작 Behaviour	head를 삭제	tail을 삭제	바로 다음 노드를 삭제
시간복잡도 Time complexity	O(1)	O(n)	O(1)

 

이 시점에서 여러분은 대부분 프로그래머가 연관 있을 연결리스트의 인터페이스를 정의하였습니다. 하지만 스위프트 시맨틱을 꾸미기(adorn)위해서는 해야될 일이 있습니다. 이번 챕터의 나머지 절반에서는 인터페이스를 가능한 빠르게(Swifty) 만드는 것에 초점을 맞추겠습니다.

---

🔗 번역 시리즈 링크

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. 연결리스트 도전

 

 

---

마치며 

 

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

 

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

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

 

감사합니다.