ArrayList,LinkedList,Vector and Stack

ArrayList (Since Java 1.2):

  • Grow able Array implementation of List interface.
  • Insertion order is preserved.
  • Duplicate elements are allowed.
  • Multiple null elements of insertion are allowed.
  • Default initial capacity of an ArrayList is 10.
  • The capacity grows with the below formula, once ArrayList reaches its max capacity.
  • newSize/newCapacity= (oldCapacity * 3)/2 + 1
Output:
 

  • From above example, we can say ArrayList collection represents the objects in a manner:
Insertion order is preserved, inserts duplicate values as well as null elements.
  • All collection classes extends AbstractCollection which has toString() method. Its overridden to return the collection content in the format [Object1, Object2, Object3]
  • All collection classes are implementing Clonable & Serializable interfaces.

When to use ArrayList: Use ArrayList if you want to retrieve the elements frequently. Because ArrayList implements RandomAccess interface and its index based collection.

See ArrayList’s get(int index) from API.

For data retrieval it’s just checking range check on index and returning the element from Object array. So use ArrayList if your frequent operation is retrieve.  It retrieves any random element with the same speed.

The time complexity of ArrayList’s get(int index) method is O(1).

When you should not use ArrayList: ArrayList is not recommended if you are adding/removing elements in a specified position frequently . Because it requires several shift operation for adding/removing operations.

Let’s see internal implementation of ArrayList methods:

add(E e) and add (int index, E element) -

add(E e)

Once you added element its calling the ensureCapcity. EnsureCapacity checks capacity to add a new element into the array list. If there is no capacity it creates new capacity by increasing old capacity and re-sizes the entire array (Creates new array with old data elements and with the new Capacity).

elementData = Arrays.copyOf(elementData, newCapacity);

And adds the element to the array list (elementData[size++] = e;)

So, The time complexity of ArrayList’s add(E e) is :

If the array is having capacity to add element then it is:   O (1) //amortized constant time.

If not having capacity then it is: O (n) worst case because array should be re-sized and copied to the new array.

Amortized time: It means average time taken per each operation (add element to array list) if you do multiple times.

add (int index, E element) :

Once you added an element with this method, it calls the ensureCapacity then it calls native code to re-arrange the array and adds the element into the specified index. So it takes more time to add an element in specified position. That’s the reason, array list is not recommended for adding the elements in a specified position of list.

Time complexity of ArrayList’s add(int index, E element) :

O (n – index) amortized constant time

O (n) worst-case because array should be re-sized and copied to the new array.

Summary: Use array list if you’re frequently doing retrieval operations and don’t use array list if you’re frequently adding/removing elements from anywhere in an array list.

  • get(int index)  :    O(1)  // Main Advantage of ArrayList
  • add(E element) :  O(1) amortized constant time , O(n) worst case because array should be resized and copied.
  • add(int index, E element): O(n – index) amortized constant time, O(n) worst case because array should be resized and copied to the new array.
  • remove (int index) :  O(n – index) , O(1) for removing last element.
  • Iterator.remove() :  O(n – index)
  • ListIterator.add(E element) : O(n – index)

Vector (Since Java 1.0):

Vector is same as ArrayList except that all the Vector class methods are synchronized. Hence vector is thread-safe.

ArrayList vs Vector or Difference between ArrayList and Vector 

ArrayList Vector
There are no synchronized methods. All methods are synchronized.
No Thread safe: Multiple threads can access the array list at the same time. Thread safe: Only one thread is allowed to operate on vector object at a time.
Threads are not required to wait and hence performance is high All methods are synchronized.
There are no synchronized methods. It increases the waiting time of threads (since all the methods are synchronized) and hence performance is low
Recommended to use in performance point of view. Not recommended to use in performance point of view.
ArrayList is introuducd in Java 1.2 Vector is introduced in Java 1.0. Hence Vector class is legacy.

How to get Synchronized ArrayList?

LinkedList (Since Java1.2) :

  • Linked list is implementation class of List interface.
  • Underlying data structure is Double linked list.
  • Insertion order is preserved.
  • Duplicate elements are allowed.
  • Multiple null elements of insertion are allowed.

API:

When to use Linked List:

    Use linked list, if your requirement is more on adding or removing elements of a collection objects.

Time Complexity of LinkedList API:

  • get(int index) :  O(n)
  • add(E element): O(1) // Main Advantage of Linked list.
  • add(int index, E element) :  O(n)
  • remove(int index) :  O(n)
  • Iterator.remove() : O(1) // Main Advantage of Linked list.
  • ListIterator.add(E element) : O(1) // Main Advantage of Linked list.

Stack (Since Java1.0):

  • Stack is child class of Vector
  • Stack class in java represents LIFO (Last in First Out) stack of objects.
  •  There are only 5 methods in Stack

API:

 

 

 

 

Posted in collections and tagged , , , , .

One Comment

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">