LinkedList.swift

import Foundation

indirect enum LinkedList<Element> {
    case node(element: Element, next: LinkedList)
    case end
    
    init<S: Sequence>(values: S, last: LinkedList = .end) where S.Element == Element {
        self = values.reversed().reduce(last, { .node(element: $1, next: $0) })
    }
    
    init(_ values: Element...) {
        self.init(values: values)
    }
    
    func dequeue(_ element: Element) -> (Element?, LinkedList) {
        switch self {
        case let .node(element: element, next: next):
            return (element, next)
        case .end:
            return (nil, self)
        }
    }
    
    func appending(_ element: Element) -> LinkedList {
        return LinkedList(values: self, last: .node(element: element, next: .end))
    }
    
    var first: Element? {
        switch self {
        case let .node(element, _):
            return element
        case .end:
            return nil
        }
    }
    
    var last: Element? {
        return suffix(1).first { _ in true }
    }
}

extension LinkedList: Sequence {
    func makeIterator() -> AnyIterator<Element> {
        var current = self
        return AnyIterator { () -> Element? in
            switch current {
            case let .node(element, next):
                current = next
                return element
            case .end:
                return nil
            }
        }
    }
}

extension LinkedList: CustomStringConvertible {
    var description: String {
        return ["[", map(String.init(describing:)).joined(separator: ", "), "]"].joined()
    }
}