Conforming Linked List to the Collection protocol

Question

I'm looking at the Linked List implementation from here, and it shows how the class conforms to the Collection protocol:

extension LinkedList: Collection {
    
    public typealias Index = LinkedListIndex<T>

    public var startIndex: Index {
        get {
            return LinkedListIndex<T>(node: head, tag: 0)
        }
    }
    
    public var endIndex: Index {
        get {
            if let h = self.head {
                return LinkedListIndex<T>(node: h, tag: count)
            } else {
                return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
            }
        }
    }
    
    public subscript(position: Index) -> T {
        get {
            return position.node!.value
        }
    }
    
    public func index(after idx: Index) -> Index {
        return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag + 1)
    }
}

In order to conform to the Collection protocol, the code provided three things: startIndex/endIndex, read-only subscript to get an element, and index(after:).

And order to make this possible, the code also provided LinkedListIndex which is a wrapper object of the linked list in question to make it conform to Comparable:

public struct LinkedListIndex<T>: Comparable {
    fileprivate let node: LinkedList<T>.LinkedListNode<T>?
    fileprivate let tag: Int
    
    public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
        return (lhs.tag == rhs.tag)
    }
    
    public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
        return (lhs.tag < rhs.tag)
    }
}

I have two questions:

1. Why do the elements have to conform to Comparable? Unlike firstIndex(of:), which requires the elements to be Equatable, I can't seem to find anything on Apple documentation about needing to conform to Comparable, or even Equatable, for things like startIndex.
2. How do these tags refer to a specific node? I'm not quite understanding the association between this arbitrary property tag and index.

Testing

final class LinkListTest: XCTestCase {
    func test_linkedList() {
        let linkedList = LinkedList<Int>()
        for i in stride(from: 0, to: 100, by: 10) {
            linkedList.append(i)
        }
        
        let startIndex = linkedList.startIndex // startIndex has a tag of 0 because that's how it was instantiated
        let expectedStartIndex = LinkedListIndex<Int>(node: linkedList.head, tag: 0)
        XCTAssertEqual(startIndex, expectedStartIndex)
        
        let endIndex = linkedList.endIndex // endIndex also has a tag of the count because that's how it was instantiated
        let expectedEndIndex = LinkedListIndex<Int>(node: linkedList.last, tag: 10)
        XCTAssertEqual(endIndex, expectedEndIndex)
        
        let node = LinkedList.Node(value: 50)
        let testIndex = linkedList.index(after: LinkedListIndex<Int>(node: node, tag: 50))
        print("testIndex", testIndex) // LinkedListIndex<Int>(node: nil, tag: 51)
    }
}

There is no iteration going through every node and associating it with LinkedListIndex to say node C has a tag of 3, D has a tag of 4. How does index(after:) know which node comes after LinkedListIndex<Int>(node: node, tag: 50)?

Answer 1

Based on the code you show:

1. It's not the linked list elements which are Comparable, but the indices. Collection has no Comparable requirement on its elements, but does require that its indexes be comparable so that they can be reasonably ordered:

   public protocol Collection: Sequence {
     // FIXME: ideally this would be in MigrationSupport.swift, but it needs
     // to be on the protocol instead of as an extension
     @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int")
     typealias IndexDistance = Int  
   
     // FIXME: Associated type inference requires this.
     override associatedtype Element
   
     /// A type that represents a position in the collection.
     ///
     /// Valid indices consist of the position of every element and a
     /// "past the end" position that's not valid for use as a subscript
     /// argument.
     associatedtype Index: Comparable
   
     // ...
   }
   

   This requirement on the indices makes it possible to iterate over the Collection one index at a time, and know where you are relative to startIndex and endIndex.

   Note too that the syntax

   public struct LinkedListIndex<T>: Comparable
   

   does not make LinkedList Comparable itself, and only declares that LinkedListIndex is Comparable. Note that it does not reference the original list itself, but holds on to a node for constant-time access back within LinkedList itself: but this implementation detail does not have to do with Comparable conformance, nor does it affect it.

2. It appears that LinkedListIndex.tag represents the index of the element in the list, like an array index: the first element (startIndex) has a tag of 0, the second element has a tag of 1, etc.; endIndex (the index once past the last element in the list) has an index of count

   You can use an index to iterate tag times through the list to access a specific element. This iteration isn't strictly necessary, though, because a LinkedListIndex also contains a pointer to the node it's supposed to refer to in the list, as a shortcut.

---

Update with additional question:

How does index(after:) know which node comes after LinkedListIndex(node: node, tag: 50)?

This is achieved using two things:

1. Alongside the tag, LinkedListIndex values contain a pointer to the node that they reference in the original list:

   public struct LinkedListIndex: Comparable { fileprivate let node: LinkedList.LinkedListNode? fileprivate let tag: Int }

   This is set at the time that the index is created in:

   • LinkedList.startIndex
   • LinkedList.endIndex
   • LinkedList.index(after:)

2. The implementation of LinkedList.index(after:) uses this node reference in its implementation:

   public func index(after idx: Index) -> Index {
       return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag + 1)
   }
   

   The index which comes after idx is an index which:

   • Points to the node after idx.node, and
   • Has a tag which is one past idx.tag

There is no further association between a node and a tag:

• The tag appears to be used exclusively for Comparable conformance for indices, as a way to avoid having to compare nodes (e.g., LinkedListIndex trusts that if idx1.tag < idx2.tag then presumably idx1.node comes before idx2.node in the list, even if this is not the case!), while
• The node is the only thing really consulted when subscripting, and when producing new indices

Because the nodes and tags are only very loosely related in this way, this code isn't terribly robust against mismatches (e.g. if I edit the list while you hold on to an index, the index's tag may be out of date depending on the operation I perform!).