A quick & dirty singly-linked list in Swift 4.

SinglyLinkedList.swift

/// A singly-linked list.
public final class SinglyLinkedList<T>: RangeReplaceableCollection, MutableCollection {

    /// A node for a singly-linked list.
    final class Node {
        /// The node's data.  May be absent (like for sentinel nodes).
        var value: T?
        /// The link to the next node, or `nil` when none.
        var next: Node!

        /// Creates a disconnected node, possibly with data.
        init(possibleValue: T? = nil) {
            value = possibleValue
            next = self
        }
        /// Creates a disconnected node with the given data.
        convenience init(value: T) {
            self.init(possibleValue: value)
        }
    }

    /// The one-past-the-end node, and points to the first node when the list is not empty.
    var sentinel: Node
    /// The end node.  Points to `sentinel` when the list is empty.
    var tail: Node

    deinit {
        removeAll()
        sentinel.next = nil
    }

    // MARK: Sequence

    public var underestimatedCount: Int { return isEmpty ? 0 : 1 }

    // MARK: (Mutable)Collection

    public var isEmpty: Bool { return sentinel.next === sentinel }

    // The index type.  Hashable to be usable in Key-Paths (I think).
    public struct Index: Comparable, Hashable {
        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.id < rhs.id
        }

        public var hashValue: Int { return id.hashValue }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.node === rhs.node
        }

        /// The targeted node.
        let node: Node
        /// A pusedo-ID.  Should be the offset from `startIndex`, except it's always `max` for `endIndex`.
        let id: UInt
        /// A link to the owning list.  Guards against index mixing.
        weak var list: SinglyLinkedList?
    }

    public subscript(position: Index) -> T {
        get { return position.node.value! }
        set { position.node.value! = newValue }  // The "!" forces a NIL check before write.
    }

    public var endIndex: Index { return Index(node: sentinel, id: UInt.max, list: self) }

    public var startIndex: Index {
        guard !isEmpty else { return endIndex }

        return Index(node: sentinel.next, id: 0, list: self)
    }

    public func index(after i: Index) -> Index {
        guard i.node.next !== sentinel else { return endIndex }

        return Index(node: i.node.next, id: i.id + 1, list: self)
    }

    // MARK: RangeReplaceableCollection

    public required init<S>(_ elements: S) where S: Sequence, S.Element == Element {
        sentinel = Node()
        tail = sentinel
        elements.forEach {
            tail.next = Node(value: $0)
            tail = tail.next
        }
        tail.next = sentinel
    }

    public convenience init() {
        self.init(EmptyCollection())
    }

    public convenience init(repeating repeatedValue: Element, count: Int) {
        self.init(repeatElement(repeatedValue, count: count))
    }

    public func append<S>(contentsOf newElements: S) where S: Sequence, S.Element == Element {
        appendNodes(stealingFrom: SinglyLinkedList(newElements))
    }

    public func append(_ newElement: Element) {
        append(contentsOf: CollectionOfOne(newElement))
    }

    public func insert(_ newElement: Element, at i: Index) {
        insert(contentsOf: CollectionOfOne(newElement), at: i)
    }

    public func insert<C>(contentsOf newElements: C, at i: Index) where C: Collection, C.Element == Element {
        precondition(i.list! === self)
        guard i < endIndex else { append(contentsOf: newElements) ; return }
        guard i != startIndex else { prependNodes(stealingFrom: SinglyLinkedList(newElements)) ; return }

        let previous = index(startIndex, offsetBy: numericCast(i.id - 1), limitedBy: endIndex)!
        insertNodes(after: previous, stealingFrom: SinglyLinkedList(newElements))
    }

    @discardableResult
    public func remove(at position: Index) -> Element {
        precondition(position.list! === self)
        precondition(position < endIndex)
        guard position != startIndex else { return removeFirst() }

        defer { removeSubrange(position ..< index(after: position)) }
        return position.node.value!
    }

    public func removeSubrange(_ bounds: Range<Index>) {
        precondition(bounds.lowerBound.list! === self)
        precondition(bounds.upperBound.list! === self)
        guard !bounds.isEmpty else { return }

        let previous = bounds.lowerBound == startIndex ? nil : index(startIndex, offsetBy: numericCast(bounds.lowerBound.id - 1), limitedBy: endIndex)!

        if bounds.upperBound == endIndex {
            if let beforeLowerBound = previous {
                truncateTail(cuttingOffAfter: beforeLowerBound)
            } else {
                removeAll()
            }
        } else {
            let high = index(bounds.lowerBound, offsetBy: numericCast((bounds.upperBound.id - bounds.lowerBound.id) - 1), limitedBy: endIndex)!
            if let beforeLowerBound = previous {
                removeNodes(fromAfter: beforeLowerBound, upThrough: high)
            } else {
                truncateHead(retainingAfter: high)
            }
        }
    }

    @discardableResult
    public func removeFirst() -> Element {
        defer { removeFirst(1) }
        return sentinel.next.value!
    }

    public func removeFirst(_ n: Int) {
        guard n != 0 else { return }

        let lastElementToRemoveIndex = index(startIndex, offsetBy: n - 1, limitedBy: endIndex)!
        truncateHead(retainingAfter: lastElementToRemoveIndex)
    }

    public func removeAll(keepingCapacity keepCapacity: Bool = false) {
        indices.map { $0.node }.forEach { $0.next = nil }
        tail = sentinel
        tail.next = sentinel
    }

    public func replaceSubrange<C: Collection>(_ subrange: Range<Index>, with newElements: C) where C.Element == Element {
        if newElements.isEmpty {
            removeSubrange(subrange)
        } else if subrange.isEmpty {
            insert(contentsOf: newElements, at: subrange.lowerBound)
        } else {
            precondition(subrange.lowerBound.list! === self)
            precondition(subrange.upperBound.list! === self)
            precondition(subrange.lowerBound <= subrange.upperBound)

            let newNodes = SinglyLinkedList(newElements)
            let previous = subrange.lowerBound == startIndex ? nil : index(startIndex, offsetBy: numericCast(subrange.lowerBound.id - 1), limitedBy: endIndex)!
            if subrange.upperBound == endIndex {
                if let beforeLowerBound = previous {
                    truncateTail(cuttingOffAfter: beforeLowerBound)
                    appendNodes(stealingFrom: newNodes)
                } else {
                    swap(&sentinel, &newNodes.sentinel)
                    swap(&tail, &newNodes.tail)
                }
            } else {
                let high = index(subrange.lowerBound, offsetBy: numericCast((subrange.upperBound.id - subrange.lowerBound.id) - 1), limitedBy: endIndex)!
                if let beforeLowerBound = previous {
                    removeNodes(fromAfter: beforeLowerBound, upThrough: high)
                    insertNodes(after: beforeLowerBound, stealingFrom: newNodes)
                } else {
                    truncateHead(retainingAfter: high)
                    prependNodes(stealingFrom: newNodes)
                }
            }
        }
    }

    // MARK: Custom Linked-List Stuff

    /// The last element of the list, or `nil` when the list is empty.
    public var last: Element? { return tail.value }

    /**
     Transfers the elements from the given list to the end of the receiver.

     The elements from `other` are not copied; their corresponding nodes are moved.  The newly-attached elements keep their relative order.  The indexes of the originally-present elements are not invalidated.

     - Precondition: `other` and `self` are distinct.

     - Parameter other: The source of the new elements.

     - Postcondition:
        - `self.elementsEqual(oldSelf + other)`.
        - `other.isEmpty`.
     */
    public func appendNodes(stealingFrom other: SinglyLinkedList) {
        precondition(other !== self)
        guard !other.isEmpty else { return }

        tail.next = other.sentinel.next
        tail = other.tail
        tail.next = sentinel
        other.tail = other.sentinel
        other.tail.next = other.sentinel
    }

    /**
     Removes the elements after a given index, transferring them to a new list.

     The elements going to the returned list are not copied; their corresponding nodes are moved.  Within each list, elements keep their relative order.  The indexes of the elements that are staying are not invalidated.

     - Precondition: `i` is a valid index and points to an element within `self`.

     - Parameter i: The index of the last element to stay with `self`.  All trailing elements are moved to the returned list.

     - Returns: The elements that were originally in `self`, but after `i`.

     - Postcondition: `oldSelf.elementsEqual(self + returnValue)`.
     */
    @discardableResult
    public func truncateTail(cuttingOffAfter i: Index) -> SinglyLinkedList {
        precondition(i.list! === self)
        precondition(i < endIndex)
        guard i.node !== tail else { return SinglyLinkedList() }

        let result = SinglyLinkedList()
        result.sentinel.next = i.node.next
        result.tail = tail
        tail = i.node
        tail.next = sentinel
        result.tail.next = result.sentinel
        return result
    }

    /**
     Removes the elements up to and including a given index, transferring them to a new list.

     The elements going to the returned list are not copied; their corresponding nodes are moved.  Within each list, elements keep their relative order.  All indexes to all elements, no matter which list each ends up in, are invalidated.  This includes `i` being invalidated after the method returns.

     - Precondition: `i` is a valid index and points to an element within `self`.

     - Parameter i: The index of the last element to be removed from `self`.  All leading elements are also moved to the returned list.

     - Returns: The elements that were originally in `self`, from `startIndex` up to and including `i`.

     - Postcondition: `oldSelf.elementsEqual(returnValue + self)`.
     */
    @discardableResult
    public func truncateHead(retainingAfter i: Index) -> SinglyLinkedList {
        let oldTail = truncateTail(cuttingOffAfter: i)
        swap(&sentinel, &oldTail.sentinel)
        swap(&tail, &oldTail.tail)
        return oldTail
    }

    /**
     Transfers the elements from the given list to the start of the receiver.

     The elements from `other` are not copied; their corresponding nodes are moved.  The newly-attached elements keep their relative order.  All indexes to all elements, no matter their original list, are invalidated.

     - Precondition: `other` and `self` are distinct.

     - Parameter other: The source of the new elements.

     - Postcondition:
        - `self.elementsEqual(other + oldSelf)`.
        - `other.isEmpty`.
     */
    public func prependNodes(stealingFrom other: SinglyLinkedList) {
        // Prepending an empty list should be a no-op.
        precondition(other !== self)
        guard !other.isEmpty else { return }

        // Reuse the appending code.  Reverse who keeps the nodes.
        other.appendNodes(stealingFrom: self)
        swap(&sentinel, &other.sentinel)
        swap(&tail, &other.tail)
    }

    /**
     Transfers the elements from the given list to the receiver after the given position.

     The elements from `other` are not copied; their corresponding nodes are moved.  The newly-inserted elements keep their relative order.  The indexes for the elements that are already in `self` from `startIndex` up to and including `i` are not invalidated; all other indexes are.

     - Precondition:
        - `i` is a valid index and points to an element within `self`.
        - `other` and `self` are distinct.

     - Parameter i: The index of the last element of the prefix half of `self` before insertion.
     - Parameter other: The source of the new elements.

     - Postcondition:
        - `self.elementsEqual(oldSelf1.truncateHead(retainingAfter: i) + other + oldSelf2.truncateTail(cuttingOffAfter: i))`.
        - `other.isEmpty`.
     */
    public func insertNodes(after i: Index, stealingFrom other: SinglyLinkedList) {
        precondition(i.list! === self)
        precondition(i < endIndex)
        guard i.node !== tail else { appendNodes(stealingFrom: other) ; return }
        guard !other.isEmpty else { return }

        other.tail.next = i.node.next
        i.node.next = other.sentinel.next
        other.tail = other.sentinel
        other.tail.next = other.sentinel
    }

    /**
     Removes the elements from the given half-closed interval, transferring them to a new list.

     The elements going to the returned list are not copied; their corresponding nodes are moved.  Within each list, elements keep their relative order.  The indexes for the elements from `startIndex` up to and including `s` are not invalidated; all other indexes are.

     Unlike Swift's usual half-open intervals, which include the first bound but exclude the second, this method uses a "half-closed" interval that excludes the first bound but includes the second.  An empty interval can still be made by making `s == e`.

     - Precondition:
        - `s` and `e` are valid indexes and point to elements within `self`.
        - `s <= e`.

     - Parameter s: The index of the last element of the prefix half of `self` before extraction.
     - Parameter e: The index of the last element of the extracted section.  The suffix half of `self` starts with the following element.

     - Returns: The elements that were originally in `self`, from after `s` up to and including `e`.

     - Postcondition: `oldSelf.elementsEqual(self1.truncateHead(retainingAfter: s) + returnValue + self2.truncateTail(cuttingOffAfter: s))`.
     */
    @discardableResult
    public func removeNodes(fromAfter s: Index, upThrough e: Index) -> SinglyLinkedList {
        precondition(s.list! === self)
        precondition(e.list! === self)
        precondition(s <= e)
        precondition(e < endIndex)
        guard s < e else { return SinglyLinkedList() }
        guard e.node !== tail else { return truncateTail(cuttingOffAfter: s) }

        let result = SinglyLinkedList()
        result.sentinel.next = s.node.next
        result.tail = e.node
        s.node.next = e.node.next
        result.tail.next = result.sentinel
        return result
    }

    /**
     Splices elements from a given list into the receiver.

     Sends the first element of `self` and `other` to an ordering closure, which decides which element should be the next to follow in the merged list.  Then the loop repeats with the same element from the losing list and the next element from the winning list.  When one list ends, all the remaining elements of the other are appended.  All indexes of both lists are invalidated.  Elements from the same source list keep their relative order.

     - Precondition: `other` and `self` are distinct.

     - Parameter other: The source of the new elements.
     - Parameter body: The choosing function.  Elements of the receiver are fed as the first argument, elements of `other` are fed as the second argument.  The closure should return `true` if the first argument should be reinserted before the second argument is inserted, or `false` for vice versa.

     - Postcondition:
        - `self.count == oldSelf.count + other.count`.
        - `other.isEmpty`.
     */
    func merge(stealingFrom other: SinglyLinkedList, chooseFirstOverSecond body: (Element, Element) throws -> Bool) rethrows {
        // Insert each node from the two lists into the master list, letting the closure choose the order.
        var selfNode = sentinel.next!, otherNode = other.sentinel.next!
        var nodes = [Node]()
        while selfNode !== sentinel, otherNode !== other.sentinel {
            if try body(selfNode.value!, otherNode.value!) {
                nodes.append(selfNode)
                selfNode = selfNode.next!
            } else {
                nodes.append(otherNode)
                otherNode = otherNode.next!
            }
        }

        // Append the rest when one list ends before the other.
        while selfNode !== sentinel {
            nodes.append(selfNode)
            selfNode = selfNode.next!
        }
        while otherNode !== other.sentinel {
            nodes.append(otherNode)
            otherNode = otherNode.next!
        }

        // Update the receiver to hold the master list.
        appendNodes(stealingFrom: other)
        zip(nodes.dropLast(), nodes.dropFirst()).forEach { $0.0.next = $0.1 }
        tail = nodes.last ?? sentinel
        sentinel.next = nodes.first ?? sentinel
        tail.next = sentinel
    }

}

extension SinglyLinkedList: ExpressibleByArrayLiteral {

    public convenience init(arrayLiteral elements: Element...) {
        self.init(elements)
    }

}

extension SinglyLinkedList: CustomDebugStringConvertible {

    public var debugDescription: String {
        // ========== WARNING ==========
        // My playground choked on this, since this property is repeatedly called to print out the sidebar strings.
        // I guess it's too computationally heavy.  If you crash on your first object, replace this code with a short string literal.
        var elementStrings = indices.map { $0.node }.map { "\(Unmanaged.passUnretained($0).toOpaque()): \($0.value!)" }
        elementStrings.append(String(describing: Unmanaged.passUnretained(sentinel).toOpaque()))
        return "\(type(of: self))[\(elementStrings.joined(separator: "; "))]"
    }

}

extension SinglyLinkedList: CustomStringConvertible {

    public var description: String {
        return String(describing: Array(self))
    }

}