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.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
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]
- add(T data) – Adding the element at last.
- addAtFirst(T data)- Add the element at first position.
- add(T data , int index)- Add the element at particular position.
To add the element at particular position:
- 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.
- Set the next node of i=2 as newly created node.
- Set the next node of newly created node as right node (i=4)
package com.study.singlyLinkedList;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
Node<T> newNode = new Node<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left node as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
private Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
To test the above implementation, we will create a simple DTO Item.java and create the SinglyLinkedList of generic type <Item> in main method.
package com.study.DTO;
public class Item {
private Integer itemId;
private String itemName;
private Double price;
public Item(Integer itemId, String itemName, Double price) {
super();
this.itemId = itemId;
this.itemName = itemName;
this.price = price;
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
public String getItemName() {
return itemName;
}
public void setItemName(String itemName) {
this.itemName = itemName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
@Override
public String toString() {
return "Item [itemId=" + itemId + ", itemName=" + itemName + ", price=" + price + "]";
}
}
package com.study.singlyLinkedList;
import com.study.DTO.Item;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Item> linkedList=new SinglyLinkedList<Item>();
System.out.println("****** ADDING Items TO END OF THE LINKED LIST ******");
linkedList.add(new Item(101, "IPhone-5S", 200.00));
linkedList.add(new Item(102, "IPhone-6S", 500.00));
linkedList.add(new Item(103, "IPhone-XX", 1000.00));
System.out.println("Items : "+linkedList);
System.out.println(" ");
System.out.println("****** ADDING Items TO START OF THE LINKED LIST ******");
linkedList.addAtFirst(new Item(104, "Samsung Pro", 300.00));
System.out.println("Items : "+linkedList);
System.out.println(" ");
System.out.println("****** ADDING Items AT PARTICULAR POSITION THE LINKED LIST ******");
linkedList.add(new Item(105, "Samsung Pro Plus", 500.00) , 2);
System.out.println("Items : "+linkedList);
}
}
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 –
- Singly Linked List Implementation using in java.
- Delete/Remove operations in Linked list.
- Implementation of Index based Linked List.
- Reverse a Singly Linked List.
- Find the middle element of a Singly Linked List.
- Merge sort for Linked List in Java.
- Remove duplicate node from linked list.
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
