Linked List: When should you write your Copy-on-write in iOS?

I always thought: "Why do you need to write your own copy-on-write? It's cool when there are structures and they are so fast that they do everything for you."

But all this is not necessary until you start writing your own types and you are hooked on LinkedLists.

What is this linked list and what are its benefits?

A linked list has several theoretical advantages over contiguous storage options such as Array:

• Linked lists have O (1) time complexity for inserting the first elements. Arrays have a time complexity of O (n).

  
  
  
  
  

• Compliance with Swift collection protocols like Sequence and Collection offers many useful methods for a fairly small number of requirements.

  
  
  
  
  
  
  
  
  
  

A Linked List is a sequence of data items in which each item is called a Node .

There are two main types of linked lists:

Singly linked lists are linked lists in which each node only has a link to the next node.

Doubly linked lists are linked lists in which each node has a link to the previous and next node.

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

And if you add code to the beginning of the copyNodes () function, then you don't need to copy further:

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
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

This method has a lot in common with the previous implementation. The main difference is that it will return the newly copied node based on the passed parameter.

Thus, Copy-on-write is not something distant and under the hood. And quite manageable and understandable.