Sinlge linked List -> Delete Using One Pointer

[yfredmann]

Hi dear friends,

This problem might be so popular to some of you, but I couldn't be able to do it myself.

The problem: How to delete a node from a single linked list using only one pointer?

Where the target node to be deleted has a key field, and based on a match, let us say at first a sequential search, this node has to be deleted.

What other ways that a singly linked list can be searched through other than the sequential search, assuming perhaps the contents are sorted, does the binary search works here or some other algorithm?

Thank you all

[RRick]

You're right, deleting a node in link list is a pretty common question. Unfortunately, this question sounds suspiciously like a homework problem. At this forum, we don't answer homework problems directly, but can help in places where you are confused.

The problem: How to delete a node from a single linked list using only one pointer?

I'm not sure what this means. If you want to delete a node, there are 2 cases you need to consider. Is the node the first node or something in the middle/end.

As to the last question, binary searches need random access to all elements. Does a link list have this capability? What if you order the link list? Does this add random access to it?

[yfredmann]

Thanks RRick for your answer. It's not an exact homework question! The problem of deleting a node from a singly linked list using one pointer, to the best of my knowledge, is somewhat a challenging, or better to say, a tricky problem. Once the trick is revealed, it becomes a routine work.

To delete from the beginning is so easy, with a one pointer. As I pointed earlier, the process has to search for an item, then deletes the node that contains the item.

With 2 pointers, e.g. current and previous, it's straightforward . You keep track with the two pointers to go concurrently, until the item is found (note I'm not dealing with the other two special cases: first node, or the item is_not_found). The item is in the middle or the end.

For instance, this code snippet needs to be filled in the missing case discussed above.

struct node *delete(struct node *list, int key)
{
   struct node *curr;
   for (curr = list; curr != NULL && curr->data != key)
      ;

   if (curr == NULL)   /* key was not found - this includes the list is empty */
      return list;

   if (curr == list)  /* key is in the first node */
      list = list->next;
   else /* key isn't the first node */
      /* how to provide code such that the node just prior to current bypasses
         the current node -- the only way that comes to my mind is the following:
         struct list *first = list;
         then let *list go concurrently, just prior to *curr. But this way there's a
         use of two pointers.

         Question: Is there any way to solve it using only one pointer?

      */
   free(curr);
   return list;
}

I'm not yet sure if this problem has a solution; perhaps it does.

[weaknessforcats]

/* how to provide code such that the node just prior to current bypasses
the current node -- the only way that comes to my mind is the following:
struct list *first = list;
then let *list go concurrently, just prior to *curr. But this way there's a
use of two pointers.

Question: Is there any way to solve it using only one pointer?

As you walk the list keep the address of the current node in a pointer. Maybe call it PriorNode.

Then when you need to delete the current node, all you do is use PriorNode to set the next pointer of the prior node to the current node next pointer and you are done.

[JosAH]

As you walk the list keep the address of the current node in a pointer. Maybe call it PriorNode.

Then when you need to delete the current node, all you do is use PriorNode to set the next pointer of the prior node to the current node next pointer and you are done.

And what to do if you also have to delete/free that node? (only one pointer is allowed in this game ;-)

kind regards,

Jos

[weaknessforcats]

priornode->next = current->next;
delete current;

What do you mean by using only one pointer? There are three addresses involved and you have to save current->next before you delete current.

[JosAH]

priornode->next = current->next;
delete current;

What do you mean by using only one pointer? There are three addresses involved and you have to save current->next before you delete current.

Well, this is what the OP wrote and you are using two pointers:

The problem: How to delete a node from a single linked list using only one pointer?

kind regards,

Jos ;-)

[donbock]

Plea for clarification. Are you asking for help with a program that ...

(1) Deletes one node from a linked list where each node in the list has a single node pointer (which points to the next node in the list).

(2) Same as (1) plus you are also required to achieve this with only one pointer variable in the program.


By the way, what should your program do with the deleted node?

• Return it and let the caller figure out what to do with it.
• Add it to a linked list of free nodes.
• Free it / destroy it.
• Something else.

[hsheboul]

By the way, what should your program do with the deleted node?

• Return it and let the caller figure out what to do with it.
• Add it to a linked list of free nodes.
• Free it / destroy it.
• Something else.

As much as it concerned, donbock is right in the sense of whether you want to keep track of the node that you want to discard, i.e. the deleted node, where it fills 1, 2, and 4 above. The 3rd choice need not to keep track of the deleted node.

If you don't have to keep track of the deleted node, then the *trick* as you mentioned, is easy to deal with. It's solvable! On the other hand, as weaknessforcats wrote:

What do you mean by using only one pointer? There are three addresses involved and you have to save current->next before you delete current.

there is really, in the worst case scenario, THREE pointers involved: where the node that has the key matched is in the middle -- This case of the problem is not solvable at all. PERIOD.

[hsheboul]

I was mistaken. It is solvable whether you want to keep track of the deleted node or just want to discard it, i.e. delete it.

First, check to see whether the matched node is the first one, separate check
Then do traversal with the

curr->next->data == key

Once a match found, "bypass" with a code like this

struct node *temp = curr->next;
curr->next = curr->next->next;
return temp; /*or free(temp); or what ever you want to do with it. */

Hope this helps you out in your problem.

[yfredmann]

Thanks for all your replies -- that was of great help.
I figured now where's the trick to use of looking ahead of two pointers at a time,
currentptr -> nextptr -> nextptr

Yara