Easy Delete a Linked List Node at a Given Position in Java

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

We will be given a circular linked list and a position, and we need to delete the element present at that position in the list.

Note: we need to follow 0 based indexing while deleting the nodes

Problem Statement Understanding

Let's try to understand the problem with the help of an example.

If the linked list given to us is:

Now, if position = 0.

• Then, we need to delete the first node of the list, and after deletion, the list will now look like this:
  

If the position = 2.

• Then, we need to delete the third node, and the list after deletion will look like this:
  

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let's move to the approach section.

Approach

We will divide our problem into three sections:
1) When position = 0:
a) It means that we need to delete the first node of the circular linked list.
b) In this case, we need to reach the last node and then connect it with the second node.
c) After that, we will update the head pointer for the list.

2) When position = length of the list (we need to delete the last node):
a) In this case, we need to reach the last second node and connect it with the first node.

3) When we need to delete a middle node:
a) We need to keep track of node position while iterating the list.
b) when we find the node at the specified position, we need to connect its previous node with its next node.

Let's move to the algorithm section to see the above approach in more depth.

Algorithm

1) First, calculate the length of the list and save it in len variable.
2) Initialize a variable count by 1.
3) If the head is NULL, then it means that the list is empty, so return from the function.
4) If the position is less than 0 or greater than len, then return from the function.
5) If position == 0 then, call deleteFirstNode function:

• Initialize curr and left with the head of the list.
• Return from the function if the head is NULL.
• Make the head NULL and return from the function, if left->next is left (this is the case when there is only 1 node in the list).
• Run a while loop till left->next is not equal to head.
  • Inside the loop, advance left by one node and update curr with the next node of left.
• Now, when the loop is executed completely, connect the next pointer of left to the next node of curr.
• Update the head node by left->next.
• Delete the old head node, i.e., curr.
  6) If position == (len-1) then, call deleteLastNode function:
• Initialize the curr pointer with head and left with NULL.
• Return from the function if the head is NULL.
• Make the head NULL and return from the function, if curr->next is curr (this is the case when there is only 1 node in the list).
• Run a while loop till curr->next is not equal to head.
  • Inside the loop, save the value of curr in left and advance curr by one node.
• Now, when the loop is executed completely, connect the next pointer of left to the next node of curr.
• Update the head node by left->next.
• Delete the old head node, i.e., curr.
  7) Run a while loop till len is positive.
• If position is equal to count then,
  • Connect previous node's next pointer to current node's next pointer.
  • Delete the curr pointer and return from the function.
• Advance previous by one node and update curr to the node next to previous.
• Decrement len and increment count by one.
  8) Return from the function once while loop breaks.

Dry Run

Code Implementation

• C++
• C
• Java
• Python

#include                                      using namespace std;  class Node {     public:     int data;     Node* next;     Node(int d)     {         data = d;         next = NULL;     } }; // This function will print data of  // all the nodes present in the list void Display(Node* head) {     Node* temp = head;       // In case of an empty list:     if (head == NULL) {         printf("\nDisplay List is empty\n");         return;     }       // iterate the complete list     else {         do {             cout<<(temp->data);             temp = temp->next;             cout<<" ";         } while (temp != head);     }     cout<<'\n'; }  // This function calculates the  // number of nodes in the list int Length(Node* head) {     Node* temp = head;     int len = 0;       // in case of an empty list, return 0     if (head == NULL) {         return 0;     }       // iterate the complete list     else {         do {             temp = temp->next;             len++;         } while (temp != head);     }     return len; }  // This node deletes the first node // of the list void deleteFirstNode(Node** head) {     Node *left = *head, *curr = *head;       // if the list is empty     if (*head == NULL) {         printf("\nList is empty\n");         return;     }       // In case, the list has a single node      if (left->next == left) {         *head = NULL;         return;     }       // iterate the complete list     while (left->next != *head) {           left = left->next;         curr = left->next;     }       // left will be pointing to the last node      // and curr will be the head of the list     // so, we will connect left with the curr->next     left->next = curr->next;       // make second node as head node     *head = left->next;     free(curr);       return; }  // This function deletes the last // node of the list void deleteLastNode(Node** head) {     Node *curr = *head,  *left = NULL;       // if the list is empty     if (*head == NULL) {         printf("\nList is empty\n");         return;     }       // In case, the list has a single node      if (curr->next == curr) {         *head = NULL;         return;     }       //iterate the list      while (curr->next != *head) {         left = curr;         curr = curr->next;     }       left->next = curr->next;     *head = left->next;     free(curr);       return; }  void deleteAtPosition(Node** head, int position) {     // find length of the list     int len = Length(*head);     int count = 1;     Node *previous = *head, *curr = *head;       // check if the list is empty     if (*head == NULL) {         printf("\nDelete Last List is empty\n");         return;     }       // check if the given position is out of     // bound of the list     if (position >= len || position < 0) {         printf("\nposition is not Found\n");         return;     }       // first node deletion     if (position == 0) {         deleteFirstNode(head);         return;     }     // last node deletion     else if(position == len-1){         deleteLastNode(head);         return;     }       // iterate the complete list     while (len > 0) {           // delete the node when position is found         if (position == count) {             previous->next = curr->next;             free(curr);             return;         }         previous = previous->next;         curr = previous->next;         len--;         count++;     }     return; }  int main() {     Node *head = new Node(3);     head->next = new Node(7);     head->next->next = new Node(2);     head->next->next->next = new Node(5);     head->next->next->next->next = head;     cout<<"Original list ";     Display(head);     cout<<"After deleting third node ";     deleteAtPosition(&head,2);     Display(head);     cout<<"After deleting last node ";     deleteAtPosition(&head,Length(head)-1);     Display(head);     cout<<"After deleting first node ";     deleteAtPosition(&head,0);     Display(head); }                                  

#include                    #include                      struct Node {     int data;     struct Node* next; }; // This function will print data of  // all the nodes present in the list void Display(struct Node* head) {     struct Node* temp = head;       // In case of an empty list:     if (head == NULL) {         printf("\nDisplay List is empty\n");         return;     }       // iterate the complete list     else {         do {             printf("%d",temp->data);             temp = temp->next;             printf(" ");         } while (temp != head);     }     printf("\n"); } // This function calculates the  // number of nodes in the list int Length(struct Node* head) {     struct Node* temp = head;     int len = 0;       // in case of an empty list, return 0     if (head == NULL) {         return 0;     }       // iterate the complete list     else {         do {             temp = temp->next;             len++;         } while (temp != head);     }     return len; } // This node deletes the first node // of the list void deleteFirstNode(struct Node** head) {     struct Node* left = *head;      struct Node *curr = *head;       // if the list is empty     if (*head == NULL) {         printf("\nList is empty\n");         return;     }       // In case, the list has a single node      if (left->next == left) {         *head = NULL;         return;     }       // iterate the complete list     while (left->next != *head) {           left = left->next;         curr = left->next;     }       // left will be pointing to the last node      // and curr will be the head of the list     // so, we will connect left with the curr->next     left->next = curr->next;       // make second node as head node     *head = left->next;     free(curr);       return; } // This function deletes the last // node of the list void deleteLastNode(struct Node** head) {    struct Node *curr = *head,  *left = NULL;       // if the list is empty     if (*head == NULL) {         printf("\nList is empty\n");         return;     }       // In case, the list has a single node      if (curr->next == curr) {         *head = NULL;         return;     }       //iterate the list      while (curr->next != *head) {         left = curr;         curr = curr->next;     }       left->next = curr->next;     *head = left->next;     free(curr);       return; } void deleteAtPosition(struct Node** head, int position) {     // find length of the list     int len = Length(*head);     int count = 1;     struct Node *previous = *head, *curr = *head;       // check if the list is empty     if (*head == NULL) {         printf("\nDelete Last List is empty\n");         return;     }       // check if the given position is out of     // bound of the list     if (position >= len || position < 0) {         printf("\nposition is not Found\n");         return;     }       // first node deletion     if (position == 0) {         deleteFirstNode(head);         return;     }     // last node deletion     else if(position == len-1){         deleteLastNode(head);         return;     }       // iterate the complete list     while (len > 0) {           // delete the node when position is found         if (position == count) {             previous->next = curr->next;             free(curr);             return;         }         previous = previous->next;         curr = previous->next;         len--;         count++;     }     return; }  void push(struct Node** head_ref, int data) {     struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));     ptr1->data = data;     ptr1->next = *head_ref;       if (*head_ref != NULL) {           struct Node* temp = *head_ref;         while (temp->next != *head_ref)             temp = temp->next;         temp->next = ptr1;     }     else         ptr1->next = ptr1; /*For the first node */       *head_ref = ptr1; } int main() {     struct Node* head = NULL;     push(&head, 2);     push(&head, 5);     push(&head, 7);     push(&head, 8);     push(&head, 10);     printf("Original list ");     Display(head);     printf("After deleting third node ");     deleteAtPosition(&head,2);     Display(head);     printf("After deleting last node ");     deleteAtPosition(&head,Length(head)-1);     Display(head);     printf("After deleting first node ");     deleteAtPosition(&head,0);     Display(head); }                                                      

class DeletetionAtPos {   // structure for a node static class Node {     int data;     Node next; };   // Function to insert a node at the end of // a Circular linked list static Node Insert(Node head, int data) {     Node current = head;           // Create a new node     Node newNode = new Node();             // insert data into newly created node     newNode.data = data;       // check list is empty     // if not have any node then     // make first node it     if (head == null)     {         newNode.next = newNode;         head = newNode;         return head;     }       // if list have already some node     else     {           // move first node to last node         while (current.next != head)         {             current = current.next;         }           // put first or head node address         // in new node link         newNode.next = head;           // put new node address into last         // node link(next)         current.next = newNode;     }     return head; }   // Function print data of list static void Display( Node head) {     Node current = head;       // if list is empty, simply show message     if (head == null)     {         System.out.printf("\nDisplay List is empty\n");         return;     }       // traverse first to last node     else     {         do         {             System.out.printf("%d ", current.data);             current = current.next;         } while (current != head);     } }   // Function return number of nodes present in list static int Length(Node head) {     Node current = head;     int count = 0;       // if list is empty     // simply return length zero     if (head == null)     {         return 0;     }       // traverse first to last node     else     {         do         {             current = current.next;             count++;         } while (current != head);     }     return count; }   // Function delete First node of // Circular Linked List static Node DeleteFirst(Node head) {     Node previous = head, next = head;       // check list have any node     // if not then return     if (head == null)     {         System.out.printf("\nList is empty\n");         return null;     }       // check list have single node     // if yes then delete it and return     if (previous.next == previous)     {         head = null;         return null;     }       // traverse second to first     while (previous.next != head)     {         previous = previous.next;         next = previous.next;     }       // now previous is last node and     // next is first node of list     // first node(next) link address     // put in last node(previous) link     previous.next = next.next;       // make second node as head node     head = previous.next;       return head; }   // Function to delete last node of // Circular Linked List static Node DeleteLast(Node head) {     Node current = head, previous=null;       // check if list doesn't have any node     // if not then return     if (head == null)     {         System.out.printf("\nList is empty\n");         return null;     }       // check if list have single node     // if yes then delete it and return     if (current.next == current)     {         head = null;         return null;     }       // move first node to last     // previous     while (current.next != head)     {         previous = current;         current = current.next;     }       previous.next = current.next;     head = previous.next;           return head; }   // Function delete node at a given position // of Circular Linked List static Node DeleteAtPosition( Node head, int index) {     // Find length of list     int len = Length(head);     int count = 1;     Node previous = head, next = head;       // check list have any node     // if not then return     if (head == null)     {         System.out.printf("\nDelete Last List is empty\n");         return null;     }       // given index is in list or not     if (index >= len || index < 0)     {         System.out.printf("\nIndex is not Found\n");         return null;     }       // delete first node     if (index == 0)     {         head = DeleteFirst(head);         return head;     }       // traverse first to last node     while (len > 0)     {           // if index found delete that node         if (index == count)         {             previous.next = next.next;                           return head;         }         previous = previous.next;         next = previous.next;         len--;         count++;     }     return head; }   // Driver Code public static void main(String args[]) {     Node head = null;     head = Insert(head, 99);     head = Insert(head, 11);     head = Insert(head, 22);     head = Insert(head, 33);     head = Insert(head, 44);     head = Insert(head, 55);     head = Insert(head, 66);       // Deleting Node at position     System.out.printf("Initial List: ");     Display(head);     System.out.printf("\nAfter Deleting node at index 4: ");     head = DeleteAtPosition(head, 4);     Display(head);       // Deleting first Node     System.out.printf("\n\nInitial List: ");     Display(head);     System.out.printf("\nAfter Deleting first node: ");     head = DeleteFirst(head);     Display(head);       // Deleting last Node     System.out.printf("\n\nInitial List: ");     Display(head);     System.out.printf("\nAfter Deleting last node: ");     head = DeleteLast(head);     Display(head); } }                

                    class Node: 	def __init__(self, new_data): 		self.data = new_data 		self.next = None 		self.prev = None  # This function to insert a node at the end of a list def Insert(head, data):  	current = head 	 	newNode = Node(0)  	if (newNode == None): 	 		print("\nMemory Error\n") 		return None  	newNode.data = data  	if (head == None) : 		newNode.next = newNode 		head = newNode 		return head  	else:  		while (current.next != head): 		 			current = current.next  		newNode.next = head  		current.next = newNode 	 	return head   # This function will print data of all the nodes present in the list def Display(head):  	current = head  	# In case of an empty list: 	if (head == None): 	 		print("\nDisplay List is empty\n") 		return 	 	# iterate the complete list 	else: 	 		while(True): 			print( current.data,end=" ") 			current = current.next 			if (current == head): 				break 	 # This function calculates the number of nodes in the list def Length(head): 	current = head 	count = 0  	# in case of an empty list, return 0 	if (head == None): 	 		return 0  	# iterate the complete list 	else: 	 		while(True): 			current = current.next 			count = count + 1 			if (current == head): 				break 	 	return count  # This node deletes the first node of the list def deleteFirstNode(head): 	previous = head 	next = head  	if (head == None) : 		print("\nList is empty") 		return None 	 	if (previous.next == previous) : 	 		head = None 		return None 	 	while (previous.next != head): 		previous = previous.next 		next = previous.next 	 	previous.next = next.next  	head = previous.next  	return head  # This function deletes the last node of the list def DeleteLast(head): 	current = head 	temp = head 	previous = None  	if (head == None): 		print("\nList is empty") 		return None  	if (current.next == current) : 		head = None 		return None  	while (current.next != head): 		previous = current 		current = current.next 	 	previous.next = current.next 	head = previous.next 	 	return head  # This function delete node at a given position of List def DeleteAtPosition(head, index):  	# Find length of list 	len = Length(head) 	count = 1 	previous = head 	next = head  	# check if the list is empty 	if (head == None): 		print("\nDelete Last List is empty") 		return None 	 	# check if the given position is out of bound of the list 	if (index >= len or index < 0) : 		print("\nPosition is not Found") 		return None  	# first node deletion 	if (index == 0) : 		head = deleteFirstNode(head) 		return head  	# iterate the complete list 	while (len > 0): 	 		# delete the node when position is found 		if (index == count): 			previous.next = next.next 			 			return head 		 		previous = previous.next 		next = previous.next 		len = len - 1 		count = count + 1 	 	return head   head = None head = Insert(head, 3) head = Insert(head, 7) head = Insert(head, 2) head = Insert(head, 5)  print("Original List: ") Display(head) print("\nAfter deleting node at index 3: ") head = DeleteAtPosition(head, 2) Display(head)  print("\nAfter deleting last node: ") head = DeleteLast(head) Display(head)  print("\nAfter Deleting first node: ") head = deleteFirstNode(head) Display(head)                

Output

Original list 3 7 2 5
After deleting third node 3 7 5
After deleting last node 3 7
After deleting first node 7

Time Complexity: O(n), where n is the number of nodes in the list
[forminator_quiz id="5474″]

So, in this blog, we have tried to explain how you can delete nodes at different positions in a circular list in the most optimal way. If you want to practice more questions on linked lists, feel free to solve them at Prepbytes (Linked Lists).

herlitzsoread.blogspot.com

Source: https://www.prepbytes.com/blog/linked-list/deletion-at-different-positions-in-a-circular-linked-list/

Share this post