ArrayList vs LinkedList

ArrayList vs LinkedList


There comes two classes ArrayList and LinkedList to store objects. Internally, ArrayList stores elements as an array form and LinkedList stores elements in node form. Due to their internal style of storing the elements, they come with different performance heads depending the nature of action performed like addition and retrieval.

Programs are available at ArrayList and LinkedList.

A small Clock program developed (used in subsequent programs) to know the performance:

ArrayList vs LinkedList

The above screen shows different results when executed different times. It is because a number processes may be running right now on your system, some of which may be in pause, working or stopped etc. Also it depends on the availability of JVM free time. The above Clock program is used in every program to know the performance.

The above clock program is used in finding the performance of ArrayList and LinkedList in the following programs.

In the next program elements are inserted at 0 position always and actual 0 position elements are pushed down.

ArrayList vs LinkedList

Output screen of ArrayListLinkedList.java

Inserting elements at the beginning of an ArrayList requires that all existing elements be pushed down. This is a very costly overhead. But inserting at the beginning of LinkedList is cheap, because the elements of the structure are connected with each other via linked nodes. when an element is added, the two neighbour nodes are disturbed but not all nodes.

ArrayList vs LinkedList

Output screen of RandomLookup.java

Accessing the elements with ArrayList is less expensive than accessing elements with LinkedList.

ArrayList LinkedList
Adding elements Expensive Cheaper
Retrieving elements Cheaper Expensive

To retrieve the elements, it is advised to use Iterators with LinkedList.

Programming in terms of Interfaces

The example in the previous section illustrates an important point, namely, that there may be more than one "right" way to represent data. You might, for example, decide that an ArrayList is the best choice for some application, but then later decide that a LinkedList would in fact be a better choice. One way you can make changeovers like this easier to program is by using interface types, instead of actual types of classes that implement the interface. For example, if you say:

instead of saying

and you do likewise when declaring method parameters, as in

instead of

then you can use List everywhere in your programming, and you don’t have to worry too much about whether list is really an ArrayList or a LinkedList. In other words, you program in terms of functionality offered by interface types, and you can switch the actual implementation easily at some later point, for reasons of efficiency.

Leave a Reply

Your email address will not be published. Required fields are marked *