Adding nodes to linked list alphabetically in c++

Question

I'm trying to make a linked list that gets words from the user until the input is blank, and every word is added so the list stays in alphabetical order. However, only the first node is printed. Is there something I'm doing wrong? Here's what I have (minus the header and declarations):

    //put in additional nodes until the input is blank
while(in != " "){
    cin >> in;
    newPtr->data = in;
    prevPtr->data = "";
    prevPtr->next = NULL;
    nextPtr = list;
    //shift the prevPtr and nextPtr until newPtr is alphabetically between them
    while(!(prevPtr->data<=in && nextPtr->data>in)){
        prevPtr = nextPtr;
        nextPtr = prevPtr->next;
    }
    //make newPtr point to the next node
    if(nextPtr != NULL){
        newPtr->next = nextPtr;
    }
    //make newPtr the "next" pointer of the previous node, if any
    if(prevPtr != NULL){
        prevPtr->next = newPtr;
    }
    //if there's nothing before newPtr, make it the first node
    else{
        list = newPtr;
    }
    printList(list);
};

}

I agree with paddy, you should at least give us the code to printList — Michael Wildermuth
– Michael Wildermuth, Commented Oct 16, 2012 at 22:50

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

I would post this as a comment, because I am afraid I might be missing something, but I can't yet do this, so here goes a non-answer:

What keeps you from using the std::list? You can insert a word, check if it is non-empty, immediately apply a the standard sorting algorithm (It relies on the comparison operators of the sorted objects) and print it. It is fast, your code is short and readable and you don't spend your time reinventing the wheel.

PS: If you want to test for an empty string it should be "", not " " , I think.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Oct 16, 2012 at 22:56

Konstantin Schubert

3,3962 gold badges36 silver badges47 bronze badges

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

2 Comments

user1751466 Over a year ago

I'll be completely honest. I'm doing this as part of a class and the teacher wants us doing it this way. This question would also be useful to future readers who want to understand inner workings of the internal library.

Michael Wildermuth Over a year ago

No worries, we have all been there. This stuff takes time

Michael Wildermuth · Accepted Answer · 2012-10-16 23:50:00Z

0

I think there is a number of issues here.

For one in the initial iteration what is prevPtr->data pointing at? If it's pointing at nothing or hasn't been allocated to any memory you shouldn't be setting this to anything yet.

Plus you need to allocate memory for newPtr on every iteration, otherwise you are just writing over the memory location of where it is pointing to last from the in the list.

Second lets assume that prevPtr is pointing to something, on the second iteration (or more) of this while loop prevPtr has been moved farther down the list (prevPtr = nextPtr) which would cause prevPtr->data = " " to erase any data in that element. So you could be printing the first node plus a bunch of spaces afterwards.

Third you should check if list is NULL first in your loop, because if loop is NULL, nextPtr->data would be pointing at junk which is not good. This NULL check on list could be your corner case of the first element.

Try something like this, I didn't have time to test it but it should get going in the right direction:

Node *list = NULL; 

while(in != " "){
    cin >> in;
    Node *newPtr = new Node();
    newPtr->data = in;
    newPtr->next = NULL;

    prevPtr = list;
    nextPtr = list;

    // Do we have an empty list
    if(list != NULL)
    {
        // Corner Case: First on the list
        if(newPtr->data <= prevPtr->data)
        {
            list = newPtr;
            newPtr->next = prevPtr;
        }
        else
        {
            // CASE: Somewhere between the first and the list
            while(nextPtr->next != NULL)
            {
                nextPtr = nextPtr->next;
                if(newPtr->data >= prevPtr->data && newPtr->data <= nextPtr->data)
                {
                    prevPtr->next = newPtr;
                    newPtr->next = nextPtr;
                    break;
                }
                prevPtr = prevPtr->next;
            }

            // Corner Case: end of list
            if(nextPtr->next == NULL)
            {
                nextPtr->next = newPtr;
            }
        }
    }
    else 
    {
        // Corner Case: We had an empty list
        list = newPtr;
    }
    printList(list);

edited Oct 16, 2012 at 23:50

answered Oct 16, 2012 at 23:08

Michael Wildermuth

5,8723 gold badges34 silver badges49 bronze badges

2 Comments

user1751466 Over a year ago

Before the loop is this set of declarations: list = new Node; string in; cin >> in; list->data = in; list->next = NULL; newPtr = new Node; prevPtr = new Node; Will this be sufficient? If not how would you allocate the memory?

Michael Wildermuth Over a year ago

You could make that work, but you don't need to allocate prevPtr, and you should allocate newPtr in every iteration of the loop. I added more to my answer check it out.

Collectives™ on Stack Overflow

Adding nodes to linked list alphabetically in c++

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related