Difference between ArrayList, Vector and LinkedList in Java

SHARE & COMMENT :

This is a basic tutorial explaining about the APIs define under the collection package in Java. We encounter numerous questions from our readers to clarify the differences on these interfaces, we have come up with an tutorial to explain the key differences on these APIs. ArrayList, Vector and LinkedList, these confuse many beginners and even experienced professionals who end up not knowing where to apply each of these types of lists. In fact they are all very similar, after all they implement the same interface (List). They all possess the same methods but not the same implementations of those methods. It is mainly in the performance that we can see the main difference.In the following sections we will explain how to use each of the lists and finally point out the main differences between them, which is the main objective of this article.

ArrayList

Let us start with the most known and used, ArrayList. This type of list is implemented as an array that is dynamically scaled, ie whenever it is necessary to increase its size by 50% the size of the list. Say you have a list size of 10 and its size will increase to 15 automatically when an add operation happens. Also the ArrayList allows elements to be accessed directly by the methods get () and set (), and added through add () and remove ().

Example Listing 1 : Using ArrayList

package net.javabeat;

import java.util.ArrayList;
import java.util.Iterator;

public class Main {

	public static void main(String args[]) {

		ArrayList<Integer> al = new ArrayList<Integer>();
		al.add(3);
		al.add(2);
		al.add(1);
		al.add(4);
		al.add(5);
		al.add(6);
		al.add(6);

		Iterator<Integer> iter1 = al.iterator();
		while (iter1.hasNext()) {
			System.out.println(iter1.next());
		}
		System.out.println("**************");
		System.out.println(al.get(2));

	}

}

If you run the above code the output would be:


3
2
1
4
5
6
6
**************
1

In the above code we notice that the ArrayList does not remove duplicate elements, and we can still access any element directly through its index, but everything has a cost and which we will see later.

ArrayList starts with a fixed size, which increases as needed, but the cost of this increase is high, because a copy is made of the current array to a new array with a new size, then imagine an array with 10 million elements that will be copied to a new array to create only 5000 elements? Indeed it is a high cost. So it is highly advisable that you start your Array with a number of elements that suits your current goal, without the need for dynamic creation of new spaces, or if you know you’ll have to store 300-400 objects in an Array , set 500.

There is a further very important point about ArrayList: These are not synchronized, hence are not thread-safe, ie, if your application needs to work as thread-safe at some point where a list is required, then discard ArrayList unless you take care of thread safety explicitly, which is obviously not correct way of doing.

Vector

From the point of view of API, or the way it is used, ArrayList and Vectors are very similar, you can say they are same. If you do not know in depth the concept of Vector and ArrayList both are used as if they were the same. See in Listing 2 is an example of that.

Example Listing 2 : Using Vector

package net.javabeat;

import java.util.Iterator;
import java.util.Vector;

public class Main {

	public static void main (String args []) {

		Vector<Integer> al  = new Vector<Integer> ();
		al.add (3);
		al.add (2);
		al.add (1);
		al.add (4);
		al.add (5);
		al.add (6);
		al.add (6);

		Iterator<Integer> iter1 = al.iterator();
		while (iter1.hasNext ()) {
		        System.out.println (iter1.next ());
		}
		System.out.println("**************");
		System.out.println (al.get (2));

	}
}

If you run the above code the output would be:


3
2
1
4
5
6
6
**************
1

You can see that in Listing 2: we have used the same structure as in Listing 1, changing only the list of ArrayList to Vector, but the rest of the code remains the same, and the output will also be identical.

So what is the difference between Vector and ArrayList?

  • First let’s talk about the fact that Vector is synchronized and ArrayList is not. This means that if you have an application that needs to be thread-safe at some point, use Vector and you will be guaranteed of thread safety.
  • Another important point is the dynamic allocation of the Vector, which is different from the ArrayList. Remember we talked about the 50% of the ArrayList increases its size when the list is full? The Vector increases twice, ie if you have a full list of 10 elements, this list will increase to 20, with 10 empty positions. But is this not bad? Depends on what you need if you want to increase the amount of elements very often, so it is ideal to use the Vector as it increases the size two times and you will get much more space than the ArrayList that need to be increased more frequently, hence reducing the performance of your application.

LinkedList

Before starting the explanations we will show a use of LinkedList and you will notice that is identical to an ArrayList.

Example Listing 3 : Using LinkedList

import java.util.Iterator;
import java.util.LinkedList;

public class Main {

	public static void main (String args []) {

		LinkedList ll = new LinkedList ();
		ll.add (3);
		ll.add (2);
		ll.add (1);
		ll.add (4);
		ll.add (5);
		ll.add (6);
		ll.add (6);

		Iter2 ll.iterator iterator = ();
		while (iter2.hasNext ()) {
			System.out.println (iter2.next ());
		}

	}

}

If you run the above code the output would be:

3
2
1
4
5
6
6

This type of list implements a double linked list, or a list doubly “linked”. The main difference between LinkedList and ArrayList is in performance between the methods add, remove, get and set.

This kind of list has better performance in the add and remove methods, than the methods that add and remove from the ArrayList, instead its get and set methods have a worse performance than the ArrayList. Let us see a comparison between each of the methods present in ArrayList and LinkedList:

  • get(int index): method in LinkedList has O (n) and the method in ArrayList has O (1)
  • add (E element): method in LinkedList has O (1) and method in ArrayList has O (n) in the worst case, since the array will be resized and copied to a new array.
  • add (int index, E element): method in LinkedList has O (n) and method in ArrayList has O (n) in the worst case.
  • remove (int index): method in LinkedList has O (n) and method in ArrayList has O (n-index), remove the last element then O (1).

Notice that the main difference is in the performance, and a thorough analysis should be made in cases where performance is critical.

Reference Books:

We have talked so much about performance difference between LinkedList and ArrayList, let’s see this in practice, which is faster at what times, so check the listing below.

Example Listing 4 : Performance comparison between LinkedList and ArrayList

package net.javabeat;

import java.util.ArrayList;
import java.util.LinkedList;

public class Main {

	public static void main(String args[]) {

		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();

		// Add ArrayList
		long startTime = System.nanoTime();

		for (int i = 0; i < 100000; i++) {
			arrayList.add(i);
		}
		long endTime = System.nanoTime();
		long duration = endTime - startTime;
		System.out.println("ArrayList add:" + duration);

		// Add LinkedList
		startTime = System.nanoTime();

		for (int i = 0; i < 100000; i++) {
			linkedList.add(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList add:" + duration);

		// Get ArrayList
		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			arrayList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList get:" + duration);

		// Get LinkedList
		startTime = System.nanoTime();

		for (int i = 0; i < 10000; i++) {
			linkedList.get(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList get:" + duration);

		// ArrayList removes
		startTime = System.nanoTime();

		for (int i = 9999; i >= 0; i--) {
			arrayList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("ArrayList remove:" + duration);

		// Remove LinkedList
		startTime = System.nanoTime();

		for (int i = 9999; i >= 0; i--) {
			linkedList.remove(i);
		}
		endTime = System.nanoTime();
		duration = endTime - startTime;
		System.out.println("LinkedList remove:" + duration);

	}
}

OUTPUT

ArrayList add:18482391
LinkedList add:15140237
ArrayList get:2558084
LinkedList get:87518301
ArrayList remove:229680490
LinkedList remove:83977290

Summary

This article highlighted about the similarities and differences between the list types: ArrayList, Vector and LinkedList. We also discussed with example the performance of the code with the use of each of these types. Hope you liked this article.

Comments

comments

About Manisha Patil

Manisha S Patil, currently residing at Pune India. She is currently working as freelance writer for websites. She had earlier worked at Caritor Bangalore, TCS Bangalore and Sungard Pune. She has 5 years of experience in Java/J2EE technologies.

Comments

  1. Why HashMap allows null as key & Hashtable wont allows null as key? Could you exaplain

    • Hello Siddu,

      To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.

      Null is not an object. So, hashcode can not be genertaed to compare the objects.

      Howevere, Hashmap is an advanced version of the Hashtable. Which is specifically designed to allow the key values and handles them as special case.
      Implementation is something like this (key==null ? k==null : key.equals(k)).

      I hope this clears your doubts.

      Thanks,
      Krishna

  2. List list=new ArrayList() vs ArrayList list=new ArrayList()? Could you explain which is most effective?

    • Mohamed Sanaulla says:

      Generally best practice is to use:
      List list = new ArrayList() [Java7 Syntax)
      OR
      List list = new ArrayList() [Pre Java7 Syntax).

      But this approach is more useful when declaring the parameters of method, for example:
      someMethod(List aList) is better than someMethod(ArrayList aList).
      This is because when the method parameters have a wider type one can pass instances of any sub class of that wider type i.e in the method accepting List one can pass instance of ArrayList or Vector or LinkedList, but in the method accepting ArrayList one can pass only instances of ArrayList.

Speak Your Mind

*

Close
Please support the site
By clicking any of these buttons you help our site to get better