XOR lists are obscure and cursed but cool. And not useful on modern hardware as the CPU can’t predict access patterns. They date from a time when every byte of memory counted and CPUs didn’t have pipelines.

(In general, all linked lists or trees are terrible for performance on modern CPUs. Prefer vectors or btrees with large fanout factors. There are some niche use cases still for linked lists in for example kernels, but unless you know exactly what you are doing you shouldn’t use linked data structures.)

EDIT: Fixed spelling

Not really a data structure per say, but just knowing LISP and the interesting structures it uses internally.

The results of LISP operations CAR, CDR, CADR and the other one I can’t remember now.

The CSR (compressed sparse row) format is a very simple but efficient way of storing sparse matrices, meaning matrices with a large amount of zero entries, which should not all occupy memory. It has three arrays: one holds all non-zero entries in order, read row by row, the next array contains the column indices of each non-zero element (and therefore has the same length as the first array), the third array indices into the first array for the first element of each row, so we can tell where a new row starts.

On sparse matrices it has optimal memory efficiency and fast lookups, the main downside is that adding or removing elements from the matrix requires shifting all three arrays, so it is mostly useful for immutable data.

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.

B trees are cool but not obscure necessarily. I didn’t learn about them in college. It sounds like binary tree and it’s similar but it’s different. It’s a data structure to take advantage of the way disk reads work.

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.

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

I get way more use out of Doubly Connected Edge Lists (DCEL) than I ever thought I would when I first learned about them in school.

When I want to render simple stuff to the screen, built-in functions like ‘circle’ or ‘line’ work. But for any shapes more complicated than that, I often find that it’s useful to work with the data in DCEL form.

I’ve been knee-deep in these lately so I’m a big fan

Theta sketches!

Do you want to approximately count a large volume of items, but save the state for later so you can UNION , INTERSECT and even DIFF them? Then Thetas are right for you!

Or basically anything in the Apache Datasketches lbrary.

Not exactly a datastructure alone, but bitslicing is a neat trick to turn some variable-time operations into constant-time operations. Used in cryptography for “substitution box” (S-box) operations, which can otherwise leak secrets via data-dependent timing variations.

The datastructure side of it is breaking up n words into bits and interleaving them within n variables (usually machine registers), so that the first variable contains the first bit from each word, the second variable the second bit, etc. It’s also called “SIMD within a register”.

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.

skiplists are interesting data structures. The underlying mechanism is it’s a 2-dimensional probabilistic linked list with some associated height ‘h’ that enables skipping of nodes through key-value pairs. So, compared to a traditional linked list that uses a traversal method to search through all values stored. A skip list starts from the maxLevel/maxheight, determines if “next” points to a key greater than the key provided or a nullptr, and moves down to the level below it if it is. This reduces the time complexity from O(1) with a linked list to O(N) where N Is the maxLevel.

The reason behind why its probabilistic (in this case using a pseudo random number) is because its easier to insert and remove elements, otherwise (if you went with the idealized theoretical form) you would have to reconstruct the entire data structure each and every time you want to add/remove elements.

In my testing when adding 1,000,000 elements to a skiplist it reduced from 6s search with a linked list to less than 1s!

An ultimately doomed one that existed in Perl for a while was the pseudohash. They were regular integer-indexed arrays that could be accessed as though they were hashes (aka associative arrays / dictionaries). They even made it into the main Perl books at the time as this awesome time saving device. Except they weren’t.

I did a quick web search just now and someone did a talk about why they weren’t a great idea and they tell it better than I could; Link: https://perl.plover.com/classes/pseudohashes/

The supplied video doesn’t have great sound quality, and it might be better to just click through the slides under Outline at the bottom there.

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

Locality Sensitive Hashing. Not sure if it’s more algorithm than data structure, or even if it’s obscure, but it is very cool.