Code Pumpkin

Array List

March 31, 2017
Posted by Dipen Adroja

ArrayList

We can think, arraylist as an array having collection of items which can grow and shrink dynamically.

Before going further one question should arise Why we want to use array list instead of array? Answer is very simple, when we need a data structure which have all the array capabilities and is also efficient at changing its size which is not possible in case of array.

Our array list implementation will support below operations:

size – returns size of the arraylist

isEmpty – Returns whether the list is empty.

get – Returns (but does not remove) the element at index i.

set – Replaces the element at index i with e, and returns the replaced element.

add – Inserts element e to be at index i, shifting all subsequent elements later.

remove – Removes and returns the element at index i, shifting subsequent elements earlier.

Implementation

As the name suggest we will implement arraylist using array. For this, first we will create an interface which will give us the functionalities to be implemented for creating list.


public interface List< E> {
 
    int size( );
 
    /** Returns whether the list is empty. */
    boolean isEmpty( );
 
    /** Returns (but does not remove) the element at index i. */
    E get(int i) throws IndexOutOfBoundsException;
 
    /** Replaces the element at index i with e, and returns the replaced element. */
    E set(int i, E e) throws IndexOutOfBoundsException;
 
    /** Inserts element e to be at index i, shifting all subsequent elements later. */
    void add(int i, E e) throws IndexOutOfBoundsException;
 
    /** Removes/returns the element at index i, shifting subsequent elements earlier. */
    E remove(int i) throws IndexOutOfBoundsException;
}

Array Based Implementation

In an array-based implementation we maintain the following fields:

  • an array of a default capacity (In our case we have kept it 20),
  • A variable size which will refers to the current size of the array list.

The array based implementation is shown in below code snippet with purpose and functioning of the each method. Each operation is also having the time complexity associated with them for this implementation.


public class ArrayList < E> implements List< E> {
 
    public static final int CAPACITY = 20;
    E[] data;
    private int size=0;
     
    public ArrayList(){
        this(CAPACITY);
    }
     
    public ArrayList(int capacity) {
        data = (E[]) new Object[capacity];
    }
 
  /**
    * This runs on O(1)
    *
    */
     
    @Override
    public int size() {
        return size;
    }
 
  /**
    * This runs on O(1)
    *
    */
     
    @Override
    public boolean isEmpty() {
        return size==0;
    }
 
   /**
     * While getting an element at index i, we will check for boundary condition first.
     * If it passes then we will return element at given array index.
     * This runs on O(1)
     *
     */
      
    @Override
    public E get(int i) throws IndexOutOfBoundsException {
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
        return data[i];
    }
 
   /**
     * This runs on O(1)
     * Setting an element at index i will also first check for boundary condition.
     * After that we will set element value at index i and return the old value
     * of the element at index i
     */
      
    @Override
    public E set(int i, E e) throws IndexOutOfBoundsException {
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
        E temp = data[i];
        data[i] = e;
        return temp;
    }
 
   /**
     * This runs on O(n)
     * For adding an element, we will check for boundary conditions once it is
     * passed we will check for current capacity.
     *
     * If array is full, we call the resize method and then add the new element
     * at given index
     *
     * To add element in natural order, we will pass the i as current size of
     * the arraylist.
     *
     * To add element in between, we will first shift all the elements to make
     * room for new element then we set it at given index
     *
     */
     
    @Override
    public void add(int i, E e) throws IndexOutOfBoundsException {
         
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
         
        if(size==data.length)
            resize(data.length *2);
         
        for(int k=size-1;k>=i;k--){
            data[k+1] = data[k];
        }
        data[i] = e;
        size++;
    }
     
   /**
     * This runs on O(n)
     * First check for bounday condition. shift all the elements to left
     * which are after the element to be removed. Return the removed element
     *
     */
 
    @Override
    public E remove(int i) throws IndexOutOfBoundsException {
         
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
         
        E temp = data[i];
         
        for(int k=i;k<=size-1;k++){
            data[k]=data[k+1];
        }
        data[size-1] = null;
        size--;
        return temp;
    }
     
   /**
     * This method will resize the underlying array when the array gets full.
     * We have used the native array copy method to copy all the elements
     * to new array.
     *
     */
      
    protected void resize(int capacity)
    {
        E[] temp = (E[]) new Object[capacity];
        System.arraycopy(data, 0, temp, 0,data.length);
        data = temp;
    }  
}

Download Complete Java Program »

Apart from this, we can also have other methods which our implementation support.Some of these operations are, addAll(Adds all elements of other list) We can also think about shrinking the arraylist space when more than half of the array list is empty though it will have little trade off between space and time complexity.

You can always go to Oracle Docs and check for other operation supported by arraylist and try to implement it yourself.

Though arrrayList have its advantages over arrays, it has some disadvantages as well. When there is a requirements of frequent insert/delete of the intermediate elements, at that time arraylist will not be that efficient as every time elements needs to shifted to right/left after each insertion and deletion.

That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.

Happy Learning 🙂

If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.

We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.



About the Author


Coder, Blogger, Wanderer, Philosopher, Curious pumpkin



Tags: , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.
Total Posts : 124
follow us in feedly

Like Us On Facebook