" I can't imagine anything else you can possibly store about relative elements besides index and order (and nothing). Graphs are their own other planet, and I don't think we can easily say much about them. So the 3 data structure types you can have are:<p>1. indexed data structures with an O(n) worst-case operation<p>2. order-less data structures with an O(1) worst-case operation<p>3. sorted data structures with an O(log n) worst-case operation<p>That's it. Let me know what you think"<p>I disagree.<p>sorting is a O(n*log(n)) worst-case operation for example.