Delete operation in Linked list

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:

  1. If root node is null , no need to do anything. Return false.
  2. 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:

  1. If root node is null , no need to do anything. Return false.
  2. If input index is negative or greater than ( size -1) , throw IndexOutOfBoundsException
  3. 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.
  4. 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.
  5. 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]

 

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.

Below is the test class, where we will add some items to linked list and later we will remove some items.

 

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 –

Top