Jump to content
  • Advertisement
Sign in to follow this  
hisDudeness

Insert() function for link list

This topic is 4865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

here is my best shot at a function that inserts a linked list into another link list at any point. it doesn't work at all and i have been racking my brains the last 24 hours trying to figure out why. all you need to know is that i have two global node pointers: node* HEAD = NULL; node* TAIL = NULL; it is a doubly linked list.
// Function : Insert
// Takes two node pointers, newNode and target, and inserts newNode into
// the list (starting at global pointer HEAD) after the target node. Keep 
// in mind, newNode could be the first node of a second list, which is why the 
// function traverse newNode at several places to search for its last node.

// The goal of the function is to allow for either a single node or an entire
// linked list to be inserted at any location (front, middle, end) of the main
// linked list.
void Insert(node* newNode,node* target)
{
    node* stepNode = NULL;

    // If newNode is the first node in the list.
    if(target == HEAD)
    {
        // 1. Make HEAD point to first node of newNode.
        HEAD->next = newNode;

        // 2. Make first node of newNode point back to HEAD.
        newNode->prev = HEAD;

        // 3. Find the last node of newNode.
        stepNode = newNode;
        while(stepNode->next != NULL)
            stepNode = stepNode->next;
        newNode = stepNode;

        // 4. Make this last node point to TAIL.
        newNode->next = TAIL;

        // 5. Make TAIL point back to the last node.
        TAIL->prev = newNode;
    }

    // Else if newNode is last node in list.
    else if(target == TAIL->prev)
    {
        // 1. Establish the link between target and the first
        // node of newNode.
        target->next = newNode;
        newNode->prev = target;

        // 2. Find the last node of newNode.
        stepNode = newNode;
        while(stepNode->next != NULL)
            stepNode = stepNode->next;
        newNode = stepNode;

        // 3. Link the last node of newNode and TAIL.
        newNode->next = TAIL;
        TAIL->prev = newNode;
    }

    // Else if the newNode is to be inserted at the front
    // of the list.
    else if(target == HEAD->next)
    {
        // 1. Link HEAD with the first node of newNode.
        HEAD->next = newNode;
        newNode->prev = HEAD;

        // 2. Find the last node of newNode.
        stepNode = newNode;
        while(stepNode->next != NULL)
            stepNode = stepNode->next;
        newNode = stepNode;

        // 3. Link newNode with target.
        newNode->next = target;
        target->prev = newNode;
    }

    // Else, newNode is inserted somewhere in the middle of the
    // list.
    else
    {
        // 1. Link target with the first node of newNode.
        target->next = newNode;
        newNode->prev = target;

        // 2. Find the last node of newNode.
        stepNode = newNode;
        while(stepNode->next != NULL)
            stepNode = stepNode->next;
        newNode = stepNode;

        // 3. Find target's next node, prior to insertion.
        node* xNode = TAIL;
        while(xNode->prev != target)
            xNode = xNode->prev;

        // 4. Link the last node of newNode with xNode.
        newNode->next = xNode;
        xNode->prev = newNode;
    }
}

Any suggestions rock, my fingers are raw from scratching my head.

Share this post


Link to post
Share on other sites
Advertisement
First, realize that the C++ standard library provides a doubly-linked list; it is called std::list, in the <list> header. Although it looks like you really are writing in C, so whatever.

Second, note that a list of n items offers n+1 places that you might want to insert a node. Special cases for the head and tail are only needed if you want to insert in front of the head, or behind the tail. And if you specify an insertion point just by a target node, you must have a clear notion of whether you want to insert "before" or "after" the target.

Third, insertion into a list will never require searching through the list for things to insert. The only pointers you need to manipulate are those of the object being inserted, and of the list nodes immediately before and after it (in the middle; whichever one of those actually exists at the end); everything else already points where it needs to.

Fourth, be aware of the order in which you assign the pointers. Oh, and don't use either pointer of the inserted item before assigning them; those pointers aren't useful (and they should be NULL, assuming a halfway sane design).

To insert "new" "after" a "target", in the middle:

First, new->prev points at target. (If there is no target, i.e. we're at beginning of list, it points NULL.)
Next, new->next points at target->next. (If there is no target, point to the old head of the list.)
Next, target->next points at new, now that we've used the value. (If there is no target, reset the head pointer accordingly.)
Finally, new->next->prev points at new. (We can't use target->next any more to fetch the object "after" new, because we already reset that pointer.)

Similarly for insertion "before"; swap nexts and prevs, but use the same order of events.

Draw it on a piece of paper with boxes and arrows if you're confused.

Share this post


Link to post
Share on other sites
What he said

But if you still need help debugging, let us know what is going wrong...losing nodes, inserting improperly, not working at all, etc. And post your most current code. or PM me. one or the other.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!