Return to Revisions

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 simplified 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 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.

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
}

Structure

You have nice 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 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
}

Some return values can be ignored

If you add the @discardableResult attribute to the popFirst() and popLast() method then a user of the library has the option to remove elements

var l1 = LinkedList([1, 2, 3])
l1.popFirst()
l1.popLast()

without getting a “Result of call to ... is unused” warning.

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.popFirst()
_ = l1.popLast()

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