Singly Linked List Implementation using generics in Java

In previous post, we saw the implementation of linked list without Generics where we can add any object to linked list in constant time (Time Complexity – O(1) ).Now, in this post, we will use the JAVA Generics to create a Singly linked list of any object type.Also, we will add more functionality to singly linked list, like adding the element at first position and at any particular position.

Node:

First, we will create the node class with Generics Node<T>. Type of data variable will be T and type of node variable will be Node<T>.Refer the below code snippet.

 

SinglyLinkedList:

Create SinglyLinkedList class with Generics SinglyLinkedList <T>. Type of node variable will be Node<T>. Now, we will implement the below methods.[Try Yourself]

  1. add(T data) – Adding the element at last.
  2. addAtFirst(T data)- Add the element at first position.
  3. add(T data , int index)- Add the element at particular position.

To add the element at particular position:

  1. In above example, if we need to add the element at position i=3 , break the linked list into two part.Left part consists of elements i=0 , i=1 and i=2 . Right part consists of element i=3 and i=4.
  2. Set the next node of  i=2  as newly created node.
  3. Set the next node of newly created node as right node (i=4)

To test the above implementation, we will create a simple DTO Item.java and create the SinglyLinkedList of generic type <Item> in main method.

Output:

****** ADDING Items TO END OF THE LINKED LIST ******
Items : [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

****** ADDING Items TO START OF THE LINKED LIST ******
Items : [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

****** ADDING Items AT PARTICULAR POSITION THE LINKED LIST ******
Items : [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=105, itemName=Samsung Pro Plus, price=500.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0]]

 

We could see the above example where we added the Item at last, first and position 2 in SinglyLinkedList. Here, we are allowing the duplicate entry in SinglyLinkedList. Can we implement these methods to avoid duplicate? [Try Yourself]

Going forward, we will retain the above code and keep adding the new methods. In next post, we will see the delete operation on linked list.

Hope you like this post. Please leave your comments/suggestions.

You may like –

 

Top