Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

Deleting a Node

Deleting a node is more complex than inserting a node because pointers and memory have to be shuffled. The problem with deletion is that, in most cases, you want to delete a specific node. The node might be at the head, tail, or middle, so you must write a very general algorithm that takes all these cases into consideration. If you’re careful, deletion isn’t a problem. If you don’t take all the cases into consideration and test them, though, you’ll be sorry!

In general, the algorithm must search the linked list for the key in question, remove the node from the list, and release its memory. In addition, the algorithm has to fix up the pointers that pointed to the node and that the node pointed to. Take a look at Figure 11.3 to see this.

Figure 11.3 Removing a node from a linked list.

In any event, here’s the code that implements the deletion based on removing the node with key ID:

    // again this function will modify the globals

    // head and tail (possibly)

    int Delete_Node(int id) // node to delete

    {

    // this function deletes a node from

    // the linked list given its id

    NODE_PTR curr_ptr = head, // used to search the list

             prev_ptr = head; // previous record

    // test if there is a linked list to delete from

    if (!head)

        return(-1);

    // traverse the list and find node to delete

    while(curr_ptr->id != id && curr_ptr)

         {

         // save this position

         prev_ptr = curr_ptr;

         curr_ptr = curr_ptr->next;

         } // end while

    // at this point we have found the node

    // or the end of the list

    if (curr_ptr == NULL)

        return(-1); // couldn’t find record

    // record was found, so delete it, but be careful,

    // need to test cases

    // case 1: one element

    if (head==tail)

       {

       // delete node

       free(head);

       // fix up pointers

       head=tail=NULL;

      // return id of deleted node

      return(id);

      } // end if

    else // case 2: front of list

    if (curr_ptr == head)

       {

       // move head to next node

       head=head->next;

       // delete the node

       free(curr_ptr);

       // return id of deleted node

       return(id);

       } // end if

    else // case 3: end of list

    if (curr_ptr == tail)

       {

       // fix up previous pointer to point to null

       prev_ptr->next = NULL;

       // delete the last node

       free(curr_ptr);

       // point tail to previous node

       tail = prev_ptr;

       // return id of deleted node

       return(id);

       } // end if

    else  // case 4: node is in middle of list

       {

       // connect the previous node to the next node

       prev_ptr->next = curr_ptr->next;

       // now delete the current node

       free(curr_ptr);

       // return id of deleted node

       return(id);

       } // end else

    } // end Delete_Node

Note that there are a lot of special cases in the code. Each case is simple, but you have to think of everything—which I hope I did!

Finally, you may have noticed the dramarama involved with deleting nodes from the interior of the list. This is due to the fact that once a node is traversed, you can’t get back to it. Hence, I had to keep track of a previous `NODE_PTR` to keep track of the last node. This problem, along with others, can be solved by using a doubly linked list, as shown in Figure 11.4.

Figure 11.4 A doubly linked list.

The cool things about doubly linked lists are that you can traverse them in both directions from any point and insertions and deletions are much easier. And the only change to the data structure is another link field, as shown here:

    typedef struct NODE_TYP

       {

       int id;        // id number of this object

       int age;       // age of person

       char name[32]; // name of person

       // more fields go here

       NODE_TYP *next;   // link to the next node

       NODE_TYP *prev; // link to previous node

       } NODE, *NODE_PTR;

With a doubly linked list, you always move forward or backward from any node, so the tracking code is simplified for insertions and deletions. For an example of implementing a simple linked list, take a look at the console application `DEMO11_1.CPP[vbar]EXE`. It allows you to add, delete, and traverse a linked list.

> Note: `DEMO11_1.CPP` is a console application, rather than the standard Windows `.EXE` application that you’ve been working with, so make sure to set the compiler for Console Application before trying to compile it. And obviously, there is no DirectX, so you don’t need any of the DirectX `.LIB` files.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.