0

Are deques (double-ended queues) traversable data structures? Does it make a difference whether they are have an array-based implementation vs linked implementation?

labronzo
  • 1
  • 2
  • 1
    If you're programming oriented to interfaces, then you won't really care if the deque is backed by an array, a linked list or any other structure. And yes, they're traversables. – Luiggi Mendoza Oct 21 '14 at 05:32

3 Answers3

0

Yes, deques is traversable data structure, you can get interator from deque for traversing. Functionally, It does not make difference. But, technically and data structure wise, it make a difference. Remember, when we are using list we can add node dynamically. But, when using array, we need to define the size of deque or default size is used. Now, if you insert another element then it will create new array of double size and copy old array into new array then insert the new element.

Pavan
  • 121
  • 4
0

Yes, they are traversable. Especially in JAVA Deque API, you can always get either iterator (or) descendingIterator to traverse the Deque either from first to last (or) from last to first respectively.

For just traversing the Deque, the underlying implementation may not make much difference. But for other operations it does. People usually prefer ArrayDeque over LinkedList. For more information on this follow the thread Why is ArrayDeque better than LinkedList.

Also look at the corresponding JAVA APIs to get the major differences between these two different implementations.

Community
  • 1
  • 1
Nagakishore Sidde
  • 2,617
  • 1
  • 16
  • 9
0

No. Like the structures it is a hybrid of (i.e., stacks and queues), deques (or double-ended queues) are not designed to be traversable. In fact, they are specifically designed not to be traversable. If the capability of traversing items contained within is necessary for a particular application, then a dequeue is probably not the best data structure to use in that case.

Ezra Justin Lee
  • 81
  • 6