Deque

What is it?

A C# Generic Deque class implemented in .NET 2.0 with no dependencies. Deques have constant time insertion and removal from either end. This implementation is a circular-array backed Deque class to the System.Collections.Generic namespace. The tradeoff over a doubly-linked-list backed Deque is that arbitrary access into the deque is constant time, but arbitrary insertion into the deque is O(n), whereas a doubly-linked-list backed deque is the opposite.

More information about Deques can be found here: http://en.wikipedia.org/wiki/Double-ended_queue

How can I get it?

Deque is available as a NuGet package: https://nuget.org/packages/Deque/

PM> Install-Package Deque

Why was it made?

The Deque data structure is not part of the C# Standard Library, but it is nonetheless an incredibly useful data structure.

Performance Benchmarks

This implementation of Deque was made to be highly performant, and uses several optimizations. Below are the results of benchmarks taken from several built-in .NET data structures compared to the Deque class, it can be seen that the Deque class is on par with them performance wise.

Without preallocating space

With preallocating space

Methods

public Class Deque<T> : IList<T>
{
    public void Add;
    public void AddFront(T item);
    public void AddBack(T item);
    public void AddRange(IEnumerable<T> collection);
    public void AddFrontRange(IEnumerable<T> collection);
    public void AddFrontRange(IEnumerable<T> collection, int fromIndex, int count);
    public void AddBackRange(IEnumerable<T> collection);
    public void AddBackRange(IEnumerable<T> collection, int fromIndex, int count);

    public bool Contains(T item);
    public void CopyTo(T[] array, int arrayIndex);
    public int Count;

    public int IndexOf(T item);
    public void Insert(int index, T item);
    public void InsertRange(int index, IEnumerable<T> collection);
    public void InsertRange(int index, IEnumerable<T> collection, int fromIndex, int count);

    public void Remove(int index);
    public T RemoveFront();
    public T RemoveBack();
    public void RemoveRange(int index, int count);

    public T Get(int index);
    public void Set(int index, T item);

    public T this[index];
}