Create your own LinkedList in Java

As a Java developer, we need to frequently use the collection framework. Have you ever tried to create your own any of the collection classes in Java? Here we go, we will see how to create our own LinkedList in Java.

We will create a very simple class with add and get methods. Also, the LinkedList class of collection framework is doubly LinkedList but we will singly LinkedList.

Line 36 to 42, we have created an inner class i.e Node with a generic type T. This class has 2 fields:

  1. item field is a generic type that will hold an actual value of LinkedList node.
  2. next field is a Node type that holds the address of the next node of the LinkedList.
We have also defined a constructor to set value for the item field.

In lines 4 and 5, we have created an instance variable of type Node in MyLinkedList class i.e. first and last. The field first will always hold the first node of the LinkedList and the field last will always hold the node of LinkedList. Now the question is, why the last variable? The answer is very simple: it will always hold the last node of the LinkedList. By doing this, we don't need to traverse through the whole LinkedList to add a new element. Each time we will add a new element, the last field will point to it.

Line 6, we have defined a size variable. We will use this variable to check the index out of bound.

In lines 8 to 19, we have defined the add() method. This method accepts a generic type of value. We have assigned a value of the last variable to the temp variable and we have created and assigned a new node to the last variable in lines 10 and 11. We have a null check on the temp variable in line 12. If it is null, it means LinkedList is empty and we are adding a first node of the LinkedList so we marked the first node as same as the last node in line 13. If LinkedList is not empty, we will add our newly created last element to next of temp and temp becomes the second last element. Since a temp is a local variable of add() method, it will no longer available once the execution of the add method is finished.

Now let's discuss the get() method. We have defined this method from line 27 to 34. This method has an index of int type as a parameter. It returns the requested index element. First of all, it checks that the provided index is valid nor not by calling a private method checkValidIndex() in line 28. The get method() simply iterate through each element of LinkedList till it reaches to requested index. First of all, it assigns the first node to the temp variable then it temp to next node in each iteration. Please note here: we have not moved to the first element because once it is moved, we will not any variable which holds to first node.


Popular posts from this blog

Data types and Literals in Java

Java's Magic: Bytecode