import Foundation

public class LinkedList<T: Any> {

    let head: T

    let tail: LinkedList<T>?

    init(head: T, tail: LinkedList<T>? = nil) {

        self.head = head

        self.tail = tail

    }

    public var count: Int {

        if let tail = tail {

            return 1 + tail.count

        } else {

            return 1

        }

    }

}

extension LinkedList: Collection where T: Any {

    public typealias Element = T

    public typealias Index = Int

    public subscript(position: Index) -> Element {

        if position < 0 {

            fatalError("negative index: \(position)")

        } else if position == 0 {

            return head

        } else if let tail = tail {

            return tail[position - 1]

        } else {

            fatalError("index out of range: \(position)")

        }

    }

    public var startIndex: Int {

        return 0

    }

    public var endIndex: Int {

        // Important: do not subtract 1

        return count

    }

    public func index(after i: Int) -> Int {

        return i + 1

    }

}