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.

Comments

Post a Comment

Popular posts from this blog

Data types and Literals in Java

Image
Data types Data types category:   Data types summary: Literals A constant value which can be assigned to variable is called "Literal". Integral Literals All possible value of Integral data type(byte, short, int and long) are called Integral Literals. Default Value: By default every Integral literal is int type. When you assign a value in long data byte and that value is more than 2147483647(Maximum value for int) then compiler will give you error. Ex: long a = 3000000000; Error: The literal 3000000000 of type int is out of range  Even though we have used long data type and value is also within range of long but still compiler gives error because every integral literal is int type. We can resolve this error by specifying long type explicitly. We can specify long type by suffixing l or L . Ex: long a = 3000000000L; Number System: Integral Literal can be represented as Decimal, Octal and Hexadecimal number systems. Let's
Read more

How to define Auxiliary Constructor in case class in Scala

We have seen case class previously. We had discussed what is case class, how to create object of case class, list of boilerplate code generated for case class. If you don't know case class, I recommend to understand case class first. Let us revise case class declaration. case class Person(id:Int, name: String) Person class is declared with primary constructor where id and name are parameter. So good so far. The constructor which is not primary constructor, other than primary constructors and overloaded to primary constructor are called auxiliary constructor. How will you declare Auxiliary(other overloaded) constructors. What is syntax of creating auxiliary constructor. Please note that constructors in case class are not really constructor. Actually these are apply methods on companion object. Auxiliary constructor in case class are different than regular class. We can add auxiliary constructors in case class by adding apply() methods in companion object of case class
Read more

equals() method of Object class in Java

Image
When you compare two object references using == operator, it evaluate to true only when both references refer to same object. public class Person { private Integer id; private String name; public Person(Integer id, String name) { this.id = id; this.name = name; } public static void main(String[] args) { Person p1 = new Person(1, "Prithvi"); Person p2 = p1; Person p3= new Person(1, "Prithvi"); System.out.println(p1==p2); System.out.println(p1==p3); } } Output: true false We have created 3 references of Person class. Object references p1 and p2 both refer to same object so comparison evaluate to true. Comparison of p1 and p3 evaluate to false, even though p3 has same contents as p1 but refer to different object so comparison returns false. Below image explains this - Objects p3 and p1 are meaningfully equal. We must have some way to see their content are same or not. But the question is, How will you compare two different object
Read more