Creating Custom Array List (Generics Explained)

Creating Custom Array List (Generics Explained)

So, after a long time! Finally my exams are over and I am back to real-learning. In this blog we will be creating Custom Array Lists and then understand the concepts of Generics in Java. So let's start!

Idea and Thought Process

We want to create custom array lists for fun and to learn "What's going behind the Array List? What does an Array List do? It just gives us an array of infinite size in which we can add, remove, replace elements and much more. So while making a custom array list we need to take care that the size of the list is infinite and we can perform some actions on it. In this blog, we will not create a proper custom array list that contains all functions but will understand the concepts of Generics instead! So the most important question is how will we maintain the size of the array infinite? The simple answer is when Array will get full, the size of the array should become double and then it will just be another array. Let's code!

Creating an Integer Custom Array List

1. Firstly we will create a class named CustomArrayList, a private integer array named data, private integer DefaultSize which will store its default size. Then a constructor will initiate the array!

class CustomArrayList{
       private int[] data;
       private static int DefaultSize=10;
       public CustomArrayList(){
           this.data=new int[DefaultSize];
       }
}

The reason for private variables is very obvious and the reason for static default size is that this variable should be object independent! It should not change with the object! (Here we have taken the default size as 10, you can take anything)

  1. Now we will introduce another variable named Initsize which will be set to 0 initially. This variable will tell us the current size of the array!

     class CustomArrayList{
            private int[] data;
            private static int DefaultSize=10;
            private int InitSize=0;
            public CustomArrayList(){
                this.data=new int[DefaultSize];
            }
     }
    
  2. Now let's add the 'add()' function. This function should ensure that when the array is full, its size gets doubled. For this we create another two functions, first one to check whether the array is full and second one to resize it.

     private boolean isfull(){
                return InitSize==DefaultSize;
            }
            private void resize(){
                int[] temp=new int[DefaultSize*2];
                for(int i=0;i<temp.length;i++){
                    temp[i]=data[i];
                }
                data=temp;
            }
    

    Here InitSize variable will get updated by add() function and hence gives us the following condition. In resize function firstly we created a temp array of double size and then copied elements of the array to temp and then finally pointed our 'data' array to this temp array.

  3. Now will add these functions to add() function

     public void add(int num){
                if(isfull()){
                    resize();
                }
                data[InitSize++]=num;
            }
    

    Here the if condition is already explained. The next condition will add the element to the array and then increase the value of InitSize by 1 (Don't use ++InitSize, as then data[0] will be null!)

  4. So finally our custom array list is:

     class CustomArrayList{
            private int[] data;
            private static int DefaultSize=10;
            private int InitSize=0;
            public CustomArrayList(){
                this.data=new int[DefaultSize];
            }
            public void add(int num){
                if(isfull()){
                    resize();
                }
                data[InitSize++]=num;
            }
            private boolean isfull(){
                return InitSize==DefaultSize;
            }
            private void resize(){
                int[] temp=new int[DefaultSize*2];
                for(int i=0;i<temp.length;i++){
                    temp[i]=data[i];
                }
                data=temp;
            }
         }
    

    One can easily debug this if we create an object of this list and then use add(1), it will invoke the add function, as InitSize=0 so isfull() will give false and data[0] will become 1 and InitSIze will become 1. Now if we again use add(2) function same procedure will take place nut InitSIze=2. This will move till add(10), when we will use add(11), isfull will give true and so all elements of the data array will be copied to new array whose size is doubled and then hence add element to it!

So this is enough for understanding the working of Array List. Now let's move to Generics!

Need For Generics

For some time remove "Generics" from your brain and think What will you do if I assign you a task to make a custom array list which takes Integer, Character, Strings and Float. What will you do? Will you copy your code again and again for integer, strings etc.? This is a very bad practice! So to solve this, we use Generics in Java.

Generics

Let's understand Generics by some Caclulus. In differential calculus, sometime we use Parametrized Cordinates to differentiate a function. What do we mean by "Parametrized"? It means if we will replace that parametrized coordinate by our variable, whole function will remain same just the output will be in the form our variable. This is the same way Generics work in Java. We will replace "int" in our class by "<T>" here T is the parametrized variable and <> tell us that it is parametrized!

How to use Generics?

  1. Generics are declared with the class name.

     class CustomArrayList<T>{
     }
    

    Now we can use T wherever we want to use, like in our custom array list we had integer array, so instead of int array we can use <T> array. Just see this code:

     class CustomArrayList<T>{
            private T[] data;
            private static int DefaultSize=10;
            private int InitSize=0;
            public CustomArrayList(){
                this.data=new T[DefaultSize];
            }
            public void add(T num){
                if(isfull()){
                    resize();
                }
                data[InitSize++]=num;
            }
            private boolean isfull(){
                return InitSize==DefaultSize;
            }
            private void resize(){
                T[] temp=new int[DefaultSize*2];
                for(int i=0;i<temp.length;i++){
                    temp[i]=data[i];
                }
                data=temp;
            }
         }
    

    I have replaced int[] with T[], so that whatever I put in T, be it Integer, String every T will get replaced by that! Keep in mind that T can't be substituted by primitive data types that is we can't use int, char etc. as a substitution for T, we can use only non-primitive data types like "Integer", "Character" etc. Secondly, the above code will not run! A compilation error will be there while initializing the T array directly! Let's explore this error!

Exploring the Error

As I said, the above code will not run, it will give an error that T type array can't be instantiated directly. Before this, you should be well acquainted with the fact that Object creation takes place during run-time, and secondly Java compiler erases all the type parametres in generic code. So what if data=new T[DefaultSize] was allowed? Firstly during compile time this code will be converted to byte code and in run-time(when this byte code is executed) it will be unknown of any information of T (beacuse the information is erased!). So in last a very simple thing to say is that one can't create instances of type parameters that simply means this:

// we can't do this
class example<T>{
T element= new T();
}

We can solve this error by creating an object using object class, as every class inherits object class. So we can do this:

class CustomArrayList<T>{
       private Object[] data;
       private static int DefaultSize=10;
       private int InitSize=0;
       public CustomArrayList(){
           this.data=new Object[DefaultSize];
       }
       public void add(T num){
           if(isfull()){
               resize();
           }
           data[InitSize++]=num;
       }
       private boolean isfull(){
           return InitSize==DefaultSize;
       }
       private void resize(){
           Object[] temp=new Object[DefaultSize*2];
           for(int i=0;i<temp.length;i++){
               temp[i]=data[i];
           }
           data=temp;
       }
    }

How will it solve the error? During creating an object for this class, an array of Object type will be initiated but you can add only "T" type variable into it, as in add function T is still there, that means a generalized array will be created first which can contain any type of variable but using add function you can add only a specific type of variable into that array!

TypeCasting and Generics

Although this is not related to Gnerics, but for better understanding we can do this also. Array List has one more function "get()" which return the element for index you want. Let's create!

class CustomArrayList<T>{
       private Object[] data;
       private static int DefaultSize=10;
       private int InitSize=0;
       public CustomArrayList(){
           this.data=new Object[DefaultSize];
       }
       public void add(T num){
           if(isfull()){
               resize();
           }
           data[InitSize++]=num;
       }
       private boolean isfull(){
           return InitSize==DefaultSize;
       }
       private void resize(){
           Object[] temp=new Object[DefaultSize*2];
           for(int i=0;i<temp.length;i++){
               temp[i]=data[i];
           }
           data=temp;
       }
      public T get(int index){
      return data[index];
}
    }

Will it run? No! because data is an object of Object class and function want to return T type. We know that data will always contain T type variables but Compiler don't know that! Compiler only knows that data can contain anything belonging to Object class, hence according to compiler we can't assign a string to integer, therefore we need to typecast it!

 class CustomArrayList<T>{
       private Object[] data;
       private static int DefaultSize=10;
       private int InitSize=0;
       public CustomArrayList(){
           this.data=new Object[DefaultSize];
       }
       public void add(T num){
           if(isfull()){
               resize();
           }
           data[InitSize++]=num;
       }
       private boolean isfull(){
           return InitSize==DefaultSize;
       }
       private void resize(){
           Object[] temp=new Object[DefaultSize*2];
           for(int i=0;i<temp.length;i++){
               temp[i]=data[i];
           }
           data=temp;
       }
      public T get(int index){
      return (T)(data[index]);
}
    }

This will work fine!

I hope, you are able to understand the concept of Generics in Java, although Generics is very easy but the problem arises when we get error of instantiating Generics variable. Otherwise Generics is just like parametrized coordinates!