8

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?

Community
  • 1
  • 1
sachinrahulsourav
  • 742
  • 1
  • 7
  • 16

3 Answers3

7

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

Lukas Eder
  • 211,314
  • 129
  • 689
  • 1,509
  • list.remove() is from the Iterator interface and this operation will have the same efficiency in an ArrayList as well. As far as list.add() I agree adding an element somewhere in the list is efficient for large lists with a LinkedList. – sachinrahulsourav Mar 19 '12 at 17:32
  • 2
    @sachinrahulsourav: Check out the source code of `remove(int)`. `ArrayList` performs a call to `System.arraycopy`, whereas `LinkedList` just updates some references... Being declared in an interface doesn't impact implementation facts... Apart from that, note that `remove(int)` is not declared in `Iterator`, but in `List`... – Lukas Eder Mar 19 '12 at 17:35
  • You right. I just realized, remove() will have to do a copy and update the references – sachinrahulsourav Mar 19 '12 at 17:37
  • 1
    If you're doing a lot of insertion removing from the front of the list, perhaps you want `ArrayDeque` (or reverse the list). – Tom Hawtin - tackline Mar 19 '12 at 17:46
2

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.

Oleksi
  • 12,947
  • 4
  • 56
  • 80
  • Insert or remove an element from where? It could be O(n). – Tom Hawtin - tackline Mar 19 '12 at 17:46
  • @TomHawtin-tackline Only if you include finding the list node for that element. In some cases, you already have it, or can get at it in constant time. And in many cases where you have to search, you'd had to search anyway, even if you had an array. –  Mar 19 '12 at 18:13
-1

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.

Steve Kuo
  • 61,876
  • 75
  • 195
  • 257