Wednesday, October 17, 2018

ArrayList implementation

This ArrayList class mimics ArrayList of Java collection. The methods are all commented to make it easy for the readers. The code is available here.

List.java


package com.ds.adt.list;

/**
 * List interface includes all the methods that needs to be implemented by 
 * List type ADTs such as ArrayList, LinkedList, DoublyLinkedList etc.  
 * 
 * @author Pritam Banerjee
 * @version 15 October 2018
 */
public interface List<T> {

    public void add(T data);

    public void insert(T data, int position);

    public T get(int position);

    public void remove(T data);

    public void remove(int position);

    public void removeAll(List<T> data);

    public int size();
}



ArrayList.java

package com.ds.adt.list.array;

import java.lang.reflect.Array;
import com.ds.adt.list.List;

/**
 * Implements the List Interface and mimics Java's ArrayList
 *
 * @author Pritam Banerjee
 * @version 15 October 2018
 */

public class ArrayList<T> implements List<T> {

    /** Keeps track of the size of the array */
    private int size = 0;

    /** The total size of the array */
    private int capacity = 5;

    /** The actual resizable array */
    private T[] arr;

    /**
     * Constructor Declare the actual array
     */
    @SuppressWarnings("unchecked")
    public ArrayList() {
        arr = (T[]) new Object[capacity];
    }

    /**
     * Adds data to the list.
     * 
     * @param T data to be added
     */
    @Override
    public void add(T data) {
        if (size > capacity - 1) {
            resize();
        }
        arr[size] = data;
        size++;
    }

    /**
     * Used to insert in a particular position
     * 
     * @param T data
     * @param Integer position 
     */
    @Override
    public void insert(T data, int position) {
        if (position > size) {
            return;
        }
        Class<T> t = null;
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) Array.newInstance(t, capacity);
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (position != i) {
                temp[count] = arr[i];
            } else {
                temp[position - 1] = data;
                temp[position] = arr[i];
            }
            count++;
        }
    }

    /**
     * Remove T data
     * 
     * @param T data to be deleted 
     */
    @Override
    public void remove(T data) {
        if (data == null)
            return;

        if (size == 0)
            return;

        int count = 0;
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Object[size];
        for (int i = 0; i < size; i++) {
            if (!arr[i].equals(data)) {
                temp[count] = arr[i];
                count++;
            }
        }
        arr = temp;
        size = count;
    }

    /**
     * Remove all the elements of a List passed as a param 
     * 
     * @param position List
     */
    @Override
    public void removeAll(List<T> position) {
        for (int i = 0; i < position.size(); i++) {
            remove(position.get(i));
        }
    }

    /**
     * Returns the size of the list
     * 
     * @return size Integer
     */
    @Override
    public int size() {
        return size;
    }

    /**
    * Removes the element on a particular position 
    * 
    * @param position Integer
    */
    @Override
    public void remove(int position) {
        if (size == 0) {
            return;
        }
        if (position > size) {
            throw new IndexOutOfBoundsException();
        }

        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Object[capacity];
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (i != position) {
                temp[count] = arr[i];
                count++;
            }
        }
        arr = temp;
        size--;
    }

    /**
     * Returns the element on that position
     * 
     * @param position int
     * 
     * @return T 
     */
    @Override
    public T get(int position) {
        if (position < size) {
            return arr[position];
        }
        return null;
    }

    /**
     * Overrides object toString() method 
     * 
     * @return String 
     */
    @Override
    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append("arr[" + i + "] = " + arr[i] + " ");
            sb.append("\n");
        }
        return sb.toString();
    }

    /**
     * Resizes the array when capacity reaches a limit
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        capacity = capacity * 2;
        T[] temp = (T[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            temp[i] = arr[i];
        }
        arr = temp;
    }

}


The following class gives a demo of the above ArrayList:

package com.ds.adt.list.array;

import com.ds.adt.list.List;

public class ArrayListDemo {

    public static void main(String[] args) {
        
        List<Integer> arrInteger = new ArrayList<Integer>();
        arrInteger.add(12);
        arrInteger.add(14);
        arrInteger.add(11);
        arrInteger.add(1);
        arrInteger.add(4);
        arrInteger.add(85);
       
        System.out.println(arrInteger);
        
        arrInteger.remove(2);
        
        System.out.println("After deleting 2");
        System.out.println(arrInteger);
        
        // Testing with Strings
        List<String> arrString = new ArrayList<>();
        
        System.out.println("String array: ");
        arrString.add("Pritam");
        arrString.add("Navi");
        arrString.add("Poda");
        arrString.add("Test");
        arrString.add("Molly");
        arrString.add("Piu");
       
        System.out.println(arrString);
        
        arrString.remove("Test");
        
        System.out.println("After deleting Test:");
        System.out.println(arrString);

    }


}

1 comment:

  1. Thanks for sharing such a great information.. It really helpful to me..I always search to read the quality content and finally i found this in you post. keep it up!
    online education in india

    ReplyDelete