Explain vector, time complexity and how vector grows in java

(Last Updated On: November 6, 2016)

Answer: Vector & time complexity in Java: Vector is a dynamic array that grows or shrinks on run time to accommodate items during addition or deletion. Another important point is, it is synchronized. Supports both Iterator and ListIterator(provides both forward and backward traversal) which are fail-fast iterators.

It allows null and duplicates values. And, also it can contain heterogeneous objects if you don’t specify object type in vector (see below example).

Vector class supports 4 constructors:

  1. Vector() : Construct an empty vector with default array size of 10 and capacity increment of 0.

Note :

  • Capacity increment: The amount by which the capacity of the vector is automatically incremented when its size becomes greater than its initial capacity.
  • Since capacity increment is zero here, the capacity of the vector is doubled each time it needs to grow.
  1. Vector(int initialCapacity): Construct an empty vector with array size of initialCapacity and capacity increment of 0.

Note : Since capacity increment is zero here, the capacity of the vector is doubled each time it needs to grow.

  1. Vector(int initialCapacity, int capacityIncrement): Constructs an empty vector with the specified initial capacity and capacity increment

Note : Since we’re supplying capacity increment value here, the capacity of the vector will grow by this amount.

  1. Vector(Collection<? extendsE> c) : Construct a vector containing the elements of the specified collection, in the order they are returned by the collection’s iterator.

Vector time complexity in Java:

Good for

  • Retrieving elements from a specific position – O (1).
  • Adding and removing elements from the end. Constant time complexity – O(1).

Note : Adding and removing elements from any other position is expensive — Lenear: O(n-i), where n is the number of elements and i is the index of the element added or removed. These operations are more expensive because you have to shift all elements at index i and higher over by one element.

Uses:

  • If size of the array is not known in advance.
  • Need a thread-safe collection as vector is synchronized.
  • If expect frequent change in size of array dynamically.

How does vector grow internally in Java?

A vector will grow based on its capacityIncrement value. New length of vector is calculated as given below

newLength = capacityIncrement == 0 ? existingSize * 2 : existingSize + capacityIncrement

Once new size of vector is calculated Arrays.copyOf(existingArray, newLength) is called. The existing array and the new length of the array is passed to the method. This method will create a new array of given length and copy data into the new array.

Demonstrating some important methods with vector example

 

Output:

capacity : 10
Size: 0
capacity : 10
Size: 10
capacity : 20
Size: 11
After trim to size capacity : 11
Size: 11
Element at position 7 7
capacity : 11
Size: 10
capacity : 11
Size: 8
Element from list Hetero 1: 2
Element from list Hetero 2: three
Element from list Hetero 3: {}