Thread: (Linked List) Is this right?

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    6

    (Linked List) Is this right?

    Does this seem right? I mean I could show you all the code but this function is kind of self contained. It works so long as all the visuals(a custom type) sent thru it have the same location_z value, but it hangs forever out if they have differant values.

    What it does is place the visual into a list, and the list is supposed to be like this when its done:

    Static Pointer root->visual(lowest Z value)->...->visual(highest Z value)->Null

    and then another function(confirmed working) clears out the list each time.

    Everything works pretty much perfectly until you pass it something with a differant Z value, which to me points the finger at this function.

    It ends up hanging forever if any Z value is used that is not equal to all other Z values passed.

    Code:
    void visual::place(visual * new_visual)
    {
        // If root is null root points to this visual and it points to null
        if(root == 0)
        {
            root = new_visual;
            new_visual->next_visual=0;
        }
        // Otherwise it will have to be placed in order
        else
        {
            // If root has a higher or same Z
            // Then make visual new root and link it to old root
            if(new_visual->location_z <= root->location_z)
            {
                visual * old_root = root;
                root = new_visual;
                new_visual->next_visual = old_root;                                            
            }
            // Otherwise move down the list and attempt to find
            // a spot where first is <= and second is >= Z
            else
            {
                // Set index to root
                visual * index = root;
                // Control bool
                bool finished = false;
                // Loop until resolved
                while(finished == false)
                {
                    // If the next visual is zero we've hit the end and
                    // the new_visual is the highest Z
                    if(index->next_visual == 0)
                    {    
                        // Set the next visual of the index to the new
                        // visual and then set the next visual
                        // of the new visual to null
                        index->next_visual = new_visual;
                        new_visual->next_visual=0;
                        // Declare finished
                        finished=true;
                    }
                    // Otherwise see if the current index is lower or equal
                    // while the next index is greater or equal
                    if((index->location_z<=new_visual->location_z) && (index->next_visual->location_z>=new_visual->location_z))
                    {
                        // If so, then the new visual next visual becomes the index
                        // next visual
                        // The index next visual then becomes the new visual
                        // This causes an insertion
                        new_visual->next_visual=index->next_visual;
                        index->next_visual = new_visual;
                        // Declare finished
                        finished=true;
                    }
                    // If not finished, move on to next index and try again
                    if(finished==false){index=index->next_visual;}
                }
            }       
        }
    }

  2. #2
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Code:
                     if(index->next_visual == 0)
                    {    
                        // Set the next visual of the index to the new
                        // visual and then set the next visual
                        // of the new visual to null
                        index->next_visual = new_visual;
                        new_visual->next_visual=0;
                        // Declare finished
                        finished=true;
                    }
                    // Otherwise see if the current index is lower or equal
                    // while the next index is greater or equal
                    else if((index->location_z<=new_visual->location_z) && (index->next_visual->location_z>=new_visual->location_z))
                    {
                        // If so, then the new visual next visual becomes the index
                        // next visual
                        // The index next visual then becomes the new visual
                        // This causes an insertion
                        new_visual->next_visual=index->next_visual;
                        index->next_visual = new_visual;
                        // Declare finished
                        finished=true;
                    }
    Think you need that else otherwise the new node will be inserted twice at the end of the list. ( not shure about this ).
    BTW you don't need the check
    Code:
    if((index->location_z<=new_visual->location_z) && (index->next_visual->location_z>=new_visual->location_z))
    Code:
    if ( index->next_visual->location_z > new_visual->location_z)
    should be enough
    Kurt

  3. #3
    Registered User
    Join Date
    Jan 2006
    Posts
    6
    Thanks, I got that working a few seconds before I checked this ironically enough.

    Else-if is more elegant than what I did(which was check the keeper variable).

    I may not need the first check, but I need >= not just > in case of ties(and since it is drawing order in a tile-based setup there will be more ties than non-ties).

    I'm abusing the concept of Z. What I actually mean is a primitive 2D drawing order from lowest to highest

  4. #4
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Actually I wanted to add something like
    if you dont have to preserve order. But didn't because I couldn't find the right words ( my english is rather poor ).
    Kurt

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Actually, the original post is far more complicated than it needs to be. The below is removes much of the redundancy, but there is much more that can be done to simplify it furthur.
    Code:
    void visual::place(visual * new_visual)
    {
        // If root is null root points to this visual and it points to null
        if(root == NULL)
        {
            root = new_visual;
            new_visual->next_visual = NULL;
        }
        // Otherwise it will have to be placed in order
        else
        {
            // Set index to root
            visual * index = root;
            // If root has a higher or same Z
            if(new_visual->location_z <= root->location_z)
            {
                root = new_visual;
                new_visual->next_visual = index;                                            
            }
            // Otherwise move down the list and attempt to find
            // a spot where second is >= Z
            else
            {
                while (index->next_visual != NULL && index->next_visual->location_z >= new_visual->location_z)
                {
                    index = index->next_visual;
                }
    
                // Then the new visual next visual becomes the index
                // next visual
                // The index next visual then becomes the new visual
                // This causes an insertion
                new_visual->next_visual = index->next_visual;
            }
            // Attach the new item to it's predecesor
            index->next_visual = new_visual;
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM