Hmm,... for a linked list, each node (which would be a class) would have an Int (or similar) ID, and the main body of the list would have an internal [Int: Node] property to index all of its nodes. The list's Index would be those key IDs. It's up to the list to make sure all IDs are strictly increasing whenever a RangeReplaceableCollection or a custom equivalent event occurs, which may involve recalculating all indexes.
Maybe something similar for search trees? (I have to find out what they are first.)
Ooh, time to get distracted from my BigInt obsession for a Linked-List one.