Arrays vs ArrayLists vs Vectors vs LinkedLists

The question is which one to use and when? Which one is more efficient? Lets look into each one of them.

An array is basically a fixed size collection of elements. The bad point about an array is that it is not resizable. But its constant size provides efficiency. So arrays are better to use when you know the number of elements available with you.

ArrayList is another collection where the number of elements is resizable. So if you are not sure about the number of elements in the collection use an ArrayList. But there are certain facts to be considered while using ArrayLists.

=> ArrayLists is not synchronized. So if there are multiple threads accessing and modifying the list, then synchronization might be required to be handled externally.

=> ArrayList is internally implemented as an array. So whenever a new element is added an array of n+1 elements is created and then all the n elements are copied from the old array to the new array and then the new element is inserted in the new array.

=> Adding n elements requires O(n) time.

=> The isEmpty, size, iterator, set, get and listIterator operations require the same amount of time, independently of element you access.

=> Only Objects can be added to an ArrayList

=> Permits null elements

If you need to add a large number of elements to an ArrayList, you can use the ensureCapacity(int minCapacity) operation to ensure that the ArrayList has that required capacity. This will ensure that the Array is copied only once when all the elements are added and increase the performance of addition of elements to an ArrayList. Also inserting an element in the middle of say 1000 elements would require you to move 500 elements up or down and then add the element in the middle.

The benefit of using ArrayList is that accessing random elements is cheap and is not affected by the number of elemets in the ArrayList. But addition of elements to the head of tail or in the middle is costly.

Vector is similar to ArrayList with the difference that it is synchronized. It offers some other benefits like it has an initial capacity and an incremental capacity. So if your vector has a capacity of 10 and incremental capacity of 10, then when you are adding the 11th element a new Vector would be created with 20 elements and the 11 elements would be copied to the new Vector. So addition of 12th to 20th elements would not require creation of new vector.

By default, when a vector needs to grow the size of its internal data structure to hold more elements, the size of internal data structure is doubled, whereas for ArrayList the size is increased by only 50%. So ArrayList is more conservative in terms of space.

LinkedList is much more flexible and lets you insert, add and remove elements from both sides of your collection - it can be used as queue and even double-ended queue! Internally a LinkedList does not use arrays. LinkedList is a sequence of nodes, which are double linked. Each node contains header, where actually objects are stored, and two links or pointers to next or previous node. A LinkedList looks like a chain, consisting of people who hold each other's hand. You can insert people or node into that chain or remove. Linked lists permit node insert/remove operation at any point in the list in constant time.

So inserting elements in linked list (whether at head or at tail or in the middle) is not expensive. Also when you retrieve elements from the head it is cheap. But when you want to randomly access the elements of the linked list or access the elements at the tail of the list then the operations are heavy. Cause, for accessing the n+1 th element, you will need to parse through the first n elements to reach the n+1th element.

Also linked list is not synchronized. So multiple threads modifying and reading the list would need to be synchronized externally.

So the choice of which class to use for creating lists depends on the requirements. ArrayList or Vector( if you need synchronization ) could be used when you need to add elements at the end of the list and access elements randomly - more access operations than add operations. Whereas a LinkedList should be used when you need to do a lot of add/delete (elements) operations from the head or the middle of the list and your access operations are comparatively less.

ArrayList vs Vector

This is one of the famous questions that a Java beginner has in his mind. This is also a famous question asked in interviews. Following are the differences between ArrayList and Vector.

1. Vectors and Hashtable classes are available from the initial JDK 1.0. But, ArrayList and HashMap are added as a part of new Collections API since JDK 1.2.

2. Vectors and Hashtable are synchronized where as ArrayList and HashMap are unsynchronized.

When to use Vector? When to use ArrayList? 
1. ArrayList is faster when compared to Vector since ArrayList is unsynchronized. So, if the List will be modified by only one thread, use ArrayList. If the list is a local variable, you can always use ArrayList.

2. If the List will be accessed by multiple threads, always use Vector, otherwise you should take care of synchronization manually.

To visualize the problem with synchronization, try the following code.
There is a Producer class that adds 5000 elements to the List (ArrayList/Vector). Another class, Consumer class removes 5000 elements from the same list. There are around 10 producer threads and 10 consumer threads.

class Producer implements Runnable {

  private List list;

  public Producer(List pList) {
    list = pList;
  }

  public void run() {
    System.out.println("Producer started");
    for (int i = 0; i < 5000; i++) {
      list.add(Integer.toString(i));
    }
    System.out.println("Producer completed");
  }

}

class Consumer implements Runnable {
  private List list;

  public Consumer(List pList) {
    list = pList;
  }

  public void run() {
    System.out.println("Consumer started");
    for (int i = 0; i < 5000; i++) {
      while (!list.remove(Integer.toString(i))) {
        // Just iterating till an element is removed
      }

    }
    System.out.println("Consumer completed");
  }
}

public class ListTest {

  public static void main(String[] args) throws InterruptedException {
    //   List list = new Vector();
    List list = new ArrayList();

    for (int i = 0; i < 10; i++) {
      Thread p1 = new Thread(new Producer(list));
      p1.start();
    }

    for (int i = 0; i < 10; i++) {
      Thread c1 = new Thread(new Consumer(list));
      c1.start();
    }
    Thread.yield();

    while (Thread.activeCount() > 1) {
      Thread.sleep(100);
    }

    System.out.println(list.size());

  }

}

Try running the program with ArrayList. You can see a number of ArrayIndexOutOfBoundException, Consumer threads will still keep waiting for more elements which wont be added because the Producer has terminated after throwing the Exception.

Now, change the line,

List list = new ArrayList();

to

List list = new Vector();

and run the program.

Now you can see a proper result.

This clearly explains why you should use Vector class when there are multiple threads in the system.

In this program, even if you remove the Consumer class and Consumer thread, you can see that the Producer will themselves throw Exception.

 

This is because, while adding an element to the ArrayList, it checks for the size of the Array. If the array size is not sufficient, a new array will be created, the elements will be copied to the new array. If the context switching if Threads happen at this place also, we will get ArrayIndexOutOfBoundException, or sometimes, you may not get any Exception, but some elements will be missing, and many unexpected behaviors.

So always use Vector if there are multiple threads. The same rule applies to HashMap vs Hashtable, StringBuilder vs StringBuffer.

Summary:
1. Use Vector if there are multiple threads and ArrayList if there is only a single thread.
2. Use Hashtable if there are multiple threads and HashMap if there is only a single thread.
3. Use StringBuffer if there are multiple threads and StringBuilder if there is only a single thread.