Thread: Merging Linked Lists

  1. #1
    Unregistered
    Guest

    Merging Linked Lists

    my head hurts so much...
    I'm having a lot of problems with this. I know the answer is so simple, but I just can't figure it out. I'm trying to take two presorted linked lists, and combine them into one sorted linked list. Here's what I've got so far. As always, it's my logic that's the error.

    list definition:

    struct DblNode
    {
    int Data;
    DblNode *Next, *Prev;
    };

    merging function:

    void MergeLists(DblNode* &resList, DblNode* &fListOne, DblNode* &fListTwo)
    {
    DblNode *curRes, *curFirst, *curSecond;
    resList = new DblNode;
    curRes = resList;
    curFirst = fListOne;
    curSecond = fListTwo;
    while(curFirst->Next != NULL || curSecond->Next != NULL)
    {
    curRes = new DblNode;
    if(curFirst->Data < curSecond->Data)
    {
    curRes = curFirst;
    curRes->Next = curSecond;
    curRes = curRes->Next;
    }
    else
    {
    curRes = curSecond;
    curRes->Next = curFirst;
    curRes = curRes->Next;
    }
    curFirst = curFirst->Next;
    curSecond = curSecond->Next;
    }
    if(curFirst->Next == NULL)
    {
    while(curSecond->Next != NULL)
    {
    curRes = new DblNode;
    curRes = curSecond;
    curRes = curRes->Next;
    curSecond = curSecond->Next;
    }
    }
    else
    {
    while(curSecond->Next != NULL)
    {
    curRes = new DblNode;
    curRes = curSecond;
    curRes = curRes->Next;
    curSecond = curSecond->Next;
    }
    }
    curRes->Next = NULL;
    }

    the code I've got here so far is only supposed to link the list with the Next pointer, not the Prev. The reason for this is because if I can't figure out how to do that, why should I clutter it up with some more errorous code? Thanks for the help guys.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    156
    As a general rule you should always check the return of any pointer. Like in your new you allocate and assume there's a value. While in this case new will throw a bad_alloc if it fails and you'll never get a chance to check the return. But it is a VERY good habit to get into.

    Enough evangelizing.... Just after a quick look in a Merging of two lists there should never be a need to create any new nodes, since you are just merging. All you should be doing is adjusting the existing pointers. And a big clue is always keep the current_pointer, and previous_pointer for your insertion.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    25
    Personally I would just create a new linked list from the two with a loop to read from them into it. Mainly like a constructor with arrays of head nodes, then it would loop threw each head node adding data until it reached the end.

    Just depends on what you are using it for though. If you are going to be working with large lists a merge function would be overall better then the above listed.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    156
    You could do it that way but it would not be a very effiecient approach. Remember every call to new calls the object's constructor and if its derived it calls that constructor and so on.... As well as each delete calls the respective destructor.

    Also, with every call to new the memory pool is searched for a block of memory large enough to satisfy the request. This is done by checking a map or directory of some sort that show which blocks are currently availible. It's a quick process but it just one more thingy....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. merging linked lists
    By scwizzo in forum C++ Programming
    Replies: 15
    Last Post: 09-14-2008, 05:07 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. merging two linked lists..
    By Makimura in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2001, 12:34 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM