When would you use a java.util.LinkedList
Possible Duplicate:
When to use LinkedList<> over ArrayList<>?
This is a genuine attempt to know when would one use a LinkedList;
From what i understand since the java.util.LinkedList doesn't support random access, the only way to get the nth element is to skip from 1 to (n-1) or use get(n) which itself is very inefficient. So why would one use a LinkedList? An ArrayList would serve for most part unless you want to iterate the collection from both sides using a ListIterator?
Think about this method:
List list = // choose your list here
list.add(0, new Object());
For large lists, LinkedList will heavily out-perform ArrayList . The same applies for
list.remove(0);
... and many other methods. For more information, I suggest reading about the java.util.Deque interface, which is also implemented by LinkedList
Consider 3 common operators on these sorts of data structures: random element access, adding elements, and removing elements.
In LinkedList, your random element access is slow (O(N)), but adding and deleting are fast (O(1). For ArrayList, the reverse is true: random element access is fast (O(N)), but adding and removing elements are slower.
You need to look at which operations your system will do more of and use the appropriate data structure.
LinkedList better suited (as compared to ArrayList ) for insertions/deletion for arbitrary indexes. When inserting or deleting from an ArrayList , the internal array has to be shifted. For LinkedList , it's a matter of simply repointing the the nodes' pointers.