You are here:

C++/deleting nodes

Advertisement


Question
 Hi Bill,

I have a question about deleting nodes of a linked list.
I'm basically doing it like this:

MyClass *temp;
MyClass *start=start_of_my_list;

while(!end_reached)//some loop control function here
{
temp=start;
start=start->forward();//this a function I know works
delete temp;
}

I'm trying to delete intermediate nodes without reconnecting the two halves of the resulting list (because one of these halves will be deleted later; my application requires it).

I don't get this to work properly. After a lot of experimenting I discovered that the nodes that are deleted need to be disconnected from all other nodes by making sure that they don't point to any other nodes and they are not pointed to by any other nodes. This means all these nodes have to point to NULL. However, this doesn't make much sense to me. Why would a node need to be disconnected before deleting it? Is it because that the program gets confused if some nodes (even though they are never visited by the program) point to something that no longer exists.

No matter what I disconnect, I still have a hard time getting this deletion to work. Above I gave you a simplified version of my code. My data structure is actually of a grid type. If I visualize my data structure, it would be a table. All nodes in the top row have two pointers: forward and left. All the rows below the bottom row only have forward pointers (the left pointer is set to NULL). I drew you this diagram of my data structure:

D <- C <- B <- A <- start
|    |    |    |
ˇ    ˇ    ˇ    ˇ
H    G    F    E
|    |    |    |
ˇ    ˇ    ˇ    ˇ
L    K    J    I

Maybe I'm having problems because the grid is complicated. My goal is simply to delete the grid above. I've been trying to delete this grid one colulmn at a time. Using the above example, I delete in this order: A, E, I, B, F, J ... and I just cannot get it to work without crashing. There is something tricky about handling the pointers that I cannot figure out.
Do you have any quick ideas as to what I could try?
Most thankfully,
         Andres

Answer
It sounds like what's happening is you have cross- or multiple-links.  When you delete one, the other pointer is still pointing to a deleted node.  If above you want to delete C, C has to outgoing pointers, both of which have to be fixed before deleting C.

Pictures like above help a lot.  Write a function to print the tree as best you can.  You may find who's got bad pointers.

Sorry this is very helpful, and late too - I've been very busy.

Bill

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Bill A

Expertise

I can answer questions about C++, programming algorithms, Windows programming in MFC (which is C++). I cannot answer questions about STL (templates) and I have no experience with Linux. I do enjoy reviewing code and critiquing it or finding problems in it. I will also gladly show better algorithms or methods if you want to take advantage of that.

Experience

I've developed a commercial embedded C compiler/assembler and IDE with debugger toolset, of which the IDE and debugger are written in C++. I work in the industry writing high tech embedded programs and Windows programs to communicate with the embedded devices.

Publications
Book: Embedded Systems Design using the Rabbit 3000 Microprocessor Authored Chapter 10 in its entirety.

Education/Credentials
BS Computer Engineering

©2016 About.com. All rights reserved.