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:
- Java: The Complete Reference
- Head First Java by Kathy Sierra, Bert Bates
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
- Difference between JVM, JRE and JDK
- Conversion between list and array types
- Annotations in Java 5.0
- G1 Garbage Collector in Java 7.0
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.
Design Patterns in Java