In previous post, we saw the implementation of different add operations on linked list.In this post, we will add the delete operation in linked list. We can delete the element of linked list by passing the object or by index. we are going to write the two methods detete(T data) and deleteByIndex(int index).We will have additional method clear() to remove all the elements of linked list.
delete(T data): In previous posts, we could see the add operations where we are allowing the duplicate entries in linked list. So, this delete method will remove the first occurrence of object if object exists and returns true. If data is not available, method will return false.
Steps:
- If root node is null , no need to do anything. Return false.
- If input data is the root element of linked list , update the root node with next node of root node(see method next()) in linked list. Reduce the size of linked list by one and return true.
3. If input data is not the root element, then we will call the method, deleteByIndex by passing the index(positive) of first occurrence of object.
deleteByIndex(int index) : This method will delete the data positioned at input index. Valid index range would be : 0 <= index <= size – 1 . Why -1 ? If linked list size is 10 then index starts from 0 to 9 both inclusive.
Steps:
- If root node is null , no need to do anything. Return false.
- If input index is negative or greater than ( size -1) , throw IndexOutOfBoundsException
- if index=0, means remove the first element. To remove first element, update the root node with next node of root node(see method next()) in linked list. Reduce the size of linked list by one and return true.
- If index = size – 1 , means remove the last element. To remove the last element, get the second last element of the linked list and set the next node of second last element as NULL. Reduce the size of linked list by one and return true.
- If 0 < index < size – 1 , get the left and right node of indexed node and set the next node of left node as right node. leftNode.nextNode = rightNode. Reduce the size of linked list by one and return true.
clear() : clear() method will reset the root node and size of the linked list. After calling the clear() method , size of linked list will be 0.
Below is the code implementation for delete operations in linked list.[Try Yourself]
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;
}
}
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 nose 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;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
this.node = null;
this.size = 0;
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
@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;
}
}
Create a Item.java class with equals and hashCode implementation to identify the equal objects.Here, based on the equals and hashCode implementation, if two objects have same itemId and itemName , both objects will be equal.
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 + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((itemId == null) ? 0 : itemId.hashCode());
result = prime * result + ((itemName == null) ? 0 : itemName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Item))
return false;
Item other = (Item) obj;
if (itemId == null) {
if (other.itemId != null)
return false;
} else if (!itemId.equals(other.itemId))
return false;
if (itemName == null) {
if (other.itemName != null)
return false;
} else if (!itemName.equals(other.itemName))
return false;
return true;
}
}
Below is the test class, where we will add some items to linked list and later we will remove some items.
package com.study.singlyLinkedList;
import com.study.DTO.Item;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Item> linkedList=new SinglyLinkedList<Item>();
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));
linkedList.addAtFirst(new Item(104, "Samsung Pro", 300.00));
linkedList.add(new Item(105, "Samsung Pro Plus", 500.00) , 2);
System.out.println("****** ADDING DUPLICATE Item TO END OF THE LINKED LIST ******");
linkedList.add(new Item(101, "IPhone-5S", 200.00));
System.out.println("AFTER ADDING ALL ITEMS , size: "+linkedList.size() + " "+linkedList);
System.out.println(" ");
System.out.println("****** REMOVE FIRST Item IPhone-5S ******");
linkedList.delete(new Item(101, "IPhone-5S", 200.00));
System.out.println("****** AFTER REMOVING Item IPhone-5S ******");
System.out.println("Items size: "+linkedList.size() + " "+ linkedList);
System.out.println(" ");
System.out.println("****** REMOVE Item IPhone-XX ******");
linkedList.delete(new Item(103, "IPhone-XX", 1000.00));
System.out.println("****** AFTER REMOVING Item IPhone-XX ******");
System.out.println("Items size: "+linkedList.size() + " "+ linkedList);
System.out.println(" ");
System.out.println("****** REMOVE Item at index 1 ******");
linkedList.deleteByIndex(1);
System.out.println("****** AFTER REMOVING Item at index 1 ******");
System.out.println("Items size: "+linkedList.size() + " "+ linkedList);
System.out.println(" ");
try {
System.out.println("****** PASSING INVALID INDEX TO DELETE ELEMENT : EXPECTING IndexOutOfBoundsException******");
System.out.println(" ");
linkedList.deleteByIndex(3);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("****** CLEAR THE LINKED LIST ******");
linkedList.clear();
System.out.println("****** CLEARING LIST ******");
System.out.println("Items : "+linkedList);
System.out.println(" ");
}
}
Output:
****** ADDING DUPLICATE Item TO END OF THE LINKED LIST ******
AFTER ADDING ALL ITEMS , size: 6 [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],Item [itemId=101, itemName=IPhone-5S, price=200.0]]
****** REMOVE FIRST Item IPhone-5S ******
****** AFTER REMOVING Item IPhone-5S ******
Items size: 5 [Item [itemId=104, itemName=Samsung Pro, price=300.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],Item [itemId=101, itemName=IPhone-5S, price=200.0]]
****** REMOVE Item IPhone-XX ******
****** AFTER REMOVING Item IPhone-XX ******
Items size: 4 [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=105, itemName=Samsung Pro Plus, price=500.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]
****** REMOVE Item at index 1 ******
****** AFTER REMOVING Item at index 1 ******
Items size: 3 [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]
****** PASSING INVALID INDEX TO DELETE ELEMENT : EXPECTING IndexOutOfBoundsException******
****** CLEAR THE LINKED LIST ******
****** CLEARING LIST ******
Items : []
java.lang.IndexOutOfBoundsException: Index not available.
at com.study.singlyLinkedList.SinglyLinkedList1.deleteByIndex(SinglyLinkedList1.java:172)
at com.study.singlyLinkedList.TestSinglyLinkedList.main(TestSinglyLinkedList.java:41)
Hope you like this post. Please leave your comments/suggestions.
In next post, we will see the implementation to get the element by index and get the index of any element in linked list.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- 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.
