Thursday, December 29, 2011

Deleting a node from a singly linked link list

Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.

Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do?

We can easily get away by moving the data from the next node into the current node and then deleting the next node. This solution has O(1) runtime. Here’s some code to illustrate this simple logic.

void deleteNode( Node * node )
{
    Node * temp = node->next;
    node->data = node->next->data;
    node->next = temp->next;
    free(temp);
}

Deleting the node in java - See the code here.

0 comments:

Post a Comment