LinkedList.swift

class LinkedList<T>: Collection {

    typealias Element = T
    typealias Index = Int
    typealias Iterator = IteratorImpl
    
    final class IteratorImpl: IteratorProtocol {
        typealias Element = T
        
        private var cursor: Node?
        
        fileprivate init(cursor: Node? = nil) {
            self.cursor = cursor
        }
        
        func next() -> T? {
            defer {
                cursor = cursor?.next
            }
            return cursor?.value
        }
        
    }
    
    final class Node {
        fileprivate(set) var value: T
        fileprivate var next: Node?
        fileprivate var prev: Node?
        
        fileprivate init(value: T, next: Node? = nil, prev: Node? = nil) {
            self.value = value
            self.next = next
            self.prev = prev
        }
    }
    
    private var _count = 0
    private var start: Node?
    private var end: Node?
    
    // Mark : Public
    
    @discardableResult
    func append(_ newElement: T) -> Node {
        let newNode = Node(value: newElement)
        newNode.prev = end
        end?.next = newNode
        
        if start === nil {
            start = newNode
        }
        
        end = newNode
        
        _count += 1
        return newNode
    }
    
    @discardableResult
    func prepend(_ newElement: T) -> Node {
        let newNode = Node(value: newElement)
        newNode.next = start
        start?.prev = newNode
        
        start = newNode
        
        if end == nil {
            end = newNode
        }
        
        _count += 1
        
        return newNode
    }
    
    var last: T? {
        end?.value
    }
    
    func moveToFront(_ node: Node) {
        guard node !== start else { return }
        
        node.prev?.next = node.next
        node.next?.prev = node.prev
        
        if node === end {
            end = node.prev
        }
        
        node.next = start
        start = node
    }
    
    func sendToBack(_ node: Node) {
        guard node !== end else { return }
        
        node.prev?.next = node.next
        node.next?.prev = node.prev
        
        if node === start {
            start = node.next
        }
        
        node.prev = end
        end = node
    }
    
    // Mark: Collection
    
    var count: Int { _count }
    var startIndex: Int { 0 }
    var endIndex: Int { _count }
    
    func makeIterator() -> IteratorImpl {
        IteratorImpl(cursor: start)
    }
    
    subscript(position: Int) -> T {
        get {
            return node(at: position)!.value
        }
        set {
            let node = node(at: position)!
            node.value = newValue
        }
    }
    
    func index(after i: Int) -> Int {
        i + 1
    }
    
    var first: T? {
        start?.value
    }
    
    
    // Mark: Private
    
    private func node(at index: Int) -> Node? {
        if index == 0 {
            return start
        }
        var cursor = start
        for _ in 0..<index {
            cursor = cursor?.next
        }
        
        return cursor
    }
}