Printable View
Note that this example also implies that it's a double-linked list OR you know the first pointer in the list so you can walk to the previous node. If you can't, then you can't free a node because however you did, the previous node would point to a deleted (or freed) node.
If you can't delete a node because you can't find previous nodes, (either because you don't even know where the first node is or the list isn't doubly linked) your implementation is broken indeed. A working implementation can do at the very least insertion and deletion.
Did you not read my post? or anyone else's for that matter...Quote:
Originally Posted by sreeramu
For completeness I shall spell out ALL of your options:
1. Pass a pointer to the head as well, and iterate through the list to find the prev node to update.
2. Use a doubly-linked list instead.
3. Use lazy-deletion with a seperate structure containing nodes to be deleted upon next iteration through the list.
4. Use lazy deletion as above but with an intrusive deletion flag a.k.a kill-bit.
5. Allocate all nodes from a pool allocator and search the entire memory pool to find the prev node to update.
I recommend 1 or 2.
@iMalc
i am asking that we should do this operation on a single linked list . . . We cant use the double linked list....But for me it is conform we cant do this operation in single linked list...
I think that some of them are not able to understand my question
consider this is the function
and now in main we would be calling that function like thisCode:struct node *delete(struct node *p)
{
}
in this you consider that 'p' is the pointer of 3rd node of the single linked list and now we want to delete 'p' and one more point we know only 'p' we dont know other things like head of the linked list or prev node address and number of nodes in the list....Code:main()
{
.........
delete(p);
.........
}
Quote:
Originally Posted by sreeramu
In that particular call scenario, you CAN NOT find the previous node [unless you allocate your memory from a special heap or some such], so you have only the choice of "mark this as deleted and remove it later on".
The other alternative is to pass in the ACTUAL head of the list to delete.
[I also don't see ANY purpose to returning a struct node * from delete].
--
Mats
Discussing with colleagues over some beer I actually ended up finding that we can delete the isolated node except if it is the last node in the list.
All you need to do is copy the current->next and current->next->data to this node and delete the next node.
Doesn't work if it's the last node. We can check the current->next->next = NULL to check this.
I suppose that works, but it's mind boggling and difficult to understand and as you mention, doesn't work with the last node, so if someone passes the last node, then you can't delete it.
It's better if someone passes in the head or making it a double linked list.
Seems like one of those things which does not make sense in real world but good for interview stuff ;)
I don't care if you are not willing to change to a doubly-linked list, or pass in the head pointer. I'm simply stating these as a possible way of solving this.Quote:
Originally Posted by sreeramu
Yet another method is to iterate using a pointer to a pointer. Instead of always having a pointer pointing to the node to look at it, you have a pointer-pointer pointing to the 'next' pointer of the previous item. The data is then always accessed via (**iter).data or (*iter)->data instead of just iter->data. Then, you can modify *iter to change what the previous item's 'next' pointer value is, or the head pointer.
Yes I realise that this is another method you are probably not willing to accept because you have to ever-so-slightly change your function prototype, or data structure. That doesn't mean others can't use the idea.
the method pankaj401 mentioned can be fixed by using an 'end' pointer member in the list 'class'. It would actually point one-past the tail, meaning it would normally be NULL, except for when the last node in the list gets deleted. It would then point to this node. In fact if you delete the last item again, then it can be pushed onto the head of the 'end' list. Iteration over the entire list would loop until curr == end, instead of until curr == NULL. Nodes stored in the 'end' list can be deleted whenever.
So basically you're still saying that you still want confirmation that it is impossible, when we have shown ways of it actually being possible? Well sorry, no it is not impossible. It certainly is possible if you allocate all nodes from a memory pool. It is however not very practical to do this, but it is not impossible.
Note that I also recommend staying away from using 'delete' as the function name, as it would make it harder to port to C++.
I actually kind of like that. (I guess that says something about me.) And of course, at the cost of an additional sizeof(node) bytes, we can put it in a sentinel node that must always live at the end of the list. We still won't be able to delete it, but now it's an error to try.Quote:
Originally Posted by pankaj401
Or, of course, we can make the list circular; then all we have to do is go all the way around the list to find the previous node! So what if deletion now takes an hour to do? :)
Come on!
If you add another node, why not make it double-linked? That makes it much easier to delete nodes in the list.
can you give some examples ....ho to do that......Quote:
Originally Posted by Elysia
A double linked list will contain a pointer to walk forward and one to walk backward.Code:struct MyLinkedList
{
MyLinkedList* pNext;
MyLinkedList* pPrev;
MyLinkedList* pBegin; /* Optional - but it yields big performance gains if you need to skip or access the last element in the list */
MyLinkedList* pEnd; /* Same as above, but for the first.
}
You can also use a pointer to point to the beginning of the list and one to the last. They're optional, but they'll save time if you need to walk to the end/beginning respectively.
I recommend a pointer to the last since if you need to inset an element, you need to walk to the end of the list and insert it. If you need to add a node at the beginning of the list, then pBegin is a good choice.
To save memory, you can create an additional struct that contains two members, pBegin that points to the beginning and pEnd that points to the end of the struct, respectively. Then you can add allocate one instance of this object and keep a pointer to it in every node. That saves 4 bytes for every node.
Good luck.
You can do that, but it would be a terrible solution. You're far better off passing in a pointer to the one object that holds the begin and end pointers to the 'remove' function, than storing that in every node. Just think of how expensive it would become to remove the first or last element. That's potentially a lot of nodes to update!Quote:
Originally Posted by Elysia
The above does lend itself to yet another potential solution though, storing a pointer to the head node inside each node, which allows you to find the prev item. Of course this also is a waste of time as you could simply store the prev pointer in each node instead.
So in other words, separate pointers for start and last or a pointer within each node to another struct that contains a pointer to start and end would be the most efficient.
The second being a little more expensive in terms of memory.