Daftar Tertaut: Kapan Anda harus menulis Salinan-saat-tulis di iOS?

Saya selalu berpikir: "Mengapa Anda perlu menulis salinan-saat-menulis Anda sendiri? Sangat keren bila ada struktur dan mereka begitu cepat sehingga mereka melakukan segalanya untuk Anda."

Tetapi semua ini tidak diperlukan sampai Anda mulai menulis tipe Anda sendiri dan Anda terpikat pada LinkedLists.

Apa daftar tertaut ini dan apa manfaatnya?

Daftar tertaut memiliki beberapa keunggulan teoretis dibandingkan opsi penyimpanan yang berdekatan seperti Array:

• Daftar tertaut memiliki kompleksitas waktu O (1) untuk memasukkan elemen pertama. Array memiliki kompleksitas waktu O (n).

  
  
  
  
  

• Kepatuhan dengan protokol pengumpulan Swift seperti Urutan dan Koleksi menawarkan banyak metode yang berguna untuk sejumlah kecil persyaratan.

  
  
  
  
  
  
  
  
  
  

Sebuah Daftar Tertaut adalah urutan item data di mana setiap item disebut Node .

Ada dua jenis utama daftar tertaut:

Daftar tertaut tunggal adalah daftar tertaut di mana setiap node hanya memiliki link ke node berikutnya.

Daftar tertaut ganda adalah daftar tertaut di mana setiap node memiliki link ke node sebelumnya dan berikutnya.

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

Dan jika Anda menambahkan kode ke awal fungsi copyNodes (), Anda tidak perlu menyalin lebih lanjut:

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
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Metode ini memiliki banyak kesamaan dengan implementasi sebelumnya. Perbedaan utamanya adalah ia akan mengembalikan node yang baru disalin berdasarkan parameter yang diteruskan.

Jadi, Copy-on-write bukanlah sesuatu yang jauh dan tersembunyi. Dan cukup mudah diatur dan dimengerti.