Writing an Insert Algorithm for an Ordered Linked List C++

Question

I'm writing an insert algorithm for an ordered linked list. I've got most of the algorithm completed, but the one while loop condition is throwing me off. I think the rest of it I have correct, but any help with it would be appreciated, thanks!

bool MyLinkedList::Insert(ListNode *newNode)
{
    // Assume ListNode is a structure and contains the variable int key;
    // Assume the function returns true if it successfully inserts the node
    ListNode *back = NULL, *temp = head;
    if(head == NULL)   // Check for inserting first node into an empty list
    {
        head = newNode;
        return true;
    }   
    else
    {       // Search for insert location
        while((**???**) && (**???**))
        {
            back = temp; // Advance to next node
            temp = temp -> next; 
        {

        // Check for inserting at head of the list
        if(back == NULL) 
        {
            newNode -> next = head; // Insert at head of list
            head = newNode;
            return true;
        }
        else // Insert elsewhere in the list
        {
            newNode -> next = temp;
            back -> next = newNode;
            return true;
        }
    }
    return false;  // Should never get here
}

The mystery code is presumably whatever is needed to compare two of your ListNode structures. Without know what a ListNode is or how they should be compared no one can help you with that. — Jonathan Potter
– Jonathan Potter, Commented Oct 16, 2013 at 20:12
MyLinkedList class contains private: ListNode *head. the ListNode structure contains: int Key, double dataValue, and ListNode *next. the next pointer in newNode has already been set to NULL. — Larry T.
– Larry T., Commented Oct 16, 2013 at 20:14

user2784234 · Accepted Answer · 2013-10-16 20:28:42Z

3

I am assuming you have the following structure for ListNode (based on your prior comment).

struct ListNode {
      int Key;
      double dataValue;
      ListNode *next;
}

On the assumption that the list is ordered based on the key values, the while loop condition should look like this:

 while((temp != NULL) && (temp->Key < newNode->Key))

The rest of the code seems to agree with it.

The second argument would need change if the comparison methodology for ordering the sorted list is different than simple key comparison.

answered Oct 16, 2013 at 20:28

user2784234

4513 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sandymatt · Accepted Answer · 2013-10-16 20:15:20Z

0

while((**???**) && (**???**))

You need to insert your comparisons here. Whatever kind of data is inside the ListNode, you should have some way of comparing two of them. I suspect you have an overloaded operator if it isn't a primitive type.

answered Oct 16, 2013 at 20:15

sandymatt

5,5851 gold badge21 silver badges19 bronze badges

Collectives™ on Stack Overflow

Writing an Insert Algorithm for an Ordered Linked List C++

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related