Skip to main content

Collections: ArrayDeque vs. ArrayList

2 replies [Last post]
brunomedeiros
Offline
Joined: 2007-07-19

Hi. (I hope this is the right forum)
I want to use a Collection where I will only append elements to fill the collection, and then the collection stays immutable. I of course don't know the initial collection size at the start. Which is the best class to use, in terms of performance, ArrayDeque, or ArrayList, or any other? (if there is a difference at all)

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
briand
Offline
Joined: 2005-07-11

The difference really depends on how you want to use it. List supports the notion
of accessing the contained elements by index, Deque does not. List also allows you
to insert or delete at any point in the list, while Deque only allows insert and delete from
one end or the other. Check out the docs for the Deque and List interfaces to get a better
understanding of how they differ. If you are looking to implement a LIFO or FIFO queue
Deque would likely perform better than the List.

Note that both ArrayList and ArrayDeque are backed by arrays and both can be created
with a specified initial size for that array. Both will grow the array when necessary, and
such growth will result in copy operations from the old array into the new array. It will
also result in object allocations for the new array and garbage collections (eventually)
for the old array. ArrayList has a high cost for insert and delete operations, as portions
of the array must be copied during these operations, but it has excellent random access
performance. LinkedList has a lower cost for insert and delete operations, as only pointers
need to be moved, but has a higher cost for locating a entry by index.

It's difficult to say which is better for you as we only know how you plan to build the
collection (append elements to one end or the other, not sure which) and that the
list doesn't mutate. However, we don't know how you plan to access the list (LIFO,
FIFO, RANDOM, etc). If you right you code so that it doesn't assume a specific
concrete collection class (like ArrayList or ArrayDeque) but uses the appropriate
interfaces instead (List or Deque) , then you can easily substitute an ArrayList with
a LinkedList (or vice versa) to see which performs better for your needs. That's a
great part of the power behind the collections interfaces.

brunomedeiros
Offline
Joined: 2007-07-19

Oops, I forgot to mention that the order of the elements will not matter. Thus the access will be random, and after the collection is completed, it will be returned as a Collection interface to clients (not List, nor Deque).