Is there sparse array implementation in .NET library?

Question

Is there already implemented data structure in .NET library acting like sparse array (where most indexes are empty) with O(1) access by index and O(1) access to next (and previous) element?

Answer 1

A couple of years ago I implemented a sparse collection based on my "AList" concept. It's called SparseAList, and it's probably better than any "simple" solution that you might roll yourself. For example, @NathanPhilips' solution has Insert and RemoveAt methods that call ToDictionary. Enumerable.ToDictionary is an O(N) method - it regenerates the whole dictionary "from scratch" - so it's not efficient.

SparseAList, by contrast, is based on the B+ tree, so it has efficient O(log N) insertions, lookups and removals, and it also uses memory efficiently. It is included in Loyc.Collections.dll in LoycCore, available on NuGet (search for Loyc.Collections).