/*
 * definition
 */
indirect enum LinkedList<T> : Sequence {

    case end
    case node(value: T, next: LinkedList<T>)

    init() {
        self = .end
    }

    init(value: T) {
        self = .node(value: value, next: .end)
    }

    mutating func push(_ item: T) {
        self = .node(value: item, next: self)
    }

    mutating func pop() -> T? {
        switch self {
        case .end:
            return nil
        case .node(let value, let next):
            self = next
            return value
        }
    }

    func makeIterator() -> LinkedList<T>.Iterator {
        return Iterator(self)
    }
    
    struct Iterator : IteratorProtocol {
        typealias Element = T
        private var list: LinkedList<Element>
        init(_ list: LinkedList<Element>) {
            self.list = list
        }

        mutating func next() -> LinkedList<T>.Iterator.Element? {
            switch self.list {
            case .end:
                return nil
            case .node(let value, let nextList):
                self.list = nextList
                return value
            }
        }
    }
}

/*
 * usages
 */

var linked = LinkedList<String>(value: "first")
linked.push("second")
print(linked)

for v in linked {
    print(v) // second, first
}

if let value = linked.pop() {
    print(value) // second
}

for v in linked {
    print(v) // first
}