Given a singly linked list and a position, delete a linked list node at the given position.
Example:
If node to be deleted is root, simply delete it. To delete a middle node, we must have pointer to the node previous to the node to be deleted. So if positions is not zero, we run a loop position-1 times and get pointer to the previous node.
Below is the implementation of above idea.
C/C++
// A complete working C program to delete a node in a linked list // at a given position #include #include // A linked list node struct Node { int data; struct Node *next; }; /* Given a reference [pointer to pointer] to the head of a list and an int, inserts a new node on the front of the list. */ void push[struct Node** head_ref,int new_data] { struct Node* new_node = [struct Node*]malloc[sizeof[struct Node]]; new_node->data = new_data; new_node->next = [*head_ref]; [*head_ref] = new_node; } /* Given a reference [pointer to pointer] to the head of a list and a position, deletes the node at the given position */ void deleteNode[struct Node **head_ref,int position] { // If linked list is empty if [*head_ref == NULL] return; // Store head node struct Node* temp = *head_ref; // If head needs to be removed if [position == 0] { *head_ref = temp->next;// Change head free[temp];// free old head return; } // Find previous node of the node to be deleted for [int i=0; temp!=NULL && inext; // If position is more than number of ndoes if [temp == NULL || temp->next == NULL] return; // Node temp->next is the node to be deleted // Store pointer to the next of node to be deleted struct Node *next = temp->next->next; // Unlink the node from linked list free[temp->next];// Free memory temp->next = next;// Unlink the deleted node from list } // This function prints contents of linked list starting from // the given node void printList[struct Node *node] { while [node != NULL] { printf[" %d ", node->data]; node = node->next; } } /* Drier program to test above functions*/ int main[] { /* Start with the empty list */ struct Node* head = NULL; push[&head, 7]; push[&head, 1]; push[&head, 3]; push[&head, 2]; push[&head, 8]; puts["Created Linked List: "]; printList[head]; deleteNode[&head, 4]; puts[" Linked List after Deletion at position 4: "]; printList[head]; return 0; } |
Java
// A complete working Java program to delete a node in a linked list // at a given position class LinkedList { Node head;// head of list /* Linked list Node*/ class Node { int data; Node next; Node[int d] { data = d; next =null; } } /* Inserts a new Node at front of the list. */ public void push[int new_data] { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node =new Node[new_data]; /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Given a reference [pointer to pointer] to the head of a list and a position, deletes the node at the given position */ void deleteNode[int position] { // If linked list is empty if [head ==null] return; // Store head node Node temp = head; // If head needs to be removed if [position ==0] { head = temp.next;// Change head return; } // Find previous node of the node to be deleted for [int i=0; temp!=null && inext is the node to be deleted // Store pointer to the next of node to be deleted Node next = temp.next.next; temp.next = next;// Unlink the deleted node from list } /* This function prints contents of linked list starting from the given node */ public void printList[] { Node tnode = head; while [tnode !=null] { System.out.print[tnode.data+" "]; tnode = tnode.next; } } /* Drier program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void main[String[] args] { /* Start with the empty list */ LinkedList llist =new LinkedList[]; llist.push[7]; llist.push[1]; llist.push[3]; llist.push[2]; llist.push[8]; System.out.println[" Created Linked list is: "]; llist.printList[]; llist.deleteNode[4];// Delete node at position 4 System.out.println[" Linked List after Deletion at position 4: "]; llist.printList[]; } } |
Python
# Python program to delete a node in a linked list # at a given position # Node class class Node: # Constructor to initialize the node object def __init__[self, data]: self.data= data self.next = None class LinkedList: # Constructor to initialize head def __init__[self]: self.head= None # Function to insert a new node at the beginning def push[self, new_data]: new_node= Node[new_data] new_node.next = self.head self.head= new_node # Given a reference to the head of a list # and a position, delete the node at a given position def deleteNode[self, position]: # If linked list is empty if self.head== None: return # Store head node temp= self.head # If head needs to be removed if position== 0: self.head= temp.next temp= None return # Find previous node of the node to be deleted for iin range[position-1 ]: temp= temp.next if tempis None: break # If position is more than number of nodes if tempis None: return if temp.next is None: return # Node temp.next is the node to be deleted # store pointer to the next of node to be deleted next = temp.next.next # Unlink the node from linked list temp.next = None temp.next = next # Utility function to print the linked LinkedList def printList[self]: temp= self.head while[temp]: print " %d " %[temp.data], temp= temp.next # Driver program to test above function llist= LinkedList[] llist.push[7] llist.push[1] llist.push[3] llist.push[2] llist.push[8] print "Created Linked List: " llist.printList[] llist.deleteNode[4] print " Linked List after Deletion at position 4: " llist.printList[] # This code is contributed by Nikhil Kumar Singh[nickzuck_007] |
Output:Created Linked List: 8 2 3 1 7 Linked List after Deletion at position 4: 8 2 3 1
Thanks to Hemanth Kumar for suggesting initial solution. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above