in any DSA textbook we'll find out that we have two ways to implement maps - so called "hashmaps" and and the less common "treemaps".
which makes me wonder: why are there no "linked list maps"?
reading elements would obviously be slower - O(n) vs O(log n) - but inserting can be faster if we keep a reference to the tail of the linked list - O(1) vs O(log n).
am i missing something?

>>105969755 (OP)
O(n) reads and O(1) writes are the same characteristics as a regular linked list. You're just describing a linked list of (key, value) pairs, which could be more efficiently implemented using a regular array.

>O(n) reads and O(1) writes are the same characteristics as a regular linked list. You're just describing a linked list of (key, value) pairs
yeah, obviously that's what im describing
>which could be more efficiently implemented using a regular array
no doubt about that, but im comparing it to a treemap
treemaps are wildly more inefficient than hashmaps but they're often mentioned as a data structure, why is this third variant that im describing never mentioned?
i feel like it would be the simplest implementation too, way simpler than both a treemap and a hashmap.

>>105970198
>O(n) reads and O(1) writes are the same characteristics as a regular linked list. You're just describing a linked list of (key, value) pairs
yeah, obviously that's what im describing
>which could be more efficiently implemented using a regular array
no doubt about that, but im comparing it to a treemap
treemaps are wildly more inefficient than hashmaps but they're often mentioned as a data structure, why is this third variant that im describing never mentioned?
i feel like it would be the simplest implementation too, way simpler than both a treemap and a hashmap.

>>105970425
>treemaps are wildly more inefficient than hashmaps
What kind of tree map? B-trees (and related) are only efficient when your keys are sortable.

>>105970718
BSTs

>>105970734
Of course BSTs are inefficient for most data, they are really only something studied in CS classes. B-trees are the practical version.

>>105969755 (OP)
>why are there no "linked list maps"
There are.
https://en.wikipedia.org/wiki/Association_list

>>105970772
>they are really only something studied in CS classes
This is false. Any time you need a dictionary that must be efficiently iteratable in key order then a BST is your first choice. For example, in log-structured merge trees the first stage is typically a BST. It only turns into a B-tree when its serialized out to disk.

>>105972185
Why is a BST more efficiently iterable than a B-tree?