🦉 🤟🏽 👩🏻‍🤝‍👨🏼 リンクリスト：iOSでCopy-on-writeをいつ書くべきですか？ 🗽 🎫 🧙🏽

私はいつも考えていました。「なぜあなたはあなた自身のコピーオンライトを書く必要があるのですか？構造があり、それらがあなたのためにすべてをするほど速いのはクールです。」

しかし、あなたがあなた自身のタイプを書き始めて、あなたがLinkedListsに夢中になるまで、これはすべて必要ではありません。

このリンクされたリストとは何ですか？その利点は何ですか？

リンクリストには、アレイなどの連続したストレージオプションに比べていくつかの理論上の利点があります。

リンクされたリストには、最初の要素を挿入するためのO（1）時間の複雑さがあります。配列の時間の複雑さはO（n）です。
シーケンスやコレクションなどのSwiftコレクションプロトコルへの準拠は、かなり少数の要件に対して多くの便利な方法を提供します。

リンクリストは、各アイテムがノードと呼ばれる一連のデータアイテムです。

リンクリストには主に2つのタイプがあります。

単一リンクリストは、各ノードが次のノードへのリンクのみを持つリンクリストです。

二重リンクリストは、各ノードが前のノードと次のノードへのリンクを持つリンクリストです。

, . , head tail.

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

public struct LinkedList<Value> {
  public var head: Node<Value>?
  public var tail: Node<Value>?
  
  public init() {}

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

, ! , . . .

Node'a , reference type. , . .

? LinkedList . COW .

value type COW . , ( ) .

private mutating func copyNodes() {
  guard var oldNode = head else {
      return
  }
  head = Node(value: oldNode.value)
  var newNode = head
  
  while let nextOldNode = oldNode.next {
    newNode!.next = Node(value: nextOldNode.value)
    newNode = newNode!.next
    oldNode = nextOldNode
  }
  tail = newNode
}

. , O (n) …

COW

O (n) .

, . - , .

isKnownUniquelyReferenced

Swift isKnownUniquelyReferenced. , , .

また、copyNodes（）関数の先頭にコードを追加する場合は、さらにコピーする必要はありません。

private mutating func copyNodes(returningCopyOf node:
Node<Value>?) -> Node<Value>? {
  guard !isKnownUniquelyReferenced(&head) else {
return nil
  }
  guard var oldNode = head else {
return nil
}
  head = Node(value: oldNode.value)
  var newNode = head
  var nodeCopy: Node<Value>?
  while let nextOldNode = oldNode.next {
    if oldNode === node {
      nodeCopy = newNode
    }
    newNode!.next = Node(value: nextOldNode.value)
    newNode = newNode!.next
    oldNode = nextOldNode
}
  return nodeCopy
}

この方法には、以前の実装と多くの共通点があります。主な違いは、渡されたパラメーターに基づいて、新しくコピーされたノードを返すことです。

したがって、Copy-on-writeは、遠いものではなく、内部的なものでもありません。そして、非常に扱いやすく、理解しやすいです。

リンクリスト：iOSでCopy-on-writeをいつ書くべきですか？

COW

More articles: