ansaurus

Question

Answer 1

+13 A:

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*

notnoop 2009-12-25 05:41:25

Node *next = n->next;n->next = n->next->next;can you please elaborate this more?

2009-12-25 05:45:37

If linked list is long enough then will shifting contents be a feasible solution?

2009-12-25 05:48:41

@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 2009-12-25 05:55:00

Very creative solution! +1

Marc W 2009-12-25 05:59:07

Note that this only works if you don't have pointers to the following node.

Jim Ferrans 2009-12-25 06:16:40

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 2009-12-25 06:30:28

Answer 2

+3 A:

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.

Nikolai N Fetissov 2009-12-25 05:44:10

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 2009-12-26 00:42:08

Answer 3

+10 A:

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.

codaddict 2009-12-25 05:54:58

ansaurus

tags:

views:

answers:

Delete a node in singly link list

related questions