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

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.

Originally Posted by sreeramu

Any one give the solution or tell that it is possible are not...

Did you not read my post? or anyone else's for that matter...
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

Code:

struct node *delete(struct node *p)
{
}

and now in main we would be calling that function like this

Code:

main()
{
.........
delete(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....

Originally Posted by sreeramu

@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

Code:

struct node *delete(struct node *p)
{
}

and now in main we would be calling that function like this

Code:

main()
{
.........
delete(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....

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

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.

Originally Posted by sreeramu

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

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

Come on!
If you add another node, why not make it double-linked? That makes it much easier to delete nodes in the list.

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

A double linked list will contain a pointer to walk forward and one to walk backward.
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.

Originally Posted by Elysia

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

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.