LinkedList Swift Implementation

Question

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.

• Heslacher: 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 .
• Noah Wilder: 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.

Answer 1

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

• Noah Wilder: 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 🤞