How to delete a node at a given position of a single linked list?

Delete a Node from single linked list using head to tail iterations

This is a program to delete a particular node in a single linked list without knowing the previous node. The usual logic for deleting a node in a single linked list is very simple. Iterate from head to the previous node of the target node. We will break the loop when node->next = target node. Now get the next node to the target and update the next pointer. We will make a link between previous to target->next.

 void delete_node(node *target)
{
  if(target == NULL || head == NULL) return;
  prev = NULL;
  node = head;
  while (node && node != target) {
    prev = node;
    node = node->next;
  }
  /* Order of nodes: prev > target > next */
  if(prev) {
    prev->next = target->next;
  } else {
    head = head->next;
  }
  free(target);
}

Delete a Node from single linked list without head pointer

Delete a node from a single linked list without a head pointer is different than deleting a node using iteration. This is also the same as deleting a node from a single linked list at a given position. We have no way to know the previous node as this is a single linked list. So we used an indirect technique. We take a node and goto the next. We have two pointer current and next. We can copy the content of the next to the current. Actually, all the content of the next node is copied to the current and thus the next node becomes a redundant one. So we can delete it. The below diagram shows how it is happening.

delete a particular-node of single linked list

Delete a Node from single linked list without head pointer code

We are constructing a single linked list of 10 nodes to demonstrate this delete node mechanism. We are using the iteration of the linked list only to display the entire list. We are taking the node pointer from the user as the input. Before deletion, we have 10 nodes and the user has given the 7th node address to delete. The core routine is doing a sanity check on the pointer location of the node. Also, it is checking if the next node is null or not. In both cases, this delete operation can not be performed.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
  int value;
  struct node *next;
}node;

int main(int argc, char *argv[])
{
  int i;
  node *n[10];
  node *tmp, *del;
  /* Construct a linked list of 10 nodes */
  for (i = 0; i < 10; i++)
  {
    n[i] = (node *) malloc (sizeof(node));
    n[i]->value = i + 1;
    n[i]->next = NULL;
    if (i > 0) {
          n[i -1]->next = n[i];
    }    
  }
  tmp = n[0];
  printf ("Linked List\n");
  while (tmp)
  {
    printf ("Node %p Value %d\n", tmp, tmp->value);
    tmp = (node *)tmp->next;
  }
  printf ("Enter a node to delete :");
  scanf ("%p", &tmp);
  
  /* Delete a Node from single linked list without head pointer */
  if (tmp && tmp->next) {
    printf ("Deleting %p, value %d\n", tmp, tmp->value);
    
    /* Go to next node */
    del = (node *)tmp->next;
    
    /* Copy next node content to this target node */
    *tmp = *del;
    
    /* free this node */
    free(del);

  } else {
    /* Last node has next as NULL, we cannot delete this using this logic */
    printf ("Either last node or value is NULL, not deleted!\n"); 
  }
  printf ("Linked List\n");
  tmp = n[0];
  while(tmp)
  {
    printf ("Node %p Value %d\n", tmp, tmp->value);
    tmp = tmp->next;
  }
  return 0;
}

Delete a Node from single linked list without head pointer program output

We are deleting the 7th node successfully. After that user is giving the last node to delete. As we already know that node->next is NULL. So it cannot be deleted. 

Linked List
Node 00471880 Value 1
Node 004718A0 Value 2
Node 004718B0 Value 3
Node 00478DB8 Value 4
Node 00478DC8 Value 5
Node 00478DD8 Value 6
Node 00478DE8 Value 7
Node 00478DF8 Value 8
Node 00478E08 Value 9
Node 00478E18 Value 10
Enter a node to delete :00478DE8
Deleting 00478DE8, value 7
Linked List
Node 00471880 Value 1
Node 004718A0 Value 2
Node 004718B0 Value 3
Node 00478DB8 Value 4
Node 00478DC8 Value 5
Node 00478DD8 Value 6
Node 00478DE8 Value 8
Node 00478E08 Value 9
Node 00478E18 Value 10

Linked List
Node 00031880 Value 1
Node 000318A0 Value 2
Node 000318B0 Value 3
Node 00038DB8 Value 4
Node 00038DC8 Value 5
Node 00038DD8 Value 6
Node 00038DE8 Value 7
Node 00038DF8 Value 8
Node 00038E08 Value 9
Node 00038E18 Value 10
Enter a node to delete :00038E18
Either last node or value is NULL, not deleted!
Linked List
Node 00031880 Value 1
Node 000318A0 Value 2
Node 000318B0 Value 3
Node 00038DB8 Value 4
Node 00038DC8 Value 5
Node 00038DD8 Value 6
Node 00038DE8 Value 7
Node 00038DF8 Value 8
Node 00038E08 Value 9
Node 00038E18 Value 10

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions