Ich dachte immer: "Warum musst du deine eigene Kopie schreiben? Es ist cool, wenn es Strukturen gibt und sie so schnell sind, dass sie alles für dich tun."
All dies wird jedoch erst benötigt, wenn Sie mit dem Schreiben Ihrer eigenen Typen beginnen und sich auf LinkedLists einlassen.
Was ist diese verknüpfte Liste und welche Vorteile hat sie?
Eine verknüpfte Liste bietet mehrere theoretische Vorteile gegenüber zusammenhängenden Speicheroptionen wie Array:
Verknüpfte Listen haben eine zeitliche Komplexität von O (1) zum Einfügen der ersten Elemente. Arrays haben eine zeitliche Komplexität von O (n).
Die Einhaltung von Swift-Erfassungsprotokollen wie Sequence and Collection bietet viele nützliche Methoden für eine relativ kleine Anzahl von Anforderungen.
Eine verknüpfte Liste ist eine Folge von Datenelementen, in denen jedes Element als Knoten bezeichnet wird .
Es gibt zwei Haupttypen von verknüpften Listen:
Einfach verknüpfte Listen sind verknüpfte Listen, in denen jeder Knoten nur eine Verknüpfung zum nächsten Knoten hat.
Doppelt verknüpfte Listen sind verknüpfte Listen, in denen jeder Knoten eine Verknüpfung zum vorherigen und nächsten Knoten hat.
, . , 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) .
, . - , .
Swift isKnownUniquelyReferenced. , , .
Wenn Sie am Anfang der Funktion copyNodes () Code hinzufügen, müssen Sie nicht weiter kopieren:
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
}
Diese Methode hat viel mit der vorherigen Implementierung gemeinsam. Der Hauptunterschied besteht darin, dass der neu kopierte Knoten basierend auf dem übergebenen Parameter zurückgegeben wird.
Copy-on-Write ist also nicht weit entfernt und unter der Haube. Und ganz überschaubar und verständlich.