Linked Lists - java

[AgaBoogaBoo]

What's the advantage of a linked list compared to an array or arraylist besides the fact that inserting something is quicker?

 

[clamum]

I don't have any experience with the ArrayList, but an advantage of a linked list over an array is that you can take out elements in the middle of the list and re-connect the links around them easily, where as in array you would have to manually move all the elements down to get rid of the empty space. By the same idea you can add things in the middle of the list in faster time than in an array (worst case O(n) compared to O(n^2)).

 

[Schrodinger]

http://java.sun.com/docs/books/tutorial/collections/implementations/general.html :

The two general purpose List (in the API reference documentation)implementations are ArrayList (in the API reference documentation)and LinkedList (in the API reference documentation). Most of the time, you'll probably use ArrayList. It offers constant time positional access, and it's just plain fast, because it does not have to allocate a node object for each element in the List, and it can take advantage of the native method System.arraycopy when it has to move multiple elements at once. Think of ArrayList as Vector without the synchronization overhead.

If you frequently add elements to the beginning of the List, or iterate over the List deleting elements from its interior, you might want to consider LinkedList. These operations are constant time in a LinkedList but linear time in an ArrayList. But you pay a big price! Positional access is linear time in a LinkedList and constant time in an ArrayList. Furthermore, the constant factor for LinkedList is much worse. If you think that you want to use a LinkedList, measure the performance with both LinkedList and ArrayList. You may be surprised.

ArrayList has one tuning parameter, the initial capacity. It refers to the number of elements the ArrayList can hold before it has to grow. There's not much to say about it. The only ArrayList operations that are not required by List are ensureCapacity and trimToSize (which alter the excess capacity), and clone.

LinkedList has no tuning parameters, and seven optional operations, one of which is clone. The other six are addFirst, getFirst, removeFirst, addLast, getLast, and removeLast; I have very mixed feelings about them. They make it a bit more convenient to use a LinkedList as a queue or a double-ended queue (dequeue), but they prevent you from easily switching representations when you discover that ArrayList is faster.

If you need synchronization, a Vector (in the API reference documentation)will be slightly faster than an ArrayList synchronized with Collections.synchronizedList, but Vector has loads of legacy operations, so be extra careful to always manipulate the Vector with the List interface, or you'll be stuck with it for life.

If your List is fixed in size (that is, you'll never use remove, add or any of the bulk operations other than containsAll) you have a third option that's definitely worth considering. See Arrays.asList in the convenience implementations section.