C++ Singly Linked List Insertion Sort

Question

So hey, I'm having a problem with this project I have. I'm supposed to read integers from a file and insert them into a list. There's a findSpot function that needs to be implemented that traverses the linked list and if the next node's value is larger than what is being checked, it returns the current "spot". And then we output the linked list to a separate file.

Here's the code.

#include <iostream>
#include <fstream>
using namespace std;

class listNode {

public:
    int value;
    listNode* next;
    friend class linkedList;

    listNode()
        : value(0)
        , next(NULL)
    {
    }

public:
    ~listNode(){

    };
};

class linkedList {
    listNode* listHead;

public:
    linkedList()
        : listHead(NULL)
    {
    }

    bool isEmpty()
    {
        return (listHead == 0);
    }

    void listInsert(int data, listNode* spot)
    {

        listNode* newNode;
        newNode->value = data;
        newNode->next = NULL;

        if (isEmpty()) {
            listHead = newNode;
        }

        else {
            newNode->next = spot->next;
            spot->next = newNode;
            cout << newNode;
        }
    }

    /*void listDelete ()
    {

    }*/

    listNode* findSpot(int data)
    {
        listNode* spot;
        spot = listHead;

        while (spot->next != 0 && spot->next->value < data) {
            spot = spot->next;
        }

        return spot;
    }

    void printList(listNode* spot)
    {
        listNode* newNode = spot;

        while (newNode != NULL) {
            cout << "Inserting " << newNode->value << ": "
                 << "listHead-->(" << newNode->value << "," << newNode->next->value << ")-->(";
            newNode = newNode->next;
        }

        cout << endl;
    }

    /*~linkedList()
    {
        listNode* temp = spot->next;
        spot->next = spot->next->next;
        delete temp;

    }*/
};

int main(int argc, char* argv[])
{

    int data;
    listNode* spot;

    ifstream infile;
    infile.open(argv[1]);
    ofstream outfile(argv[2]);

    cout << "Reading Data from the file" << endl;

    while (infile >> data) {
        cout << data << endl;
    }

    infile.close();

    linkedList myList;
    infile.open(argv[1]);

    while (infile >> data) {
        myList.findSpot(data);
        myList.listInsert(data, spot);
        myList.printList(spot);
    }

    cout << "Printing your linked list to the output file.";

    /*while (outfile.is_open())
    {
        myList.printList();

    }*/

    infile.close();
    outfile.close();

    return 0;
}

I don't know if the problem lies mainly in the insertList function or if it's the findSpot function. The findSpot function seems correct to me but I may just be missing something.

As I run the code, the actual reading of the file the first time is fine. Actually inserting anything into the linked list causes the program to hang.

Why all the empty lines in your code? It makes it very hard to read. And before reading anything from a file, you should be testing whether your linked list actually works with a small main function that makes calls to insert entries with hard-coded values, so that it is easy for you (and others) to diagnose. It makes no sense to worry about file reading if your linked list doesn't work at all. — PaulMcKenzie
– PaulMcKenzie, Commented Feb 14, 2016 at 1:21
Oh, sorry I guess it's just a weird personal preference. The empty space makes it so that I can easily distinguish stuff from each other XD — user2444400
– user2444400, Commented Feb 14, 2016 at 1:22
Please reformat and reindent your code properly. Don't you want to make your code as understandable and as readable as possible, making it easier for others to see what you've done, and where the problem is? — Sam Varshavchik
– Sam Varshavchik, Commented Feb 14, 2016 at 1:23

Signal Eleven · Accepted Answer · 2016-02-14 07:17:15Z

Ok, lets try this again. I'll actually include some code, but please try to use this as a learning point, and not something to just copy paste. I know you said you were copying your teachers algorithm, but what they gave you is probably just that, an algorithm. It is your job to actually implement that in working code, checking for error conditions, etc. Anyway, here we go:

For the function findSpot:

listNode* linkedList::findSpot(int data) {
  listNode* spot = listHead;  // Initialize spot to start of list

  if ( isEmpty() )    // if list is empty, return NULL
    return NULL;

  // now we know listHead isn't null, so look through the list and
  // find the entry that has a value greater than the one provided
  // return the list item BEFORE the one with the greater value
  while (spot->next != 0 && spot->next->value < data) {
    spot = spot->next;
  }

  // return the one we found;  This could be the same as listHead
  // (start of list), something in the middle, or the last item on the
  // list.  If we return from here, it will not be NULL
  return spot;
}

Now we can do the insert function:

void linkedList::listInsert(int data, listNode* spot) {

  // We need a new item to put on the list, so create it
  listNode* newNode = new listNode();
  newNode->value = data;
  newNode->next = NULL;

  // If the list is empty, update the head to point at our new object
  if ( isEmpty() ) {
    listHead = newNode;

  // otherwise point spot to new item, and new item to the one spot
  // pointed to
  } else {
    newNode->next = spot->next;
    spot->next = newNode;
  }
}

Looking at your print function, that is going to have it's own issues. It looks like you want to print the whole list, but it seems that you are starting to print from "spot". It's all very confused. It also has an issue using newNode->next->value, without checking if newNode->next is NULL. Here's a short example of what I think you are trying to do... note that I don't even need to pass in spot, just the data point added:

void linkedList::printList(int data) {

  // if some huckleberry called this before calling insert,
  // list will be empty... always a good idea to check
  if ( isEmpty())
    return;

  // first line of output... just print out the data point
  // added and start of output text
  cout << "Inserted " << data << ": " << "listHead-->(";

  // start at start of list
  listNode* newNode = listHead;

  // loop through until we find the end
  while (newNode != NULL) {

    cout << newNode->value;       // print the value
    newNode = newNode->next;      // move to the next item on the list

    // We moved to the next node;  It might be NULL and the loop will end
    // if not, we want to print an open bracket since we know another one
    // is going to be printed
    if ( newNode != NULL )
      cout << ")-->(";
  }

  // last item was just printed, so close off the last bracket
  cout << ")" << endl;
}

Hope that is somewhat helpful

Signal Eleven · Accepted Answer · 2016-02-14 03:05:33Z

0

Well, there are several problems with your program (besides formatting). In the function findSpot(), you have:

listNode* spot;
spot = listHead;

while (spot->next != 0 && spot->next->value < data) {
   spot = spot->next;
}
return spot;

The problem here is that the first time you call this, listHead is NULL, so the

while (spot->next

is going to fail, since spot is NULL.

I also notice that nowhere in your code do you call new(). In listInsert, you need to use new() to initialize your newNode variable.

Lastly, find spot has 2 conditions where it can return NULL. If the list is empty, it should return NULL, and you would want to insert at the start of the list. If the new value you are adding is greater than all the others, you will also return NULL and you would have to add to the end of the list.

Since this is a homework assignment, I don't want to write the code for you, but hopefully that helps.

answered Feb 14, 2016 at 3:05

Signal Eleven

2411 silver badge6 bronze badges

5 Comments

user2444400 Over a year ago

Since listHead is null, wouldn't the function just return Spot (which would currently be at listHead?) The While loop only causes it to traverse, in which case there would be no need to traverse since there's nothing to traverse? Won't when I use the listIInsert function, won't it use spot (which is listHead) to first insert a new node?

Signal Eleven Over a year ago

No, it won't return null, it will crash. The reason is that you are checking spot->next in your while loop. If spot is NULL, you are trying to do NULL->next, which is a problem

user2444400 Over a year ago

I'm not sure how to go about this fix? The algorithm my professor gave me was pretty much that exact thing. I don't suppose I should just initialize listHead with random values?

Signal Eleven Over a year ago

Heh, no, that wouldn't be a good idea. Maybe check if the list is empty before you enter the while loop? (and return NULL if it is?)

user2444400 Over a year ago

Well I remembered my professor saying about creating a dummy/junk node for the listHead so I tried initialized it's value to -9999. Turns out my insert works now... Too bad I have to deal with the duplicate entries now. XD

Collectives™ on Stack Overflow

C++ Singly Linked List Insertion Sort

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related