Sunday, 8 September 2013

LinkedList vs ArrayList cost

LinkedList vs ArrayList cost

I've read quite a few questions here that discuss the cost of using
ArrayLists vs LinkedLists in Java. One of the most useful I've seen thus
far is is here: When to use LinkedList<> over ArrayList<>?.
I want to be sure that I'm correctly understanding.
In my current use case, I have multiple situations where I have objects
stored in a List structure. The number of objects in the list changes for
each run, and random access to objects in the list is never required.
Based on this information, I have elected to use LinkedLists with
ListIterators to traverse the entire content of the list.
For example, my code may look something like this:

for (Object thisObject : theLinkedList) {
// do something
}
If this is a bad choice, please help me understand why.
My current understanding is that traversing the entire list of objects in
a LinkedList would incur O(n) cost using the iterative solution. Since
there is no random access to the list (i.e. The need to get item #3, for
example), my current understanding is that this would be basically the
same as looping over the content of an ArrayList and requesting each
element with an index.
Assuming I knew the number of objects to be stored in the list beforehand,
my current line of thinking is that it would be better to initialize an
ArrayList to the appropriate size and switch to that structure entirely
without using a ListIterator. Is this logic sound?
As always, I greatly appreciate everone's input!

No comments:

Post a Comment