Deque

Deque is the short form of double-ended queue. It allows fast removal and insertion at both ends but can still be indexed like a normal array.

While most .NET developers simply use .NET's LinkedList class or write a small facade to make it look like a deque, the original deque data structure implemented by the C++ standard library is pretty interesting because it uses multiple arrays to combine many of the advantages an array has with that of a linked list:

+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
|  | 1| 2| 3| ~ | 4| 5| 6| 7| ~ | 8| 9|10|11| ~ |12|13|  |  |
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

When items are removed from the beginning, it simply increments the start index in the first array. If the first array becomes empty, the array is dropped and the former second array becomes the new first array.

When items are added to beginning or the end, should the array on that side of the deque become full, the deque only needs to add a new array, whereas a List would have to allocate a new (larger) array and copy all its items over into the new array.

Benchmarks

Here are some benchmarks that compare .NET's built-in collection classes against the deque. You might be surprised how much of an advantage a little hand-coding can provide versus the supposedly heavily optimized .NET classes:
  • 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

Last edited Sep 23, 2009 at 1:16 PM by Cygon, version 8

Comments

No comments yet.