CODEWITHSUNDEEP
c++c
Flash
Flash

Reputation: 3021

Deleting in a linked list

Given only a pointer to the node to be deleted , how do we delete the node in the linked list...?

Upvotes: 0

Views: 2274

Answers (6)

Pawel Zubrycki
Pawel Zubrycki

Reputation: 2713

I think it's almost impossible in singly-linked lists if you don't have any pointer to list head. You should always have a linked list head pointer.

Upvotes: 2

Zac Howland
Zac Howland

Reputation: 15870

The question is too ambiguous, and is likely that way for a reason (e.g. to spawn a conversation instead of test your actual knowledge of the data structure). They are likely expecting you to ask "Is this a doubly linked list or a singly linked list?" If it is a doubly linked list, its a simple matter:

curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete curr;

If it is a singly linked list, you must have the head node so you can find the previous node in the list. So they are likely expecting you to ask if you have a pointer to the head node. The pseudo-code would then be:

loop from head to end until test->next == curr
test->next = curr->next;
delete curr;

Alternatively, if you can modify the list (without the head node):

temp = curr->next;
curr->data = temp->data;
curr->next = temp->next;
delete temp;

Upvotes: 6

CashCow
CashCow

Reputation: 31455

I have a solution if this is not the tail.

If it is a singly-linked list you just "swap" with the node next to yours and delete that one instead.

Assuming I have 

struct Node
{
  T value;
   Node * next;
};

Solution would be something like:

void freeNode( Node * node )
{
   Node * next = node->next;
   if( next )
   {
      node->value = next->value;
      node->next = next->next;
      free( next ); 
   }
   // else I'm stuck!
}

The above sort of pseudo mix of C and C++.

If the node we have is the tail, and assuming that the tail is indicated by node->next == NULL, I cannot make the previous node into the tail so I cannot solve.

Upvotes: 1

Neilvert Noval
Neilvert Noval

Reputation: 1695

You have a pointer to that node (say, node N). Meaning, you have access on that node.
If that node has pointer to it's front node and it's back node, then simply point the back node to the front node. And the front node to the back of your node N.

To illustrate: 
step 1:
---> [ node ] ---> [ node ] ---> [ node ] ---> 
<--- [  M   ] <--- [  N   ] <--- [  O   ] <--- etc...

step 2:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <--- [node N] <--- [  O   ] <--- etc...

step 3:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <----------------- [  O   ] <--- etc...

                                    [ node ] ---> (still points to node O)
      (still points to node M) <--- [  N   ]

step 4:
just point Node N to NULL
                                    [ node ] ---> NULL
                          NULL <--- [  N   ]

result:
---> [ node ] -----------------> [ node ] ---> 
<--- [  M   ] <----------------- [  O   ] <--- etc...

Upvotes: 1

mukeshkumar
mukeshkumar

Reputation: 2778

Well, its just a trick.

Assuming curr is the address given, following would be the pseudo code:

to_delete = curr->next
curr->data = to_delete->data
curr->next = to_delete->next
delete to_delete

Essentially this just copies data and next pointer of next node in the list to the current node and deletes the next node.

Upvotes: 3

Gintautas Miliauskas
Gintautas Miliauskas

Reputation: 7892

In a standard linked list implementation, you have to modify the node that points to the node being deleted. To modify it, you have to find it first. If you have a pointer to the list head, or any element prior to the one being deleted, you can find it by traversing the list. If not, there's no general solution to this problem.

You could get out of the situation by modifying the definition of a linked list to mark deleted nodes somehow (say, with a boolean attribute deleted), and in turn modify list traversal to skip such nodes.

Upvotes: 1

Related Questions