Explain vector, time complexity and how vector grows in java

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

import java.util.List;
import java.util.Vector;

public class VectorTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Vector list = new Vector();

		System.out.println(" capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

		for (int i = 0; i < list.capacity(); i++) {
			list.add(i);
		}

		System.out.println(" capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

		list.add(10);
		System.out.println(" capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

		// Trims the capacity of this vector to be the vector's current size. If
		// the capacity of this vector is larger than its current size, then the
		// capacity is changed to equal the size by replacing its internal data
		// array, kept in the field elementData, with a smaller one. An
		// application can use this operation to minimize the storage of a
		// vector.
		list.trimToSize();

		System.out.println("After trim to size capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

		System.out.println("Element at position 7 " + list.get(7));
		list.remove(7);
		// System.out.println("Element at position 10 " + list.get(10)); Throws
		// array out of range exception

		System.out.println(" capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

		// Sets the size of this vector. If the new size is greater than the
		// current size, new null items are added to the end of the vector. If
		// the new size is less than the current size, all components at index
		// newSize and greater are discarded.
		list.setSize(8);
		System.out.println(" capacity : " + list.capacity());
		System.out.println("Size: " + list.size());

//Test if vector can contain Heterogenous objects
		Vector listHetero = new Vector();
		
		listHetero.add(2) ;
		listHetero.add("three") ;
		listHetero.add(new HashMap()) ;
		
		System.out.println("Element from list Hetero 1: " + listHetero.get(0));
		System.out.println("Element from list Hetero 2: " + listHetero.get(1));
		System.out.println("Element from list Hetero 3: " + listHetero.get(2));
	}

}

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: {}

Related Posts