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

Question

It's definitely more a quiz rather than a real problem. However, 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. Copy the NEXT of second Node(i+1) into a temporary variable.
3. Now Delete the second Node(i+1), it doesn't require pointer to the previous node.

Pseudocode:

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;
}

Mike.

Let's assume a list with the structure

A -> B -> C -> D

If you only had a pointer to B and wanted to delete it, you could do something like

tempList = B->next;
*B = *tempList;
free(tempList);

The list would then look like

A -> B -> D

but B would hold the old contents of C, effectively deleting what was in B. This won't work if some other piece of code is holding a pointer to C. It also won't work if you were trying to delete node D. If you want to do this kind of operation, you'll need to build the list with a dummy tail node that's not really used so you guarantee that no useful node will have a NULL next pointer. This also works better for lists where the amount of data stored in a node is small. A structure like

struct List { struct List *next; MyData *data; };

would be OK, but one where it's

struct HeavyList { struct HeavyList *next; char data[8192]; };

would be a bit burdensome.

Not possible.

There are hacks to mimic the deletion.

But none of then will actually delete the node the pointer is pointing to.

The popular solution of deleting the following node and copying its contents to the actual node to be deleted has side-effects if you have external pointers pointing to nodes in the list, in which case an external pointer pointing to the following node will become dangling.

I appreciate the ingenuity of this solution (deleting the next node), but it does not answer the problem's question. If this is the actual solution, the correct question should be "delete from the linked list the VALUE contained in a node on which the pointer is given". But of course, the correct question gives you a hint on solution. The problem as it is formulated, is intended to confuse the person (which in fact has happened to me, especially because the interviewer did not even mention that the node is in the middle).

One approach would be to insert a null for the data. Whenever you traverse the list, you keep track of the previous node. If you find null data, you fix up the list, and go to the next node.

The best approach is still to copy the data of the next node into the node to be deleted, set the next pointer of the node to the next node's next pointer, and delete the next node.

The issues of external pointers pointing to the node to be deleted, while true, would also hold for the next node. Consider the following linked lists:

A->B->C->D->E->F and G->H->I->D->E->F

In case you have to delete node C (in the first linked list), by the approach mentioned, you will delete node D after copying the contents to node C. This will result in the following lists:

A->B->D->E->F and G->H->I->dangling pointer.

In case you delete the NODE C completely, the resulting lists will be:

A->B->D->E->F and G->H->I->D->E->F.

However, if you are to delete the node D, and you use the earlier approach, the issue of external pointers is still there.

The initial suggestion was to transform:

a -> b -> c

to:

a ->, c

If you keep the information around, say, a map from address of node to address of the next node then you can fix the chain the next time to traverse the list. If need to delete multiple items before the next traversal then you need to keep track of the order of deletes (i.e. a change list).

The standard solution is consider other data structures like a skip list.