Design own ArrayList and Iterator in Java

Dear reader,

Today I am writing answers for few common interview questions: 
1. Difference between ArrayList and LinkedList and where to use what.
2. A basic program on ArrayList and Iterator.
3. Design your own ArrayList.
4. How Iterator works and design your own Iterator.

Answer Descriptions:

Difference between ArrayList and LinkedList in Java:
    ArrayList extends AbstractList and LinkedList extends AbstractSequentialList however both implement 
    List Interface but they work internally different. Based on their super-class you can easily figure out that 
    LinkedList is a sequential List but ArrayList is not. Main difference between ArrayList and LinkedList 
    is that ArrayList is implemented using re-sizable array while LinkedList is implemented using Doubly 
    LinkedList. In this article we will see differences between LinkedList and ArrayList and try to find 
    out when and where to use one over other.

The data-structure in the root of these two APIs are LinkedList==>Doubly Linked List and ArrayList==>Array.

1) Since Array is an index based data-structure, searching or getting elements from Array with index is 
   pretty fast. Array provides O(1) performance for get(index) method. However removal is costly in Array (so ArrayList)
   as you need to re-arrange all the elements for maintaining index values. On the Other hand LinkedList doesn't provide 
   Random or Index based access and you need to iterate over LinkedList to retrieve any element which will be of order O(n).

2) Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of re-sizing 
   array (also copying content to new array if array gets full) which makes adding into ArrayList of O(n) in 
   worst case, while adding speed is O(1) in LinkedList. ArrayList also needs to update its index if you 
   insert something to it (except if you add value at the end of array).

3) Again Removal is costly in ArrayList as you have to re-arrange all elements for updated index.

4) LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object(data) 
   but in case of LinkedList each node holds both data and address of next and previous node.
   
5) You can customize an ArrayList size while constructing an ArrayList by passing a parameter.
   I mean when we write: "new ArrayList()", an array of size 10 elements is created. So specify "new ArrayList(100)";
   I mean based on your requirement.

When to use LinkedList and ArrayList in Java:
    As I said LinkedList is not as popular as ArrayList but still there are situation where a LinkedList is better 
    choice than ArrayList in Java. Use LinkedList in Java if:

    1) Your application can live without Random access. Because if you need nth element in LinkedList you need to 
        first traverse up to nth element O(n) and than you get data from that node.
    2) Your application is more insertion and deletion driven and you insert or remove more than retrieval. Since 
        insertion or removal doesn't involve re-sizing, LinkedList is much faster than ArrayList.
    3) ArrayList is fast and easy to use, just try to minimize array re-sizing by constructing ArrayList with proper 
        initial size.


Basic Program on ArrayList and Iterator: 
//MyIteratorExample.java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class MyIteratorExample {
    public static void main(String[] args) {
        List<String> list=new ArrayList<String>();
        list.add("Mango");
        list.add("Strawaberry");
        list.add("Papaya");
        list.add("Watermalon");

        Iterator<String> it=list.iterator();        
        while(it.hasNext()){
            String s=it.next();
            System.out.println("Value: "+s);
        }
        System.out.println("----Another way to iterate through List is below----");
        for(String s:list) {  
            System.out.println("Value: "+s);
        }
    }
}
//Output:
Value: Mango
Value: Strawaberry
Value: Papaya
Value: Watermalon

----Another way to iterate through List is below (using for-each loop)----

NOTE: for-each loop is applicable to only those collection APIs which implements Iterable interface. The 
      signature is like below:
        
        //Collection (interface) extends Iterable  
        //List (interface) extends Iterable

        public Iterator iterator() {
            System.out.println("My overridded iterator method called in Fruit class");
            return new FruitIterator(this);  //FruitIterator implements java.util.Iterator interface
        }

Design your own ArrayList and Iterator:
    Writing two basics first:
    a. ArrayList: ArrayList is a collection which implements various interfaces and extends AbstractList class.
    b. Iterator: Only those classes can be iterated who implement "java.lang.Iterable" interface.   

I have written 3 files for ArrayList and Iterator design and execution. One is having main method which can be 
executed to see the output. Main program has main method and it uses mine designed ArrayList and Iterator. Se below 
are the 3 files:

FruitIterator.java   //Iterator designed by me.
MyOwnArrayList.java  //ArrayList designed by me.
MyFruitIteratorExample.java  //Having main method which executes my ArrayList and my Iterator.

************Mine designed ArrayList***********
import java.util.RandomAccess;

public class MyOwnArrayList implements RandomAccess, Cloneable, java.io.Serializable {

    private transient Object[] elementData;  //Making one array to hold data
    private int size;
    protected transient int modCount = 0;  //Counter to find how many times Array is re-sized.
    private static final long serialVersionUID = 1234L;

    public MyOwnArrayList() {  //Making an initial Array of size 10.
        this(10);
    }
    public MyOwnArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = (Object[])new Object[initialCapacity];
    }

    public boolean add(Object obj) {
        validateCapacity(size + 1);  
        elementData[size++] = obj;
        return true;
    }

    public Object get(int index) {
        Object obj=elementData[index];
        return obj;
    }

    public int size() {
        return size;
    }
    public void validateCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1; //Size increases by 1.5 times+1.

            if (newCapacity < minCapacity)
                newCapacity = minCapacity;
            elementData = (Object[])new Object[newCapacity];            
            System.arraycopy(oldData, 0, elementData, 0, size); //src, srcPos, dest, destPos, length
            //System.arraycopy(src, srcPos, dest, destPos, length);
        }
    }

    public Object remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

        modCount++;
        Object oldValue = elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            //System.arraycopy(src, srcPos, dest, destPos, length);
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        }
        elementData[--size] = null; // Let gc do its work
        return oldValue;
    }
    
    //Defining iterator method
    public FruitIterator iterator() {
        System.out.println("My overridded iterator method called in Fruit class");
        return new FruitIterator(this);
    }
}

************Mine designed Iterator***********
public class FruitIterator {
    private MyOwnArrayList fruitList;
    private int position;

    public FruitIterator(MyOwnArrayList fruitList) {
        this.fruitList = fruitList;
    }

    public boolean hasNext() {
        if (position < fruitList.size())
            return true;
        else
            return false;
    }

    public Object next() {
        Object aniObj = fruitList.get(position);
        position++;
        return aniObj;
    }
    public void remove() {
        fruitList.remove(position);
    }
}


//Program: MyFruitIteratorExample.java, Execute the below program.
public class MyFruitIteratorExample {
    public static void main(String[] args) {
        
        MyOwnArrayList fruitList = new MyOwnArrayList();
        fruitList.add("Mango");
        fruitList.add("Strawaberry");
        fruitList.add("Papaya");
        fruitList.add("Watermalon");
        
        System.out.println("-----Calling my iterator on my ArrayList-----");
        FruitIterator it=fruitList.iterator();        
        while(it.hasNext()){
            String s=(String)it.next();
            System.out.println("Value: "+s);
        }
        System.out.println("--Fruit List size: "+fruitList.size());
        fruitList.remove(1);
        System.out.println("--After removal, Fruit List size: "+fruitList.size());
    }
}

//Output:
-----Calling my iterator on my ArrayList-----
My overridded iterator method called in Fruit class
Value: Mango
Value: Strawaberry
Value: Papaya
Value: Watermalon
--Fruit List size: 4
--After removal, Fruit List size: 3

NOTE: That's it. It is done. Now the same program won't compile if you use for-Each loop in main
      program to iterate my ArrayList. The reason is for-Each loop is designed to have an Iterator 
      return type from iterator() method which is defined in my ArrayList. So your Custom Iterator
      must implements Iterator interface then. This is also design of Iterator but it is a kind of
      extension. See below code will not compile.
      
      MyOwnArrayList fruitList = new MyOwnArrayList();
      fruitList.add("Mango");
      fruitList.add("Strawaberry");
      fruitList.add("Papaya");
      fruitList.add("Watermalon");
      for(Object obj:fruitList){     //Can only iterate over an array or an instance of java.lang.Iterable
            System.out.println("Value: "+obj);
      }
      
      Now keep the above code as it is and make the below changes:
      //Add Iterable interface in my ArrayList
       public class MyOwnArrayList implements RandomAccess, Cloneable, java.io.Serializable, Iterable {..}
      
      //Make FruitIterator and implementation of Iterator
      public class FruitIterator implements java.util.Iterator {..}
      
      Then the above for-Each loop will compile and run well.
============================END===============================