Removing a node after a particular node fails after COW fix

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:

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 = {
        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):

public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
    let selectedNode = copyNodes(selected: node)
    // 2
    guard tail !== selectedNode! else {
        return tail!
    // 3
    selectedNode!.next = Node(value: value, next: selectedNode!.next)
    return selectedNode!.next!

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.

Happy to help! :smiley:

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:

    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 {
            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 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