banner



how to delete a node in a linked list c++

Deleting a node in linked list

Delete a given node from the linked list.




Example

Linked List : 10 20 30 NULL


Input

20

Output

10 30 NULL


Input

30

Output

10 20 NULL




Algorithm

1. If the head node has the given key,

     make the head node points to the second node and free its memory.

2. Otherwise,

     From the current node, check whether the next node has the given key

     if yes, make the current->next = current->next->next and free the memory.

     else, update the current node to the next and do the above process (from step 2) till the last node.




1. Head node has the given key


              void              deleteNode(struct              node              **head,              int              key) {              //temp is used to freeing the memory              struct              node              *temp;              

//key found on the head node. //move to head node to the next and free the head. if(*head->data == key) { temp = *head; //backup the head to free its memory *head = (*head)->next; free(temp); }

}

Visual Representation

Let's delete data 10 (head node).


linked list delete the head node.

1. Make the head points to the next node.

2. Free the head node's memory.

3. Finally, the new linked list.





2. For other nodes (Non-Head)


              void              deleteNode(struct              node              **head,              int              key) {              //temp is used to freeing the memory              struct              node              *temp;              //key found on the head node.              //move to head node to the next and free the head.              if((*head)->data              ==              key)       {           temp              =              *head;              //backup to free the memory              *head              =              (*head)->next;           free(temp);       }              

else { struct node *current = *head; while(current->next != NULL) { //if yes, we need to delete the current->next node if(current->next->data == key) { temp = current->next; //node will be disconnected from the linked list. current->next = current->next->next; free(temp); break; } //Otherwise, move the current node and proceed else current = current->next; } }

}

Visual Representation

Let's delete data 20.


linked list delete the node.

1. Make the current node points to the head node. (current => data = 10).

2. current => next. (current=>next=>data = 20).

3. current => next => next. (current=>next=>next=>data = 30).

4. We have to remove the node 20. Since current => next = 20 we can remove the node by setting current => next = current =>next => next. And then free the node.

5. Finally, the new linked list.




Implementation of deleting a node in linked list

Example

              /*                              * Program: Deleting a node in the linked list                              * Language: C                              */              #include<stdio.h>              #include<stdlib.h>              struct              node {              int              data;              struct              node              *next; };              void              addLast(struct              node              **head,              int              val) {              //create a new node              struct              node              *newNode              =              malloc(sizeof(struct              node));     newNode->data              =              val;     newNode->next              =              NULL;              //if head is NULL, it is an empty list              if(*head              ==              NULL)              *head              =              newNode;              //Otherwise, find the last node and add the newNode              else              {              struct              node              *lastNode              =              *head;              //last node's next address will be NULL.              while(lastNode->next              !=              NULL)         {             lastNode              =              lastNode->next;         }              //add the newNode at the end of the linked list              lastNode->next              =              newNode;     }  }              

void deleteNode(struct node **head, int key) { //temp is used to freeing the memory struct node *temp; //key found on the head node. //move to head node to the next and free the head. if((*head)->data == key) { temp = *head; //backup to free the memory *head = (*head)->next; free(temp); } else { struct node *current = *head; while(current->next != NULL) { //if yes, we need to delete the current->next node if(current->next->data == key) { temp = current->next; //node will be disconnected from the linked list. current->next = current->next->next; free(temp); break; } //Otherwise, move the current node and proceed else current = current->next; } } }

void printList(struct node *head) { struct node *temp = head; //iterate the entire linked list and print the data while(temp != NULL) { printf("%d ->", temp->data); temp = temp->next; } printf("NULL \n "); } int main() { struct node *head = NULL; addLast(&head,10); addLast(&head,20); addLast(&head,30); printf("Linked List Elements: \n "); printList(head); //delete first node deleteNode(&head,10); printf("Deleted 10. The New Linked List: \n "); printList(head); //delete last node deleteNode(&head,30); printf("Deleted 30. The New Linked List: \n "); printList(head); //delete 20 deleteNode(&head,20); printf("Deleted 20. The New Linked List: \n "); printList(head); return 0; }


Topics You Might Like

how to delete a node in a linked list c++

Source: https://www.log2base2.com/data-structures/linked-list/deleting-a-node-in-linked-list.html

Posted by: howellhishousy.blogspot.com

0 Response to "how to delete a node in a linked list c++"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel