3
\$\begingroup\$

Linked List Implementation in Swift

Swift 5.0, Xcode 10.3

I have written an implementation for a doubly linked list in Swift. As well, I decided to make the node class private and thus hidden to the user so they don't ever need to interact with it. I have written all of the algorithms that I needed to give it MutableCollection, BidirectionalCollection, and RandomAccessCollection conformance.


What I Could Use Help With

  • I am pretty sure that my LinkedList type properly satisfies all of the time complexity requirements of certain algorithms and operations that come hand in hand with linked lists but am not sure.
  • I was also wondering if there are any ways I can make my Linked List implementation more efficient.
  • In addition, I am not sure if there are and linked list specific methods or computed properties that I have not included that I should implement.
  • I have some testing but if you do find any errors/mistakes in my code that would help a lot.
  • Any other input is also appreciated!

Here is my code:

public struct LinkedList<Element> {

    private var headNode: LinkedListNode<Element>?
    private var tailNode: LinkedListNode<Element>?
    public private(set) var count: Int = 0

    public init() { }

}

//MARK: - LinkedList Node
extension LinkedList {

    fileprivate typealias Node<T> = LinkedListNode<T>

    fileprivate class LinkedListNode<T> {
        public var value: T
        public var next: LinkedListNode<T>?
        public weak var previous: LinkedListNode<T>?

        public init(value: T) {
            self.value = value
        }
    }

}

//MARK: - Initializers
public extension LinkedList {

    private init(_ nodeChain: NodeChain<Element>?) {
        guard let chain = nodeChain else {
            return
        }
        headNode = chain.head
        tailNode = chain.tail
        count = chain.count
    }

    init<S>(_ sequence: S) where S: Sequence, S.Element == Element {
        if let linkedList = sequence as? LinkedList<Element> {
            self = linkedList
        } else {
            self = LinkedList(NodeChain(of: sequence))
        }
    }

}

//MARK: NodeChain
extension LinkedList {
    private struct NodeChain<Element> {
        let head: Node<Element>!
        let tail: Node<Element>!
        private(set) var count: Int

        // Creates a chain of nodes from a sequence. Returns `nil` if the sequence is empty.
        init?<S>(of sequence: S) where S: Sequence, S.Element == Element {
            var iterator = sequence.makeIterator()

            guard let firstValue = iterator.next() else {
                return nil
            }

            var currentNode = Node(value: firstValue)
            head = currentNode

            var nodeCount = 1

            while true {
                if let nextElement = iterator.next() {
                    let nextNode = Node(value: nextElement)
                    currentNode.next = nextNode
                    nextNode.previous = currentNode
                    currentNode = nextNode
                    nodeCount += 1
                } else {
                    tail = currentNode
                    count = nodeCount
                    return
                }
            }

            return nil
        }
    }
}

//MARK: - Copy Nodes
extension LinkedList {
    private mutating func copyNodes() {
        guard let nodeChain = NodeChain(of: self) else {
            return
        }

        headNode = nodeChain.head
        tailNode = nodeChain.tail
    }
}


//MARK: - Computed Properties
public extension LinkedList {
    var head: Element? {
        return headNode?.value
    }

    var tail: Element? {
        return tailNode?.value
    }

    var first: Element? {
        return head
    }

    var last: Element? {
        return tail
    }
}

//MARK: - Sequence Conformance
extension LinkedList: Sequence {

    public typealias Iterator = LinkedListIterator<Element>

    public __consuming func makeIterator() -> LinkedList<Element>.Iterator {
        return LinkedListIterator(node: headNode)
    }

    public struct LinkedListIterator<T>: IteratorProtocol {

        public typealias Element = T

        private var currentNode: LinkedListNode<T>?

        fileprivate init(node: LinkedListNode<T>?) {
            currentNode = node
        }

        public mutating func next() -> T? {
            guard let node = currentNode else {
                return nil
            }
            currentNode = node.next
            return node.value
        }

    }
}

//MARK: - Collection Conformance
extension LinkedList: Collection {

    public typealias Index = LinkedListIndex<Element>

    public var startIndex: LinkedList<Element>.Index {
        return Index(node: headNode, offset: 0)
    }

    public var endIndex: LinkedList<Element>.Index {
        return Index(node: nil, offset: count)
    }

    public func index(after i: LinkedList<Element>.Index) -> LinkedList<Element>.LinkedListIndex<Element> {
        precondition(i.offset != endIndex.offset, "LinkedList index is out of bounds")
        return Index(node: i.node?.next, offset: i.offset + 1)
    }

    public struct LinkedListIndex<T>: Comparable {
        fileprivate weak var node: LinkedList.Node<T>?
        fileprivate var offset: Int

        fileprivate init(node: LinkedList.Node<T>?, offset: Int) {
            self.node = node
            self.offset = offset
        }

        public static func ==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func < <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
            return lhs.offset < rhs.offset
        }
    }

}


//MARK: - MutableCollection Conformance
extension LinkedList: MutableCollection {

    public subscript(position: LinkedList<Element>.Index) -> Element {
        get {
            precondition(position.offset != endIndex.offset, "Index out of range")
            guard let node = position.node else {
                fatalError("LinkedList index is invalid")
            }
            return node.value
        }
        set {
            precondition(position.offset != endIndex.offset, "Index out of range")

            // Copy-on-write semantics for nodes
            if !isKnownUniquelyReferenced(&headNode) {
                copyNodes()
            }

            position.node?.value = newValue
        }
    }
}



//MARK: LinkedList Specific Operations
public extension LinkedList {

    mutating func prepend(_ newElement: Element) {
        replaceSubrange(startIndex..<startIndex, with: [newElement])
    }

    mutating func prepend<S>(contentsOf newElements: S) where S: Sequence, S.Element == Element {
        replaceSubrange(startIndex..<startIndex, with: newElements)
    }

    mutating func popFirst() -> Element? {
        guard !isEmpty else {
            return nil
        }
        return removeFirst()
    }

    mutating func popLast() -> Element? {
        guard !isEmpty else {
            return nil
        }
        return removeLast()
    }
}

//MARK: - BidirectionalCollection Conformance
extension LinkedList: BidirectionalCollection {
    public func index(before i: LinkedList<Element>.LinkedListIndex<Element>) -> LinkedList<Element>.LinkedListIndex<Element> {
        precondition(i.offset != startIndex.offset, "LinkedList index is out of bounds")
        if i.offset == count {
            return Index(node: tailNode, offset: i.offset - 1)
        }
        return Index(node: i.node?.previous, offset: i.offset - 1)
    }

}

//MARK: - RangeReplaceableCollection Conformance
extension LinkedList: RangeReplaceableCollection {

    public mutating func replaceSubrange<S, R>(_ subrange: R, with newElements: __owned S) where S : Sequence, R : RangeExpression, LinkedList<Element>.Element == S.Element, LinkedList<Element>.Index == R.Bound {

        let range = subrange.relative(to: indices)

        precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex, "Subrange bounds are out of range")

        // If range covers all elements and the new elements are a LinkedList then set references to it
        if range.lowerBound == startIndex, range.upperBound == endIndex, let linkedList = newElements as? LinkedList {
            self = linkedList
            return
        }

        var newElementsCount = 0

        // Update count after replacement
        defer {
            count = count - (range.upperBound.offset - range.lowerBound.offset) + newElementsCount
        }

        // There are no new elements, so range indicates deletion
        guard let nodeChain = NodeChain(of: newElements) else {

            // If there is nothing in the removal range
            // This also covers the case that the linked list is empty because this is the only possible range
            guard range.lowerBound != range.upperBound else {
                return
            }

            // Deletion range spans all elements
            guard !(range.lowerBound == startIndex && range.upperBound == endIndex) else {
                headNode = nil
                tailNode = nil
                return
            }

            // Copy-on-write semantics for nodes before mutation
            if !isKnownUniquelyReferenced(&headNode) {
                copyNodes()
            }

            // Move head up if deletion starts at start index
            if range.lowerBound == startIndex {
                // Can force unwrap node since the upperBound is not the end index
                headNode = range.upperBound.node!
                headNode!.previous = nil

            // Move tail back if deletion ends at end index
            } else if range.upperBound == endIndex {
                // Can force unwrap since lowerBound index must have an associated element
                tailNode = range.lowerBound.node!.previous
                tailNode!.next = nil

            // Deletion range is in the middle of the linked list
            } else {
                // Can force unwrap all bound nodes since they both must have elements
                range.upperBound.node!.previous = range.lowerBound.node!.previous
                range.lowerBound.node!.previous!.next = range.upperBound.node!

            }

            return
        }

        // Obtain the count of the new elements from the node chain composed from them
        newElementsCount = nodeChain.count

        // Replace entire content of list with new elements
        guard !(range.lowerBound == startIndex && range.upperBound == endIndex) else {
            headNode = nodeChain.head
            tailNode = nodeChain.tail
            return
        }

        // Copy-on-write semantics for nodes before mutation
        if !isKnownUniquelyReferenced(&headNode) {
            copyNodes()
        }

        // Prepending new elements
        guard range.upperBound != startIndex else {
            headNode?.previous = nodeChain.tail
            nodeChain.tail.next = headNode
            headNode = nodeChain.head
            return
        }

        // Appending new elements
        guard range.lowerBound != endIndex else {
            tailNode?.next = nodeChain.head
            nodeChain.head.previous = tailNode
            tailNode = nodeChain.tail
            return
        }

        if range.lowerBound == startIndex {
            headNode = nodeChain.head
        }
        if range.upperBound == endIndex {
            tailNode = nodeChain.tail
        }

        range.lowerBound.node!.previous!.next = nodeChain.head
        range.upperBound.node!.previous = nodeChain.tail

    }

}

//MARK: - ExpressibleByArrayLiteral Conformance
extension LinkedList: ExpressibleByArrayLiteral {
    public typealias ArrayLiteralElement = Element

    public init(arrayLiteral elements: LinkedList<Element>.ArrayLiteralElement...) {
        self.init(elements)
    }
}

//MARK: - CustomStringConvertible Conformance
extension LinkedList: CustomStringConvertible {
    public var description: String {
        return "[" + lazy.map { "\($0)" }.joined(separator: ", ") + "]"
    }
}

Note: My up-to-date LinkedList implementation can be found here: https://github.com/Wildchild9/LinkedList-Swift.

\$\endgroup\$
  • 2
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Aug 16 at 6:17
  • \$\begingroup\$ Thank you @Heslacher, I've added a link to the Github repository where one can find my updated code and will leave the code in the question itself as is. \$\endgroup\$ – Noah Wilder Aug 16 at 15:11
6
\$\begingroup\$

Nested types

All “dependent” types are defined within the scope of LinkedList, which is good. To reference those types from within LinkedList you don't have to prefix the outer type. For example,

public func index(before i: LinkedList<Element>.LinkedListIndex<Element>) -> LinkedList<Element>.LinkedListIndex<Element> 

can be shortened to

public func index(before i: LinkedListIndex<Element>) -> LinkedListIndex<Element>

This applies at several places in your code.

Nested generics

There are several nested generic types:

fileprivate class LinkedListNode<T> 
private struct NodeChain<Element>
public struct LinkedListIterator<T>: IteratorProtocol
public struct LinkedListIndex<T>: Comparable

All these types are only used with the generic placeholder equal to the Element type of LinkedList, i.e.

private var headNode: LinkedListNode<Element>?
private var tailNode: LinkedListNode<Element>?

public typealias Iterator = LinkedListIterator<Element>
public typealias Index = LinkedListIndex<Element>

So these nested type do not need to be generic: They can simply use the Element type of LinkedList, i.e.

fileprivate class LinkedListNode {
    public var value: Element
    public var next: LinkedListNode?
    public weak var previous: LinkedListNode?

    public init(value: Element) {
        self.value = value
    }
}

which is then used as

private var headNode: LinkedListNode?
private var tailNode: LinkedListNode?

The same applies to the other nested generic types listed above. This allows to get rid of the distracting <T> placeholders and some type aliases. It becomes obvious that the same element type is used everywhere.

Another simplification

The while true { ... } loop in NodeChain.init is not nice for (at least) two reasons:

  • A reader of the code has to scan the entire loop body in order to understand that (and when) the loop is eventually terminated.
  • An artificial return nil is needed to make the code compile, but that statement is never reached.

Both problems are solved if we use a while let loop instead:

init?<S>(of sequence: S) where S: Sequence, S.Element == Element {
   // ...

    while let nextElement = iterator.next() {
        let nextNode = LinkedListNode(value: nextElement)
        currentNode.next = nextNode
        nextNode.previous = currentNode
        currentNode = nextNode
        nodeCount += 1
    }
    tail = currentNode
    count = nodeCount
}

It also is not necessary to make the head and node properties of NodeChain implicitly unwrapped optionals (and does not make much sense for constant properties anyway). Simple non-optional constant properties will do:

    let head: Node<Element>
    let tail: Node<Element>

Structure

You have nicely structured the code by using separate extensions for the various protocol conformances.

In that spirit, var first should be defined with the Collection properties, and var last should be defined with the BidirectionalCollection properties.

To guard or not to guard

(This paragraph is surely opinion-based.) The guard statement was introduced to get rid of the “if-let pyramid of doom,” it allows to unwrap a variable without introducing another scope/indentation level.

The guard statement can be useful with other boolean conditions as well, to emphasize that some condition has to be satisfied, or otherwise the computation can not be continued.

But I am not a fan of using guard for every “early return” situation, in particular not if it makes the statement look like a double negation. As an example,

guard !(range.lowerBound == startIndex && range.upperBound == endIndex) else {
    headNode = nodeChain.head
    tailNode = nodeChain.tail
    return
}

is in my opinion much clearer written as

if range.lowerBound == startIndex && range.upperBound == endIndex {
    headNode = nodeChain.head
    tailNode = nodeChain.tail
    return
}

Performance

One issue that I noticed: You do not implement the isEmpty property, so that the default implementation for collection is used. As a consequence, each call to isEmpty creates two instances of LinkedListIndex (for startIndex and for endIndex), compares them, and then discards them. A dedicated

public var isEmpty: Bool { return count == 0 }

property would be more efficient.

A bug

There seems to be a problem with the copy-on-write semantics:

var l1 = LinkedList([1, 2, 3])
let l2 = l1
l1.removeFirst()
l1.removeLast()

makes the program abort with a “Fatal error: Unexpectedly found nil while unwrapping an Optional value.”

\$\endgroup\$
  • \$\begingroup\$ Thank you for your thoughtful analysis. I have gone through the nested types and shortened them all. In addition, I shortened the nested generic type names and made them use LinkedList's Element type instead. I also rewrote my initializer using the clearer while let ... { loop. The first and last properties have now been properly organized. I also looked in and changed up the instances of guard that acted as a double negation. I added @discardableResult where fit. I also added in your implementation of isEmpty. Lastly, I think I have fixed the copy-on-write semantics finally 🤞 \$\endgroup\$ – Noah Wilder Aug 16 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.