Skew binary trees. They’re an immutable data structure combining the performance characteristics of lists (O(1) non-amortized push/pop) and b-trees (log(N) lookup and updates)
They use a sequence of complete trees, cleverly arranged using skew binary numbers so that adding an element never causes cascading updates.
In practice they’re superseded by relaxed radix balanced trees.

@protein

Finger Tree!

A persistent, purely functional workhorse. Amortized O(1) access at both ends, O(log n) concatenation/splitting.

It generalizes elegantly to build sequences, priority queues, and more. Powers Haskell’s main Data.Sequence. A functional programmer’s secret weapon.

Not necessarily obscure, but I don’t think Tries get enough love.

Edit: I can’t spell

Fibonacci heaps are pretty cool. Not used very often b/c they’re awful to implement, but better complexity than many other heaps.

Also Binary Lifting is closer to an algorithm than a data structure but it’s used in Competitive Programming a fair bit, and isn’t often taught: https://cp-algorithms.com/graph/lca_binary_lifting.html

And again closer to an algo tham a data structure, but Sum over Subsets DP in 3^n also has a cool little bit of math in it: https://cp-algorithms.com/algebra/all-submasks.html

How about this variation of linked lists? https://www.data-structures-in-practice.com/intrusive-linked-lists/

I personally don’t think it’s that obscure but I have never seen this used in production code that I didn’t write: the linked hash map or ordered hash map.

I came up with a kind of clever data type for storing short strings in a fixed size struct so they can be stored on the stack or inline without any allocations.
It’s always null-terminated so it can be passed directly as a C-style string, but it also stores the string length without using any additional data (Getting the length would normally have to iterate to find the end).
The trick is to store the number of unused bytes in the last character of the buffer. When the string is full, there are 0 unused bytes and the size byte overlaps the null terminator.
(Only works for strings < 256 chars excluding null byte)

Implementation in C++ here: https://github.com/frustra/strayphotons/blob/master/src/common/common/InlineString.hh

Edit: Since a couple people don’t seem to understand the performance impact of this vs regular std::string, here’s a demo: https://godbolt.org/z/34j7obnbs This generates 10000 strings like “Hello, World! 00001” via concatenation. The effect is huge in debug mode, but still has performance benefits with optimizations turned on:

With -O3 optimization
std::string: 0.949216ms
char[256] with strlen: 0.88104ms
char[256] without strlen: 0.684734ms

With no optimization:
std::string: 3.5501ms
char[256] with strlen: 0.885888ms
char[256] without strlen: 0.687733ms

(You may need to run it a few times to get sample numbers due to random server load on godbolt)
Changing the buffer size to 32 bytes has a negligible performance improvement over 256 bytes in this case, but might be slightly faster due to the whole string fitting in a cache line.

I’m also not sure if this is obscure, but Bloom Filters! It’s a structure that you can add elements to then ask it if it has seen the element before with the answer being either “no” or “probably yes”. There’s a trade-off between confidence of a “probably yes”, how many elements you expect to add, and how big the Bloom Filter is, but it’s very space and time efficient. And it uses hash functions which always make for a fun time.