3

As a developer everybody in their careed must have faced the requirement where you need resizable collection where you can do add, remove, retrievale(FIFO).

In every application i see using List(ArrayList) to satisy this requirement but my question why not developer go for Queue(probably ArrayDeque) . As per my current understanding i find both ArrayList(List) and ArrayDeque(Queue) equally good for the requirement i stated. But still i never spotted queue in my career , always find only List.

So my question is why not Queue is preferred over List. I am sure there must be some reason but somehow i am missing that understanding?

Update:- here is my clear requirements

1)Addition happens at end and should be fast.Probably O(1)

2)Iteration should be fast

3)lookup and removal of any specific element should be faster.

Going by above requirement i think Arralist makes sense over ArrayDeque . Here are my pointwise reason

1)Both Arraylist and ArrayDeque will be O(1) . Right?

2)Iteration performance will be same for both as it will be based on index . For ArrayDeque index will be based on timestamp whereas for arraylist user can explicitly mention index. Right?

3)It will be O(1) for both as lookup will happen based om index

M Sach
  • 33,416
  • 76
  • 221
  • 314
  • Related (i was actually looking for it cause i thought i remembered a duplicate): [Why typical Array List implementations aren't double-ended?](http://stackoverflow.com/q/6147618/319403) – cHao Dec 24 '13 at 18:21

3 Answers3

1

I prefer using whatever reference will give me the minimal set of functionality I need for easiest migration if I change implementations.

If I just need to add and remove, I can just do

Collection<T> myCol = new // pick any implementation

If I need to get them in FIFO order, I won't be using a List because the List interface has no methods for popping the oldest. It has a method for popping index 0, but that's not the same. If I need FIFO ordering, I must resign myself to using a Queue reference.

Queue<T> myQueue = new // pick any implementation

Most Queue and Deque implementations are lists themselves, so it makes sense that it might be confusing. But you do not want to do this:

ArrayDeque<T> myQueue = new ArrayDeque<T>(); // yuck! don't use a concrete reference!

Instead, use a reference with the minimal amount of functionality necessary to do the job. In this case, that means using the interface and not the implementation specific methods of the ArrayDeque class.

corsiKa
  • 81,495
  • 25
  • 153
  • 204
  • corsiKlause Ho Ho Ho. Please see my updated post and kindly let me know your thoughts on it – M Sach Dec 24 '13 at 18:44
  • i think If I need FIFO retrieval, I must use Queue but if i want index wise rerieval i must use List .Is that correct? – M Sach Dec 24 '13 at 18:56
  • That sounds correct. If you only need REMOVAL from the ends, consider a `CircularArrayQueue` - there's no default Java implementation, but there are implemenations available if you search for it on the internet. – corsiKa Dec 24 '13 at 19:01
  • FYI: `ArrayList` FAILS your test for requirement 3. If you need to removal from the middle, `ArrayList` has `O(n)` removals. :-{ – corsiKa Dec 24 '13 at 19:02
  • As you said "If you need to removal from the middle, ArrayList has O(n) removals." i think you mean for removal it will be O(1) but now elements below the removed ones needs to be shifted upwards . So total cost becomes O(n). Right? – M Sach Dec 25 '13 at 07:42
  • I guess you *could* look at it that way, but that kind of implies that shifting the other nodes is option, when it isn't. If you think about it, there is no removal necessary: you just need to shift the other nodes on top of it. So you could call the removal O(0) if you look at it that way. I prefer to consider all the mandatory operations when considering the cost, which is why I say ArrayList has O(n) removals. You can't just set the array index to null and say "oh look, it's removed!" – corsiKa Dec 25 '13 at 15:23
1

If you are only going to access the ends of your collection, then the ArrayList and the ArrayDeque will essentially have the same functionality. If your goal is to be restricting the use of the collection to FIFO, then I'd say your better off just using a queue since the deque will allow expansion and contraction at either end (not FIFO).

On the other hand, if you are wondering about using an ArrayDeque for better performance than the ArrayList, I think they are equivalent. Both will need to resize when they need more space and access at any index is still constant (although you would be limiting it to FIFO). If performance is an issue you could get a performance boost out of using a "circular queue" where the queue can wrap around at the Nth index and start up again at index zero (preventing you from needing to resize as often due to removes when the size is still less than capacity).

Another benefit of the array implementations are better cache miss/hits too which is a nice perk.

CM0491
  • 280
  • 3
  • 18
0

Besides what have been mentioned here, I personally think it might also be a case of language barrier. Some people might find the words poll, peek, offer a little puzzling and so they turn a blind eye to Queue and implement a queue themselves using the standard List.

Shinhung
  • 1