How to Implement Doubly Linked List in Swift

Swift DoublyLinkedList of DataStructure

Consider:

let node = Node<String>(value: "3+3")

The problem is that this is a new Node instance, not in any linked list. Perhaps you had another Node with the same String value in your linked list, but that doesn’t matter. This is a new, unlinked, instance. This is unlinked instance has no previous or next values.

Then consider the attempt to remove it from your linked list (replacing Expression with linkedList, following convention that variable and property names always start with a lowercase letter):

linkedList.remove(node)

When you hit the if let prev = ... line, that will fail (because your new Node instance is not linked to anything), it will fall through to the else clause, and the remove method is setting head to this new Node’s next. But because this Node is unlinked to anything, its next is nil. So, when head is set to nil, you've lost your reference to the linked list.

---

To fix this, you should not instantiate a new Node instance, but rather you should find the existing instance in the linked list and remove that.

---

I might also suggest that the logic for determining whether the head or tail must be updated should be dictated by whether the node in question is the current head or tail, e.g.:

public func remove(_ node: Node<T>) -> T {
    let prev = node.previous
    let next = node.next
    
    if head === node { head = next }
    if tail === node { tail = prev }
    
    node.previous?.next = next
    node.next?.previous = prev

    node.previous = nil
    node.next = nil
    
    return node.value
}

Cannot print entire doubly linked-list elements to console

Here is an implementation that meets your requirements.

description for a Node now returns previousNode!.dataItem <-> dataItem <-> nextNode!dataItem. If previousNode or nextNode is nil, then nil will be printed.

description for a DoublyLinkedList will use the linkedDescription of a Node to provide a recursive description of the list. Each Node's linkedDescription will include the Nodes dataItem plus the linkedDescription of the nextNode if it isn't nil. <-> is used between the nodes to represent the links.

extension DoublyLinkedList : CustomStringConvertible {
    var description : String {
        guard let doublyLinkedListHead = head else { return "UnderFlow"}
        return doublyLinkedListHead.linkedDescription
    }
}

extension Node : CustomStringConvertible {
    var description: String { return
        ((previousNode == nil) ? "nil" : "\(previousNode!.dataItem)") +
        " <-> \(dataItem) <-> " +
        ((nextNode == nil) ? "nil" : "\(nextNode!.dataItem)")
    }

    var linkedDescription: String {
        return "\(dataItem)" + ((nextNode == nil) ? "" : " <-> \(nextNode!.linkedDescription)")
    }
}

This will recursively provide the entire list when you print(list). When you print(node), it will provide previousNode!.dataItem <-> dataItem <-> nextNode!.dataItem.

---

Example:

var list = DoublyLinkedList<Int>()
list.InsertAtBeginning(4)
list.InsertAtBeginning(7)
print(list)

7 <-> 4

print(list.head!)

nil <-> 7 <-> 4

list.insertAtEnd(5)
list.insertAtEnd(4)
print(list)

7 <-> 4 <-> 5 <-> 4

print(list.head!.nextNode!)

7 <-> 4 <-> 5

Make LinkedList Generic in Swift

So your append method expects a type T (which in your case is Search), while you are directly subclassing a Node.

So you can

Option 1: create append that accepts the Node, e.g.:

    func append(value: T) {
        let newNode = Node(value: value)
        append(newNode: newNode)
    }
    
    func append(newNode: Node<T>) {
        
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        } else {
            head = newNode
        }
        
        tail = newNode
    }

So now you can

let x = DoublyLinkedList<Search>()
let y = TransactionFilterNode(...)
x.append(newNode: y) // No problem

Option 2: subclass Search instead of subclassing Node
I.e. maybe instead of class TransactionFilterNode: Node<Search> you meant to say class TransactionFilter: Search?

Custom Index for Linked List in Swift

Let's address the second problem first:

Furthermore, indices' offset invalidate after mutation to their node's parent list, thus causing absurd situations ...

That is to be expected with all collections. From Collections:

Saved indices may become invalid as a result of mutating operations.

Using an invalidated index is undefined behavior, and anything can happen: An unexpected result, a fatal error, ... Here is a simple example for Swift strings:

var s = "abcd"
let i = s.firstIndex(of: ")!
s.remove(at: s.startIndex) // invalidates `i`
s.remove(at: i)
print(s) // \360cd

Now the first (main?) problem:

... the method has no way of knowing and checking whether or not that index/node belongs to that specific LinkedList instance.

Quoting from Collections again:

You can pass only valid indices to collection operations. You can find a complete set of a collection’s valid indices by starting with the collection’s startIndex property and finding every successor up to, and including, the endIndex property. All other values of the Index type, such as the startIndex property of a different collection, are invalid indices for this collection.

In your case

mutableList[immutableIndex] = 0

immutableIndex is not a valid index for mutableList, so this is again undefined behavior. A user of your library can not expect that this does anything sensible.

A possible way to protect against this misuse could be to store in the LinkedList.Index a (weak) pointer to the head node of the linked list, and verify that owner in the accessor methods (subscripts).

---

Related Topics