Lista vinculada: Quando você deve escrever sua cópia na gravação no iOS?

Eu sempre pensei: "Por que você precisa escrever seu próprio copy-on-write? É legal quando existem estruturas e elas são tão rápidas que fazem tudo por você."

Mas tudo isso não é necessário até que você comece a escrever seus próprios tipos e esteja viciado em LinkedLists.

O que é esta lista vinculada e quais são seus benefícios?

Uma lista vinculada tem várias vantagens teóricas sobre as opções de armazenamento contíguo, como Array:

• Listas vinculadas têm complexidade de tempo O (1) para inserir os primeiros elementos. Matrizes têm uma complexidade de tempo de O (n).

  
  
  
  
  

• A conformidade com os protocolos de coleta Swift como Sequence and Collection oferece muitos métodos úteis para um número bastante pequeno de requisitos.

  
  
  
  
  
  
  
  
  
  

Uma Lista Vinculada é uma sequência de itens de dados em que cada item é chamado de Nó .

Existem dois tipos principais de listas vinculadas:

Listas vinculadas individualmente são listas vinculadas nas quais cada nó se vincula apenas ao próximo nó.

Listas duplamente vinculadas são listas vinculadas nas quais cada nó tem um link para o nó anterior e o próximo.

, . , 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. , , .

E se você adicionar código ao início da função copyNodes (), não precisará copiar mais:

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
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Este método tem muito em comum com a implementação anterior. A principal diferença é que ele retornará o nó recém-copiado com base no parâmetro passado.

Assim, o Copy-on-write não é algo distante e escondido. E bastante administrável e compreensível.