Deletion in linked list in C++ : Linked List – 3

Question. We are given a singly linked list and a pointer to a node to be deleted. We wish to delete that node.

Solution.

We could proceed as follows:

——–

// the function deletes node pointed to by x from the linked list.

// returns true if deletion was successful; else, returns false.

bool deleteNode ( Node **head, Node *x)

{

if ( ! head )

// empty list

return false;

 

Node *curr = *head;

if ( x == *head)  //special case: delete first node

{

head = head -> next ;

delete curr;

return true;

}

while (curr != 0   &&   curr -> next != x)

curr = curr -> next;

if ( ! curr)

//node not found.

return false;

//deleting the node

curr -> next = x -> next;

delete x;

return true;

}

——

Note that we need to pass a pointer to the head pointer since the location the head pointer points to may change (in case of deletion of first node).

——-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: