Surprising and basic data structures I'm interested in surprising data structures that extend the things people learned in their first algorithm/data structure course. Usually by offering an additional operation at a very low cost.

I learned that one can create a dynamic array with $O(1)$ access and $O(1)$ amortized append a long time ago. I thought there is no way to remove the amortized cost. I saw a data structure only a few months ago that do both operations in $O(1)$ non-amortized time.

What are some other examples?
I would not know what you learned or did not learn, What is surprising depends a lot on who is to be surprised. So your question is pretty much undefined.

All I can do for you (but I am no expert) is to mention one technique that impressed me when I first saw it, the skip lists of William Pugh. And more generally the use of randomness and  probabilistic techniques, actually not just in algorithmics but also in "proving" or in quickly identifying things that can then be formally proved (at high computational cost) to have this or that property.