1

I am attempting to insert a new node into a sorted linked list of integers, but am encountering problems when trying to add to lists that are more than two nodes long. I am using the following code to do this

// Initialise place-holder pointers at first and second nodes
TempPrevious = Head;
TempNext = Head -> Next;

do // Iterate until the right spot is found
{       
    // Does the new node fit between the currently selected nodes?
    if ((NewNode -> Element > TempPrevious -> Element) &&
            (NewNode -> Element < TempNext -> Element))
    {
        NewNode -> Next = TempNext;
        TempPrevious -> Next = NewNode;
        return true;
    }

    // Does the new node fit in further along the list?
    else if (NewNode -> Element > TempNext -> Element)
    {
        // Has the end of the list already been reached?
        if (TempNext -> Next == NULL)
        {
            TempNext -> Next = NewNode;
            return true;
        }

        // Or are there still more nodes to come?
        else if (TempNext -> Next != NULL)
        {
            TempPrevious = TempNext;
            TempNext = TempNext -> Next;
        }
    }
} while (TempNext -> Next != NULL);

I've already accounted for an empty list, a single node list, and a two node list, as well as inserting the new node at the start of a list more then two element long, and all of those parts work fine. I've identified the problem as being the final else if in the provided code as it seems that the pointers TempNext and TempPrevious are not being moved along with each iteration of the do-while loop. I've come to this conclusion after constructing lists containing the following elements and observing the output of the PrintList() function:

Input: 1,2,3,4,5
Output: 1,2,0

Input; 5,4,3,2,1
Output: 1,2,3,4,5

I've looked over my code and ran these tests, but cannot find any fault in the logic. Can anyone else see where I'm going wrong here?

The full list :: Insert() function is

// Insert new element
template <class Type>
bool list<Type> :: Insert (const Type& NewElement)
{
    Node *NewNode;
    Node *TempNext;
    Node *TempPrevious;
    NewNode = new Node;
    NewNode -> Element = NewElement;

    if (Empty()) // If the list is empty
    {
        Head = NewNode;
        return true;
    }

    else if (Head -> Next == NULL) // If there is only a single node in the list
    {
        // If the element is less than or equal to the new one
        if (Head -> Element <= NewNode -> Element)
        {
            Head -> Next = NewNode;
            return true;
        }
        // If the element is greater than the new one
        else if (Head -> Element > NewNode -> Element)
        {
            NewNode -> Next = Head;
            Head = NewNode;
            return true;
        }
    }

    // Multi-node lists - the list has at least two existing nodes

    // Initialise place-holder pointers at first and second nodes
    TempPrevious = Head;
    TempNext = Head -> Next;

    // Does the new node go at the start?
    if (NewNode -> Element < TempPrevious -> Element)
    {
        NewNode -> Next = TempPrevious;
        Head = NewNode;
        return true;
    }

    do // Iterate until the right spot is found
    {       
        // Does the new node fit between the currently selected nodes?
        if ((NewNode -> Element > TempPrevious -> Element) &&
                (NewNode -> Element < TempNext -> Element))
        {
            NewNode -> Next = TempNext;
            TempPrevious -> Next = NewNode;
            return true;
        }

        // Does the new node fit in further along the list?
        else if (NewNode -> Element > TempNext -> Element)
        {
            // Has the end of the list already been reached?
            if (TempNext -> Next == NULL)
            {
                TempNext -> Next = NewNode;
                return true;
            }

            // Or are there still more nodes to come?
            else if (TempNext -> Next != NULL)
            {
                TempPrevious = TempNext;
                TempNext = TempNext -> Next;
            }
        }
    } while (NewNode -> Next != NULL);

    delete TempNext, TempPrevious;
}
Improve this question
3
  • 1
    Homework? If not, here comes the default advice: use the STL list or vector classes, as appropriate. Commented Mar 19, 2011 at 16:44
  • Sorry, forgot to tag it as such :P Commented Mar 19, 2011 at 16:45
  • Have you tried drawing diagrams of the linked list and walking through the code, line by line, and changing the diagrams to match what the code is doing? A linked list is far easier to understand when you have pictures (I can't ever figure out linked list algorithms without drawing pictures!) Commented Mar 19, 2011 at 16:50

3 Answers 3

Reset to default
2

You are overcomplicating the issue needlessly. There are several things that aren't quite right in your code:

  1. The loop should not be a do ... while -- you want to check if Current == NULL before touching anything (to handle an empty list).
  2. Inside the loop you have a test for "am I looking at NewNode's final position?". You don't need any other conditional since if you are not looking at the final position, it's time to continue looping.

You can do it as easy as:

Previous = NULL;
for (Current = Head; Current != NULL; Previous = Current, Current = Current->Next) {
    if (NewNode->Element >= Current->Element) {
        continue;
    }

    // Perform the insertion    
    NewNode->Next = Current;
    if (Current == Head) {
        Head = NewNode;
    }
    else {
        Previous->Next = NewNode;
    }
    return;
}

// We haven't inserted yet after going through all the list
// Previous now points to the last item, or NULL if the list was empty, so:
NewNode->Next = NULL;
if (Previous = NULL) {
    Head = NewNode;
}
else {
    Previous->Next = NewNode;
}
return;
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks a lot for the code, but it's segfaulting at the second last line. Are you sure this is all correct?
1

I think the problem is on your while condition, it should be:

while(TmpNext != NULL)

If you already test the empty or the one element list, you can reduce all the other cases to:

TempPrevious = Head;
TempNext = Head->Next;

while(TempNext != NULL)
{
    if (TempNext->Element > NewNode->Element) 
    {
        NewNode->Next = TempNext;
        TempPrevious->Next = NewNode;
        return true;
    }
    TempPrevious = TempNext;
    TempNext = TempNext->Next;
}

// At this point we are sure that we did not inserted the element 
// anywhere in the list so we can safely added to the end
TempPrevious->Next = NewNode;
Improve this answer

Comments

0

NewNode -> Next != NULL is always false, so you only get one pass through the loop.

In fact, that loop should continue until the node is inserted. If you end the loop through the condition, it means you haven't inserted the node.

The delete TempNext, TempPrevious at the end is responsible for the 0 in one of your example lists. When you delete through these variables, you destroy the actual elements of the list to which they point.

Improve this answer

2 Comments

Ah, good spot. Unfortunately, changing it to `TempNext -> Next != NULL) hasn't fixed it.
@Chris – That would break the loop when (TempPrevious, TempNext) is the final pair, just before reaching the // Has the end of the list already been reached? clause.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.