C++ Node Deletion Between List Logic

Question

EDIT: Problem: Deleting a node between 2 nodes, and then linking the outer nodes with each other.

After learning and building several quadtrees and octrees, and really liking subdivision, I decided to use subdivision in my server. But, only placing nodes within themselves. My problem is, I cant figure out how to link the previous node, to the next one if the node is in the middle. I am wondering if I am doing this correctly. Below is my code and I comment where the problem area is. Any help would be great!

bool deleteNode ( SOCKET s , client_information_class *prev ) {
          bool return_value = false;
          if ( node[0]->client_socket != s ) {
               if ( node[0]->node != NULL ) {
                    return_value = node[0]->deleteNode ( s , *node );
               } else {
                    cout << endl << "Can not call deleteNode anymore ... Did not find the node to delete ... " << endl;
                    return return_value;
               }
          } else {
               if ( node[0]->client_state == 1 )
                    InterlockedDecrement(&connection_count);
               if ( node[0]->node != NULL ) {          // there is a next node
                    client_information_class **next = node[0]->node;
                    if ( next[0]->node != NULL ) {
                         // problem area
                         cout << endl << "next[0]->node is not null" << endl;
                         prev->node = next[0]->node[0]->node; // ??? I know its wrong
                    } else {
                         // problem area
                         cout << endl << "next[0]->node is null" << endl;
                         prev->node = next[0]->node;  // ??? I know its wrong
                    }
                    delete node;
               } else {                                   // its the last one
                    prev->node = NULL;
                    delete node;
               }
               InterlockedDecrement(&socket_count);
               return_value = true;
          }
          return return_value;
}

SingerOfTheFall · Accepted Answer

So if I got your problem right, you have a trouble inserting an item inside a linked list. I really really hope this is the issue, otherwise all the typing I've done was totally in vain.

I didn't really get all of your code (since it's a little out of context), but I'll show you the logic on an example. I will use nodes that have the following structure:

class Node
{
public:
    Node * next_;
    Node * prev_;
    int i;//we need this to tell nodes apart. 
    //And whatever data you want.
}

So we will make a linked list in which each item has pointers to the previous and the next items. The logic for more complicated structures (like if you have, for example, left + right + child + parent pointers) is the same, the only difference is that you will have to set all of them. It doesn't really change much.

So, to construct the list, we will need a couple of constructors that will handle different operations:

the default constructor to make an empty node:

Node()//default constructor
{
    prev_ = nullptr;
    next_ = nullptr;
    i = 0;
}

a constructor that takes a pointer to the last item in the list, and appends itself to the end of the list:

Node( Node * prev )//constructor for appending to the end of the list
{
    prev_ = prev;
    next_ = nullptr;//we append to the end, so there is no "next" element
prev->next_ = this;
    i = 0;
}

And finally a constructor to insert in the middle (which, I believe, is what you want):

Node( Node * prev, Node * next)//Inserting between prev and next nodes
{
    prev->next_ = this;
    next->prev_ = this;
    this->prev_ = prev;
    this->next_ = next;
    i = 0;
}

Now we have the full set of instruments to do whatever we want. The one last thing is deleting a node:

void deleteNode( Node * deleteMe )
{
    deleteMe->prev_->next_ = deleteMe->next;
    deleteMe->next_->prev_ = deleteMe->prev;
    delete deleteMe;
}

or, a more readable syntax:

void deleteNode( Node * deleteMe )
{
    Node * prevNode = deleteMe->prev_;
    Node * nextNode = deleteMe->next_;
    prevNode->next_ = deleteMe->next;
    nextNode->prev_ = deleteMe->prev;
    delete deleteMe;
}

let's make a sample list of, say, 10 elements:

int main()
{
    Node * root =  new Node();//the root of the list. it never changes.
    Node * last = root;//The pointer to the last element
    for(int i = 0; i < 10; i++)
    {
        Node * tmp = new Node( last );
        last = tmp;
    }
}

Here, all the elements in the list are properly linked, and have their i field containing 0 value. Let's insert another element somewhere in the middle, for example, between the third and the fourth elements:

Node * thirdNode = root->next_->next_;//I know this sucks, but it's just an example.
Node * insertMe = new Node(thirdNode, thirdNode->next_);//inserting between the third and the fourth.
insertMe->i = 9;//this will indicate the one we inserted, since all the others will have this as 0.

Now we can easily check if the insertion went correctly. Let's type all the element's data:

for( Node * it = root; it!= last; it = it->next_)
{
    std::cout << it->i << " ";
}

The result will be 0 0 0 9 0 0 0 0 0 0 0.

Finally, let's delete the just-inserted node:

deleteNode( insertMe );

If you will not output the values in the same vay, you will see only zeroes, which means the node was successfully deleted.

If you have more pointers in your nodes, all you have to do is to handle them properly in the same way. Another hint for you is to avoid constructions like this->next->next->prev. It is hard to tell that you are referring to the "prev" pointer of the element that is third from the current one. Instead, use something like:

Node * target = this->next->next;//easy to read

or maybe

Node * target = this;
for(int i = 0; i < 5; i++)
    target = target->next;

and then work with the pointer you got.

C++ Node Deletion Between List Logic

Answers (2)

Related Questions