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:

public class Clock 
{
  long time;
  public Clock() 
  {
    setZero();
  }
  public void setZero() 
  {
    time = System.currentTimeMillis();
  }
  public long timeTaken() 
  {
    return System.currentTimeMillis() - time;
  }
  public void printTime(String str) 
  {
    System.out.println(str + ": " + timeTaken());
  }
  public static void main(String args[])
  {
    Clock c1 = new Clock();
    for(int i = 0; i < 1000000; i++) { }
    c1.printTime("Time tiken for 1000000 iterations");
    c1.setZero();
    
    for(int i = 0; i < 100000000; i++) { }
    c1.printTime("Time tiken for 100000000 iterations");
  }
}

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.

import java.util.*;
public class ArrayListLinkedList
{
  public static void main(String args[])
  {                                            // Using ArrayList
    ArrayList al = new ArrayList();
    Clock c1 = new Clock();
    for (int i = 0; i < 25000; i++)
    {
      al.add(0, new Integer(i));
    }
    c1.printTime("Using ArrayList");
 			                      // Using LinkedList
    LinkedList ll = new LinkedList();
    c1.setZero();
    for (int i = 0; i < 25000; i++)
    {
      ll.add(0, new Integer(i));
    }
    c1.printTime("Using LinkedList");
  }
}

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.

import java.util.*;
public class RandomLookup 
{
  public static void main(String args[]) 
  {
    Object obj;
  			                // Retrieving elements from ArrayList
    ArrayList al = new ArrayList();     // create an array list
    for (int i = 0; i < 25000; i++)     // populate the array list
    {
      al.add(new Integer(i));
    }
    Clock c1 = new Clock();
    for (int i = 0; i < 25000; i++)     // reading all the elements one by one
    {
      obj = al.get(i);
    }
    c1.printTime("Reading elements from an array list");
				        // Retrieving elements from LinkedList
    LinkedList ll = new LinkedList();  // create a linked list
    for (int i = 0; i < 25000; i++)    // populate the linked list
    {
      ll.add(new Integer(i));
    }
    c1.setZero();
    for (int i = 0; i < 25000; i++)   // reading all the elements one by one
    {
      obj = ll.get(i);
    }
    c1.printTime("Reading elements from a linked list");
  }
}

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:

	List list = new ArrayList();

instead of saying

        ArrayList list = new ArrayList();

and you do likewise when declaring method parameters, as in

		void display(List list) {    }

instead of

        void display(ArrayList list) {    }

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.