Thread: One question on linked list need some ideas to solve it...

Sure, to delete a node in the middle, you need to find the node before it, and set the next pointer of that node to the next pointer of the "deletee".

--
Mats

Originally Posted by sreeramu

In this there is only one node address is given we dont know the prev node . . . Address . . . . How to em this ....

So, you have to search the list until you find the node you want, and whilst you are walking the list, you make note of the "previous" node you walked.

--
Mats

If it's a linked list, then it will have members that point to the next in the list (and possible to the previous, as well).
But it all depends on the implentation, and how the list looks like, since arguably, not all lists look alike.

Originally Posted by Elysia

If it's a linked list, then it will have members that point to the next in the list (and possible to the previous, as well).
So here's a sample of how it could be done:

Code:

MyLinkedList* p;
MyLinkedList* pNext = p->pNext;
MyLinkedList* pPrev = p->pPrevious;
pPrevious->pNext = pNext;
pNext->pPrevious = pPrev;
free(p);
p = NULL;

But it all depends on the implentation, and how the list looks like, since arguably, not all lists look alike.

Ehm, the original post says

i have one question on single linked list

. This I take to mean isn't a double linked list, so it only has a next-pointer. Which means that you need to, as I stated above, search the list for the node.

--
Mats

Alright, well I didn't know the exact difference between a single and double linked list. I find a double more efficient. Anyway, basic code would then be:

Code:

/* We assume p is pointing to the object you want to delete */
/*MyLinkedList* p;*/
MyLinkedList* pNext = p->pNext;
MyLinkedList* pPrev = NULL;
/* If we assume pFirst is a pointer to the first object in the list */
MyLinkedList* pTemp = pFirst;
/* Walk the tree until we find the previous node */
for (; pTemp->pNext != p; pTemp = pTemp->pNext);
pPrev = pTemp;
/* Set the next node to the node after the node we want to delete */
pPrev->pNext = pNext;
free(p);
p = NULL;

Originally Posted by pankaj401

I think he means that only a lone [address of a] node is given. Provided it's a singly linked list and the head is not known deleting that node while keeping rest of the list intact wouldn't be possible.

Not in the way you're used to perhaps, but with a few modifications to your iteration routines you can perform lazy-deletion. Simply take the address given and remember it somewhere. Then modify your iteration code to check for and automatically remove and items that have been remembered as needing to be deleted.

This can be done intrusively by setting a kill-bit inside the node itself. Some self-balancing binary tree types use this kind of lazy-deletion approach.

Presumably, the function that removes a node is also passed the list from which to remove it to. With that you just iterate through the list, until the next value's next value points to the passed node.

Originally Posted by sreeramu

Hai friends my question is on single linked list . . . So you consider the the pointer of the 3rd node of the linked list is given and we can travel to next only we cant travel to back so we came find the 2nd node pointer . . . So i think that it is not possible to do this problem....

Code:

+-----+     +-----+     +-----+     +-----+
|  1  |---->|  2  |---->|  3  |---->|  4  |---->NULL
|_____|     |_____|     |_____|     |_____|

So this is your linked list. If you wanted to delete the third node, you need to find and set a pointer to the node previous to that item. All you have to do is use a loop, and keep walking the list until you find the next pointer to the node you want to delete. So it might look like this when you're finished:

Code:

         node * prev    node * todelete
               v____|       v___|   
+-----+     +-----+     +-----+     +-----+
|  1  |---->|  2  |---->|  3  |---->|  4  |---->NULL
|_____|     |_____|_    |_____|    >|_____|
                    \_____________/  
                  
              prev->next = todelete->next

If you can read my crazy ascii art that should make sense. Like I said before, unlinking a list node means that you set the next pointer of a previous node to point to the node _after_ the old node.

Just do something like

prev->next = todelete->next;

Then the node is successfully unlinked, and you can call free( todelete ); or something, if you like. Like I said, very simple. Make sure that you write secure code though! Don't dereference a NULL pointer.