Let x be a node in SLL. Write a C++ function to delete the data in this node. Following this deletion, the number of nodes in the list is one less than before the deletion. Your function must run for O(1).
Bharath_4 0 Newbie Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Done. Show me your solution and I'll show you mine.
Bharath_4 0 Newbie Poster
Actually its a project for me that i would like to know the answer. would be pleased if u show me the solution. pls
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
But you won't learn anything by being given the answer. The trick is to think outside the box a little bit. Naively deleting a node from a single linked list is O(n) because you have to find the previous node for unlinking. So what can you do to avoid needing the previous node?
Bharath_4 0 Newbie Poster
Make the next node at first?? Not sure though
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Make the next node at first??
I'm having trouble deciphering what you mean, but it sounds like you're thinking in the right direction.
Here's a hint: the problem doesn't state that you only have to do this by diddling with the links between nodes.
Bharath_4 0 Newbie Poster
uhh!! ok Thank You :-/
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Did you figure it out? As mentioned before, I really am trying to help, but without flat out giving you the answer.
Bharath_4 0 Newbie Poster
No. I didnt find it
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Consider this: Swap the data with the next node, then delete the next node. This is what I mean by thinking outside the box.
Thinking through these types of problems on a simple data structure like a linked list is invaluable for when you move on to more complex data structures. In particular, this swap and delete technique is very handy with trees. But the reason I'm directing you rather than simply gaving away answers is because if you only know the specific technique for that data structure, variations of it for other data structures don't stand out as readily.
Bharath_4 0 Newbie Poster
yeah Thanks. I could try it now .
happygeek 2,411 Most Valuable Poster Team Colleague Featured Poster
You are getting help, yet still you sent (10mins ago) a PM begging me to help you as you have to submit a project tomorrow and don't have time to do it yourself...
Please don't do that again.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.