Interview Questions

Implement custom Array List in Java

Advertisement

ArrayList also known as dynamic arrays because of its ability to resize itself automatically when an element is inserted or deleted.

Internally ArrayList elements are placed in contiguous storage (array) so that they can be accessed and traversed using iterators. Here are some properties of ArrayList

  • By default ArrayList, data is inserted at the end.
  • Inserting at the end takes differential time, because sometimes there may be a need of extending the array.
  • Removing the last element takes only constant time because no resizing happens.
  • Inserting and erasing at the beginning or in the middle is linear in time.

To have our own ArrayList class we need to implement below methods:

  • void add(int data): This function takes one element and inserts it at the last. Amortized time complexity is O(1).
  • void add(int data, int index): It inserts data at the specified index. Time complexity is O(1).
  • int get(int index): It is used to get the element at the specified index. Time complexity is O(1).
  • void pop(): It deletes the last element. Time complexity is O(1).
  • int size(): It returns the size of the ArrayList. Time complexity is O(1).
  • int getCapacity(): It returns the capacity of the ArrayList. Time complexity is O(1).
  • void print(): It is used to print array elements. Time complexity is O(N), where N is the size of the ArrayList.
	
import java.util.Arrays;
public class DynamicArray{
    private int array[];
    // holds the current size of array
    private int size;
    // holds the total capacity of array
    private int capacity;
     
    // default constructor to initialize the array and values
    public DynamicArray(){
        array = new int[2];
        size=0;
        capacity=2;
    }
     
    // to add an element at the end
    public void add(int element){
        // double the  capacity if all the allocated space is utilized
        if (size == capacity){
            ensureCapacity(2); 
        }
        array[size] = element;
        size++;
    }
     
    // to add an element at a particular index
    public void add(int index, int element){
        // double the capacity if all the allocated space is utilized
        if (size == capacity){
            ensureCapacity(2); 
        }
        // shift all elements from the given index to right
        for(int i=size-1;i>=index;i--){
            array[i+1] = array[i];
        }
        // insert the element at the specified index
        array[index] = element;
        size++;
    }
 
    // to get an element at an index
    public int getElement(int index){
        return array[index];
    }
     
    // to remove an element at a particular index
    public void remove(int index){
        if(index>=size || index<0){
            System.out.println("No element at this index");
        }else{
            for(int i=index;i<size-1;i++){
                array[i] = array[i+1];
            }
            array[size-1]=0;
            size--;
        }
    }
     
    /* method to increase the capacity, if necessary, to ensure it can hold at least the 
    *  number of elements specified by minimum capacity arguement
    */
    public void ensureCapacity(int minCapacity){
        int temp[] = new int[capacity*minCapacity];
        for (int i=0; i < capacity; i++){
            temp[i] = array[i];
        }
        array = temp;
        capacity = capacity * minCapacity;
    }
     
    /*
    *  Trim the capacity of dynamic array to the current size. i.e. remove unused space
    */
    public void trimToSize(){
        System.out.println("Trimming the array");
        int temp[] = new int[size];
        for (int i=0; i < size; i++){
            temp[i] = array[i];
        }
        array = temp;
        capacity = array.length;
         
    }
     
    // to get the current size
    public int size(){
        return size;
    }
     
    // to get the current capacity
    public int capacity(){
        return capacity;
    }
     
    // method to print elements in array
    public void print(){
        System.out.println("elements in array are :"+Arrays.toString(array));
    }
}
Advertisement
Advertisement

Leave a Reply

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

6 + sixteen =

Share on Social Media