Liste liée: Quand devriez-vous écrire votre copie sur écriture dans iOS?

J'ai toujours pensé: "Pourquoi avez-vous besoin d'écrire votre propre copie sur écriture? C'est cool quand il y a des structures et elles sont si rapides qu'elles font tout pour vous."

Mais tout cela n'est pas nécessaire jusqu'à ce que vous commenciez à écrire vos propres types et que vous soyez accro aux LinkedLists.

Qu'est-ce que cette liste chaînée et quels sont ses avantages?

Une liste chaînée présente plusieurs avantages théoriques par rapport aux options de stockage contiguës telles que Array:

• Les listes liées ont une complexité temporelle O (1) pour insérer les premiers éléments. Les tableaux ont une complexité temporelle O (n).

  
  
  
  
  

• La conformité aux protocoles de collecte Swift tels que Sequence et Collection offre de nombreuses méthodes utiles pour un nombre assez restreint d'exigences.

  
  
  
  
  
  
  
  
  
  

Une liste liée est une séquence d'éléments de données dans laquelle chaque élément est appelé un nœud .

Il existe deux principaux types de listes liées:

Les listes liées individuellement sont des listes liées dans lesquelles chaque nœud n'a qu'un lien vers le nœud suivant.

Les listes à double liaison sont des listes liées dans lesquelles chaque nœud a un lien vers le nœud précédent et suivant.

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

Et si vous ajoutez du code au début de la fonction copyNodes (), vous n'avez pas besoin de copier davantage:

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
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Cette méthode a beaucoup en commun avec l'implémentation précédente. La principale différence est qu'il renverra le nœud nouvellement copié en fonction du paramètre passé.

Ainsi, la copie sur écriture n'est pas quelque chose de lointain et sous le capot. Et tout à fait gérable et compréhensible.