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

Question

Is it possible to delete a middle node in the single linked list when the only information available we have is the pointer to the node to be deleted and not the pointer to the previous node?After deletion the previous node should point to the node next to deleted node.

Answer 1

yes, but you can't delink it. If you don't care about corrupting memory, go ahead ;-)

Answer 2

Not if you want to maintain the traversability of the list. You need to update the previous node to link to the next one.

How'd you end up in this situation, anyway? What are you trying to do that makes you ask this question?

Answer 3

i wonder if this is real problem or an esoteric programming challenge. could you do it recursively?

Answer 4

Yes, but your list will be broken after you remove it.

In this specific case, traverse the list again and get that pointer! In general, if you are asking this question, there probably exists a bug in what you are doing.

Answer 5

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.

Answer 6

You'll have to march down the list to find the previous node. That will make deleting in general O(n**2). If you are the only code doing deletes, you may do better in practice by caching the previous node, and starting your search there, but whether this helps depends on the pattern of deletes.

Answer 7

In order to get to the previous list item, you would need to traverse the list from the beginning until you find an entry with a next pointer that points to your current item. Then you'd have a pointer to each of the items that you'd have to modify to remove the current item from the list - simply set previous->next to current->next then delete current.

edit: Kimbo beat me to it by less than a minute!

Answer 8

Maybe do a soft delete? (i.e., set a "deleted" flag on the node) You can clean up the list later if you need to.

Answer 9

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.

Answer 10

You could do delayed delinking where you set nodes to be delinked out of the list with a flag and then delete them on the next proper traversal. Nodes set to be delinked would need to be properly handled by the code that crawls the list.

I suppose you could also just traverse the list again from the beginning until you find the thing that points to your item in the list. Hardly optimal, but at least a much better idea than delayed delinking.

In general, you should know the pointer to the item you just came from and you should be passing that around.

(Edit: Ick, with the time it took me to type out a fullish answer three gazillion people covered almost all the points I was going to mention. :()

Answer 11

The only sensible way to do this is to traverse the list with a couple of pointers until the leading one finds the node to be deleted, then update the next field using the trailing pointer.

If you want to delete random items from a list efficiently, it needs to be doubly linked. If you want take items from the head of the list and add them at the tail, however, you don't need to doubly link the whole list. Singly link the list but make the next field of the last item on the list point to the first item on the list. Then make the list "head" point to the tail item (not the head). It is then easy to add to the tail of the list or remove from the head.

Answer 12

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.

Answer 13

You have the head of the list, right? You just traverse it.

Let's say that your list is pointed to by "head" and the node to delete it "del".

C style pseudo-code (dots would be -> in C):

prev = head
next = prev.link

while(next != null)
{
  if(next == del)
  {
    prev.link = next.link;
    free(del);
    del = null;
    return 0;
  }
  prev = next;
  next = next.link;
}

return 1;

Answer 14

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. 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.

Answer 15

Given

A -> B -> C -> D

and a pointer to, say, item B, you would delete it by
1. free any memory belonging to members of B
2. copy the contents of C into B (this includes its "next" pointer)
3. delete the entire item C

Of course, you'll have to be careful about edge cases, such as working on lists of one item.

Now where there was B, you have C and the storage that used to be C is freed.

Answer 16

The following code will create a LL, n then ask the user to give the pointer to the node to be deleted. it will the print the list after deletion It does the same thing as is done by copying the node after the node to be deleted, over the node to be deleted and then delete the next node of the node to be deleted. i.e

a-b-c-d

copy c to b and free c so that result is

a-c-d

struct node  
{
    int data;
    struct node *link;
 };

void populate(struct node **,int);

void delete(struct node **);

void printlist(struct node **);

void populate(struct node **n,int num)
{

    struct node *temp,*t;
    if(*n==NULL)
    {
        t=*n;
        t=malloc(sizeof(struct node));
        t->data=num;
        t->link=NULL;
        *n=t;
    }
    else
    {
        t=*n;
        temp=malloc(sizeof(struct node));
        while(t->link!=NULL)
            t=t->link;
        temp->data=num;
        temp->link=NULL;
        t->link=temp;
    }
}

void printlist(struct node **n)
{
    struct node *t;
    t=*n;
    if(t==NULL)
        printf("\nEmpty list");

    while(t!=NULL)
    {
        printf("\n%d",t->data);
        printf("\t%u address=",t);
        t=t->link;
    }
}


void delete(struct node **n)
{
    struct node *temp,*t;
    temp=*n;
    temp->data=temp->link->data;
    t=temp->link;
    temp->link=temp->link->link;
    free(t);
}    

int main()
{
    struct node *ty,*todelete;
    ty=NULL;
    populate(&ty,1);
    populate(&ty,2);
    populate(&ty,13);
    populate(&ty,14);
    populate(&ty,12);
    populate(&ty,19);

    printf("\nlist b4 delete\n");
    printlist(&ty);

    printf("\nEnter node pointer to delete the node====");
    scanf("%u",&todelete);
    delete(&todelete);

    printf("\nlist after delete\n");
    printlist(&ty);

    return 0;
}

Answer 17

can any one has the correct code for this....

~thanks Vijay.

Answer 18

void delself(list *list)

{

/if we got a pointer to itself how to remove it.../ int n;

printf("Enter the num:");

scanf("%d",&n);

while(list->next!=NULL)

{

if(list->number==n) /now pointer in node itself/

{

list->number=list->next->number; /copy all(name,rollnum,mark..) data of next to current, disconect its next/

list->next=list->next->next;

} list=list->next;

} }

Answer 19

void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");
   scanf("%d",&n);

   while(list->next!=NULL)
   {
      if(list->number==n) /*now pointer in node itself*/
      {
         list->number=list->next->number;   /*copy all(name,rollnum,mark..)
                             data of next to current, disconnect its next*/
         list->next=list->next->next;
      }
      list=list->next;
   }
}

Answer 20

If you have a linked list A -> B -> C -> D and a pointer to node B. If you have to delete this node you can copy the contents of node C into B, node D into C and delete D. But we cannot delete the node as such in case of a singly linked list since if we do so, node A will also be lost. Though we can backtrack to A in case of doubly linked list.

Am I right?