How to return an index in constant time?

Question

According to Swift Documentation according to protocol Collection:

It is assumed that the types corresponding to the collection will provide the properties startIndex and endIndex and subscript access to elements as O (1) operations.

How to return an index in constant time? Is it not necessary to iterate through the collection, right down to the correct index, and then return that value?

This is the LinkedList that I use to match Collection:

indirect enum LinkedList<T> {
    case value(element: T, next: LinkedList<T>)
    case end
}

extension LinkedList: Sequence {
    func makeIterator() -> LinkedListIterator<T> {
        return LinkedListIterator(current: self)
    }
    var underestimatedCount: Int {
        var count = 0
        for _ in self {
            count += 1
        }
        return count
    }
}

struct LinkedListIterator<T>: IteratorProtocol {
    var current: LinkedList<T>
    mutating func next() -> T? {
        switch current {
        case let .value(element, next):
            current = next
            return element
        case .end:
            return nil
        }
    }
}

And here I really agree with the protocol:

extension LinkedList: Collection {

    typealias Index = Int
    typealias Element = T

    var startIndex: Index {
        return 0
    }
    var endIndex: Index {
        return underestimatedCount
    }
    func index(after i: Index) -> Index {
        return (i < endIndex) ? i + 1 : endIndex
    }
    subscript (position: Index) -> Element {
        precondition(position < endIndex && position >= startIndex)
        var iterator = makeIterator()
        for i in 0 ..< position {
            iterator.next()
            if i + 1 == position {
                return iterator.next()!
            }
        }
        var zero = makeIterator()
        return zero.next()!
    }

}

let test = LinkedList<Int>.value(element: 2, next: LinkedList<Int>.value(element: 4, next: LinkedList<Int>.value(element: 7, next: LinkedList<Int>.value(element: 9, next: LinkedList<Int>.end))))

Answer 1

Index Int. , . , .

. , , , , .

class ListNode node, , , integer ordinal, struct ListIndex Comparable.

struct ListIndex node nil endIndex.

struct LinkedListCollection<T>: Collection {

    class ListNode {
        let element: T
        let next: ListNode?
        let ordinal: Int

        init(element: T, next: ListNode?, ordinal: Int) {
            self.element = element
            self.next = next
            self.ordinal = ordinal
        }

        // Create ListNode as the head of a linked list with elements from an iterator.
        convenience init?<I: IteratorProtocol>(it: inout I, ordinal: Int = 0) where I.Element == T {
            if let el = it.next() {
                self.init(element: el, next: ListNode(it: &it, ordinal: ordinal + 1), ordinal: ordinal)
            } else {
                return nil
            }
        }
    }

    struct ListIndex: Comparable {
        let node: ListNode?

        static func <(lhs: ListIndex, rhs: ListIndex) -> Bool {
            // Compare indices according to the ordinal of the referenced
            // node. `nil` (corresponding to `endIndex`) is ordered last.

            switch (lhs.node?.ordinal, rhs.node?.ordinal) {
            case let (r?, l?):
                return r < l
            case (_?, nil):
                return true
            default:
                return false
            }
        }

        static func ==(lhs: ListIndex, rhs: ListIndex) -> Bool {
            return lhs.node?.ordinal == rhs.node?.ordinal
        }
    }

    let startIndex: ListIndex
    let endIndex: ListIndex

    // Create collection as a linked list from the given elements.
    init<S: Sequence>(elements: S) where S.Iterator.Element == T {
        var it = elements.makeIterator()
        startIndex = ListIndex(node: ListNode(it: &it))
        endIndex = ListIndex(node: nil)
    }

    func index(after i: ListIndex) -> ListIndex {
        guard let next = i.node?.next else {
            return endIndex
        }
        return ListIndex(node: next)
    }

    subscript (position: ListIndex) -> T {
        guard let node = position.node else {
            fatalError("index out of bounds")
        }
        return node.element
    }
}

:

let coll = LinkedListCollection(elements: [1, 1, 2, 3, 5, 8, 13])
for idx in coll.indices {
    print(coll[idx])
}