.NET implementation of one of the most useful data structures in the C++ library, the "deque". Fast when adding or removing items at both the beginning and the end, doesn't need to copy its while contents into a new array when expanding in size and can be indexed like an array. Beats LinkedList<> in any category - click on details to view the benchmarks.

Details

One of the coolest data structures in the standard C++ library is the "deque". It keeps items close together like an array, which improves cache efficiency and like a linked list, it doesn't need to copy all its items when it is enlarged beyond its current capacity. But despite this, it can be accessed by index like an array. It also supports fast removal or insertion of items both at the beginning and at the end of it and is thus usable as a stack or a queue.

Sadly, the deque data structure is missing in the .NET collection classes.

I discovered some deque implementations on the web, but those all seemed to be simple wrappers around .NET's LinkedList<> class and not actual implementations of the deque data structure. So I decided to amend this situation:

Deque<string> strings = new Deque<string>();

// Adding to the end of a deque is fast. Even if the deque's block size is
// exceeded, unlike a List<> it doesn't need to copy its contents, so even
// in this case the spike is manageable.
for(int index = 0; index < 1024; ++index) {
  strings.AddLast("World");
}

// Adding to the beginning of a deque is also fast. The items do not have to
// be copied around in memory.
for(int index = 0; index < 1024; ++index) {
  strings.AddFirst("Hello");
}

// The deque can be very efficiently processed from one end to the other
while(strings.Count > 0) {
  Console.Write(strings.First);
  strings.RemoveFirst();
}

The deque is slightly slower than a List<> at some operations (accessing items by index, adding items with enough capacity remaining, removing items close to the middle) but eliminates most of the weak points of the List<> compared to the LinkedList<> class.

Features

• Fully implements the IList<> and IList interfaces
• Unit-tested code with 100% test coverage
• Efficient implementation and lightning-fast enumerators

Benchmarks

Update: I've written some benchmarks that test my Deque versus .NET's List<> and LinkedList<> classes. Here are the results (each measured with 250,000 items)

List<>

Appending to the end: 4 ms
Appending at the beginning: 70,579 ms
Random insertion by index: 28,390 ms
Removal of first item: 69,065 ms
Removal of last item: 3 ms

LinkedList<>

Appending to the end: 19 ms
Appending at the beginning: 28 ms
Random insertion by index: 439,024 ms (*not directly supported)
Removal of first item: 6 ms
Removal of last item: 5 ms

Deque<>

Appending to the end: 6 ms
Appending at the beginning: 4 ms
Random insertion by index: 16,144 ms
Removal of first item: 3 ms
Removal of last item: 4 ms

The Deque class is part of the Nuclex.Support library from the Nuclex Framework. You can find the most recent release of the code on the framework's CodePlex site: http://nuclexframework.codeplex.com/