I've been writing lots of linked list and node classes for school lately. When I write doubly-linked nodes, I typically use the destructor to stitch the gap that's made when I delete a node: doing so links the previous and next nodes together before this node...vanishes. With a singly-linked list, the destructor can't do that exactly, because we know where this node points, but not what points to it. I don't really like this, so I came up with an idea.
LinkedList: n0 -> n1 -> n2 -> n3
When I call delete n1, I want the following to happen:
n1 is not the end of its list (it points to something): The values from n2 are copied into n1, including the pointer to the next node. n1 now points to n3.n2's pointer to the next thing is set to nullptr.delete n2. Since n2 is now the end of its list (it points nowhere), deallocate its memory.The pointer n1 is unchanged; the memory it points to is still allocated, but modified. The memory pointed to by n2 is deallocated. Anything that pointed to n1 now effectively points to n2, since all the data was moved from n2 into n1.
If I were using names for each node (actually manipulating nodes n0,n1, and so on in non-class code), I know this would be a bad idea, because it would look like this:
// n0 -> n1 -> n2 -> n3
delete n1;
// n0 -> n1 -> n3 // ?? we asked to delete n1, not n2
But I don't. All access to individual nodes starts with the list. So we'd see this:
// [0] -> [1] -> [2] -> [3]
delete (*list)[1]; // assume SLL::operator[] returns a pointer to a node
// [0] -> [1] -> [2] // good, list is one shorter
delete? Other black magic?My train of thought in answering the first question has so far alternated between doing this in the destructor and overloading the delete operator in the Node class. I stalled when I realized that I don't know when/where the member variables are actually deallocated (or even what exactly that looks like/means). Members of the Node class are created via something like int i;, not with new. I'm confused because I want to conditionally prevent the delete operation from actually deallocating what it's given, and I don't know whether that's possible, etc.
As for the second question, I have a sneaking suspicion that this is an atrocity and that code for it should never see the light of day. If it were okay, we'd have learned about it, right? I don't know about that. We learn an awful lot of ugly, inefficient, or otherwise annoying algorithms in intro classes. Beats me, so I figured I'd ask and maybe get some sage advice on style and such.
The list and nodes are created using new. Nodes are typically created like so:
sll->setHead(new Node(data0))
->append(new Node(data1))
->append(new Node(data2));
// SLL::setHead and Node::append each return a pointer to an appropriate node
This specific discussion is not part of the class/assignment. The task at hand could easily be completed with standard methods (traversing list and deleting the old-fashioned way). I'm just curious.
Hello me from six years ago, it's me from now. You've forgotten everything about C++, dropped out of college twice, and started working at FAANG.
Upon reviewing this question and the suggested answers elsewhere, it appears that the other sources provide merely the algorithmic solution, which is presented here as a given: the idea of overwriting the doomed node with its successor and then deleting that successor instead.
The question posed here, then, is one of mechanics: How does the C++ delete operator work, and can it be interrupted---say, to delete something else instead and leave the original target alone? I cannot answer this confidently, but I have found some leads.
delete keyword is translated to method callsMoreover, this is C++. As you'll realize in about a year, several of your instructors are writing it as if it were C. We don't do new and delete here if we can help it.
Regarding your second question: Yes, this is bad practice, for a simple reason: it lacks predictability. It boils down to what Jive Dadson wrote above:
You should be using std::list or std::forward_list, so you can concentrate on learning how to write actual programs in C++.
Don't repeat yourself. Don't reimplement things that already exist in the language unless you have some compelling reason to do so (here, it was a school assignment, but you wanted to know about the bigger picture). If you need to do that, or write some other type of container or structure that doesn't exist: Use the same language and conventions as the standard libraries, so that newcomers can pick up your code in a snap. Yes, it's a bit dull, but obscure syntactic choices aren't clever, just cryptic.