Friday, October 22, 2010

Deleting a middle node from a single linked list when pointer to the previous node is not available

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/delete-non-tail-node-in-linked-list-given-only-access-to-that-node/.
Problem
Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

Solution
If we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following:
We have a list looking like:

......... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... 

and we need to delete Node(i).

  1. Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
  2. delete the second Node(i+1), it doesn't require pointer to the previous node.
Pseudocode:
As the solution given here:
void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}


Here the problem is we are not actually deleting the node, but just replacing the value from the next node. Hence it is sort of quiz. Moreover, if some node is already referring to pointer(i+1) (not data), then it may be problem.

0 comments:

Post a Comment