9

How to delete a node in a singly link list with only one pointer pointing to node to be deleted?

[Start and end pointers are not known, the available information is pointer to node which should be deleted]

3 Answers 3

17

You can delete a node without getting the previous node, by having it mimic the following node and deleting that one instead:

void delete(Node *n) {
  if (!is_sentinel(n->next)) {
    n->content = n->next->content;
    Node *next = n->next;
    n->next = n->next->next;
    free(next);
  } else {
    n->content = NULL;
    free(n->next);
    n->next = NULL;
  }
}

As you can see, you will need to deal specially for the last element. I'm using a special node as a sentinel node to mark the ending which has content and next be NULL.

UPDATE: the lines Node *next = n->next; n->next = n->next->next basically shuffles the node content, and frees the node: Image that you get a reference to node B to be deleted in:

   A           / To be deleted
  next   --->  B
              next  --->    C
                           next ---> *sentinel*

The first step is n->content = n->next->content: copy the content of the following node to the node to be "deleted":

   A           / To be deleted
  next   --->  C
              next  --->    C
                           next ---> *sentinel*

Then, modify the next points:

   A           / To be deleted
  next   --->  C       /----------------
              next  ---|    C          |
                           next ---> *sentinel*

The actually free the following element, getting to the final case:

   A           / To be deleted
  next   --->  C
              next  --->    *sentinel*
5
  • Node *next = n->next; n->next = n->next->next; can you please elaborate this more?
    – user215968
    Dec 25, 2009 at 5:45
  • If linked list is long enough then will shifting contents be a feasible solution?
    – user215968
    Dec 25, 2009 at 5:48
  • @unknown, yes, it would a feasible solution. This approach might complicate aliasing (another code holds a reference to the affected nodes and such); but you'll have that anyway.
    – notnoop
    Dec 25, 2009 at 5:55
  • 1
    Note that this only works if you don't have pointers to the following node. Dec 25, 2009 at 6:16
  • 1
    Note that shifting doesn't really happen. You just copy content of one node into another. Actual length of the list does not matter.
    – vava
    Dec 25, 2009 at 6:30
16

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.

You can find some discussion on SO here.

4

The only sensible and safe option under such restrictions is to mark the node deleted without actually unlinking it, deferring that to a later time.

1
  • Not the only option but a good one none-the-less so +1. We do that in our system quite a bit with mark-unused / deferred deletes.
    – Adisak
    Dec 26, 2009 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.