In the linked list section, I think I’ve found bug for the “remove(after:)” func after we implement the “copyNodes()” function.
Before we add copyNodes(), the function works adequately, and we have “After removing at index 1: 1 → 3” printed out as expected. But, after adding copyNodes() at the beginning of the remove(after:) function, the printout is “After removing at index 1: 1 → 2 → 3”
Then, in “example(of: “removing a node after a particular node”)”, with the copyNodes() at the beginning of the remove(after:) function, I assign list to a new list2 var prior to performing the remove operation. list2 prints out the desired outcome after the operation and list prints out as if nothing was removed!?
@kelvin_lau Can you please help with this when you get a chance? Thank you - much appreciated! :]
Hey Paul, thank you for bringing this up. This is indeed a bug.
The root of the problem is this line here:
let node = list.node(at: index - 1)!
node is a reference to a node of list.
However, once you call a mutating method, copyNodes creates a brand new set of nodes for list. The node value is now referencing an old node that is no longer part of list.
I’ll have to think about how I can fix this. But thank you for flagging this!
Hi Kevin!
Good, can’t wait to see the fix.
Edit: Added isKnownUniquelyReferenced check (hadn’t gotten that far yet).
Edit2: Fixed tail comparison check on insert after
I have a fix that I’ve tested out and seems to resolve the issue. This applies anywhere that a selected node is passed in. So, same issue on insert as well. I am handling it by optionally passing in the selected node and making a comparison to determine if a node in the copied list should also be selected.
Here is my modified copyNodes method:
@discardableResult
private mutating func copyNodes(selected node: Node<Value>? = nil) -> Node<Value>? {
guard !isKnownUniquelyReferenced(&head) else {
return node
}
guard var oldNode = head else {
return nil
}
var newSelectedNode: Node<Value>? = nil
head = Node(value: oldNode.value)
var newNode = head
while let nextOldNode = oldNode.next {
newNode!.next = Node(value: nextOldNode.value)
if node != nil && node === oldNode {
newSelectedNode = newNode
}
newNode = newNode!.next
oldNode = nextOldNode
}
tail = newNode
return newSelectedNode
}
Here are the changes to the insert(after) and remove(after):
@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
let selectedNode = copyNodes(selected: node)
// 2
guard tail !== selectedNode! else {
append(value)
return tail!
}
// 3
selectedNode!.next = Node(value: value, next: selectedNode!.next)
return selectedNode!.next!
}
@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
let selectedNode = copyNodes(selected: node)
defer {
if selectedNode!.next === tail {
tail = selectedNode
}
selectedNode!.next = selectedNode!.next?.next
}
return selectedNode!.next?.value
}
Am I reading that correctly: You are grabbing hold of a reference to the original non-copied node that is passed into insert(:after:) and remove(after:) and within the copyNodes function “transform” that reference to instead point to the corresponding copied node?
Yep. That’s exactly what I’m doing.
Looks like Tim’s solution works well. (Thank you Tim).
However, only ‘remove’ part has been revised on the book.
‘insert’ part needs to be revised on new edition.
You’re right. insert also has the same problem. Tagged for updates on the next version - thanks @tim_miller @stephen_moon
Tim has a point and looks like this issue is clarified now.
I have a question related to this topic. We modified copyNodes() with guard isKnownUniquelyReferenced(&head) in order to alleviate the problem that COW creates O(n) overhead on every mutating call. I tried testing each method by adding a print(isKnownUniquelyReferenced(&head)) at the start of each method and it always prints false even though there is only 1 reference to the list.
I think I actually figured it out with further testing, please let me know if this is correct. I see that it actually returns false only if there are multiple references to the list or the list is containing less than 2 nodes. Since an empty list means head is referencing nil, isKnownUniquelyReferenced(&head) will return false and when the list has 1 node, the node is both referenced by head and tail so isKnownUniquelyReferenced(&head) will return false?
copyNodes(returningCopyOf node:) checks the same condition as copyNodes() → guard !isKnownUniquelyReferenced(&head). But in this case, head actually only has 1 reference to it. node(at:) returns the node at specified position so it is that node that has the duplicate reference causing copyNodes(returningCopyOf:) to never fall past the guard. So in the method remove(after:), guard let node = copyNodes(returningCopyOf: node) else { return nil } always returns nil.
The case described in the book is an edge case where the node returned by node(at:) is actually the head, creating two references to head allowing the guard to fall through in copyNodes(returningCopyOf node:) and subsequently the guard in remove(after:). This solution fixes the edge case but breaks all other cases.
Here is a somewhat crude solution I came up with to handle both cases:
@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
var currentNode: Node<Value>?
defer {
if currentNode?.next === tail {
tail = currentNode
}
currentNode?.next = currentNode?.next?.next
}
if node === head {
guard let node = copyNodes(returningCopyOf: node) else { return nil }
currentNode = node
} else {
copyNodes()
currentNode = node
}
return currentNode?.next?.value
}
Hi all, just come to this thread after read the latest version (fourth version) I still found an issue with the copyNodes(returningCopyOf:) function.
in the remove example:
print("Removing middle node on list2")
if let node = list2.node(at: 0) {
list2.remove(after: node)
}
print("List2: \(list2)")
it seems that it is working properly, but if I try to do the next:
list2.append(5)
list2 will remains the same with no changes, this issue is because the missing change of updating tail at the end of the copyNodes function:
tail = newNode
This issue was reported and confirmed in November 2018. As of August 2023, the issue has not been corrected for the book or for the repo.
The 4th edition of the online book does not address the problem. Section 6.8 Optimizing COW, has a subsection “A minor predicament” that mentions the remove(after:) problem, but not the insert(after:) problem.
The github 4th edition repo, line 45, is using the wrong version of copyNodes(). It should be using the same call that remove(after: ) uses on line 88.
guard let node = copyNodes(returningCopyOf: node) else { return nil }
repo: https://github.com/kodecocodes/alg-materials/blob/editions/4.0/07-linked-list-challenge/projects/final/LinkedListChallenge.playground/Sources/LinkedList.swift
