Re: 2 big Problems with LinkedList

From:

Lew <lew@lewscanon.com>

Newsgroups:

comp.lang.java.programmer

Date:

Sun, 24 Feb 2008 11:27:53 -0500

Message-ID:

<64OdncCjr7aUBlzanZ2dnUVZ_vKunZ2d@comcast.com>

Sanny wrote:

The above code is called 5/10 times I read somewhere Linkedlist.get()
is faster than ArrayList.get() This is why I chose LinkedList.

Jeff Higgins wrote:

To read about the differences see these links.
ArrayList extends AbstractList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractList.html>
LinkedList extends AbstractSequentialList
<http://java.sun.com/javase/6/docs/api/java/util/AbstractSequentialList.html>

For more information on the Java Collections Framework in general see:
<http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html>

In the case of ArrayList and LinkedList the respective Javadocs actually speak
directly to the performance of get():

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.

vs.

Operations that index into the list will traverse the list from the beginning or the end,
whichever is closer to the specified index.

The Javadocs for LinkedList also state:

All of the operations perform as could be expected for a doubly-linked list.

which argues strongly for learning what to expect from a doubly-linked list.
<http://en.wikipedia.org/wiki/Linked_list>
et al.

--
Lew