Cannot Insert into Ordered Linked List

Question

I am writing a three file C++ program for my class. This program is ordered linked list. The program compiles but crashes when I attempt to insert (Run the program, select choice press enter, type an int to insert and press enter). Any help would be greatly appreciated.

Driver File:

#include "SortedLinkedList.h"
#include <iostream>
using namespace std;


int displayMenu();
void proccessChoice(int, SortedLinkedList&);

int main()
{
    SortedLinkedList sSList;
    int choice = displayMenu();

    do
    {
        if (choice != 3)
        {
            proccessChoice(choice, sSList);
        }
    } while (choice != 3);


    return 0;
}

void proccessChoice(int input, SortedLinkedList& l)
{
    switch(input)
    {
        case 1:
            int num;
            cout << "Please enter a int: ";
            cin >> num;
            l.addItem(num);
        break;
        case 2:
            l.popFirst();
        break;
    }


}

int displayMenu()
{
    int choice;

    cout << "menu" << endl;
    cout << "===========" << endl;
    cout << "1. add an int" << endl;
    cout << "2. Show Sorted Linked List" << endl;
    cout << "3. Exit" << endl;
    cin >> choice;
    cin.ignore();

    return choice;
}

Declaration File:

struct sslNode
{
    sslNode* next;
    int item;
};

class SortedLinkedList
{
private:
    sslNode* head;
    bool isEmpty ();

public:
    SortedLinkedList();
    ~SortedLinkedList();
    void addItem(int);
    int popFirst();
};

Implementation File:

#include <iostream>
using namespace std;
#include "SortedLinkedList.h"

SortedLinkedList::SortedLinkedList()
{
    head = NULL;
}

SortedLinkedList::~SortedLinkedList()
{
    sslNode *temp, *nextLink;
    nextLink = head;

    while(nextLink != NULL)
    {
        temp = nextLink->next;
        delete nextLink;
        nextLink = temp;
    }
}

bool SortedLinkedList::isEmpty()
{
    return (head == NULL);
}

void SortedLinkedList::addItem(int itemToInsert)
{
    sslNode* cur; 
    sslNode* prev;
    sslNode* newNode = new sslNode();
    newNode->item = itemToInsert;
    newNode->next = NULL;

    cur = head;
    prev = NULL;
    bool moreToSearch (cur != NULL);

    while (moreToSearch) //Find insertion point
    {
        if (cur->item > newNode->item) // while current location has a greater value then what needs to be inserted move pointers forward.
        {
            prev = cur;
            cur = cur->next;
            moreToSearch = (cur != NULL);
        } 
        else // if current loacation and what is to be inserted are equal or less then we have found the point of insertion 
        {
            moreToSearch = false;
        }
    }

    if (prev = NULL)
    {
        newNode->next = head->next;
        head = newNode;
    }
    else
    {
        prev->next = newNode;
        newNode->next = cur;
    }

    //Insert as only item in list
    //Insert in found location
}

int SortedLinkedList::popFirst()
{
    sslNode* first;
    first = head->next;
    head = head->next;
    int item = first->item;

    return item;
}

Borgleader · Accepted Answer · 2012-09-13 19:33:41Z

2

Your problem is you forgot an =

if (prev = NULL)
{
    newNode->next = head->next;
    head = newNode;
}
else
{
    prev->next = newNode;
    newNode->next = cur;
}

if(prev = NULL)

should be

if(prev == NULL)

right now this is always false because prev becomes null which evaluates to false and then it fails at

prev->next = newNode;

because your are dereferencing the null pointer.

You'll also want to treat the case where head == NULL before trying to insert anything. Basically if head == NULL, head = newNode;

edited Sep 13, 2012 at 19:33

answered Sep 13, 2012 at 19:19

Borgleader

15.9k5 gold badges48 silver badges63 bronze badges

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

5 Comments

drescherjm Over a year ago

I believe it would still crash if head was NULL at newNode->next = head->next;

Borgleader Over a year ago

Yes you're probably right but when I ran his code that's where it crashed so I explained why it was crashing with the current state of the code.

Realz Slaw Over a year ago

Oh, you answered it here, shall I delete my answer?

Zzz Over a year ago

Thanks for the answer, I corrected that and a few other mistakes that I found and everything works great!

Borgleader Over a year ago

Nah leave yours it mentions another problem in his code which I didn't cover.

Realz Slaw · Accepted Answer · 2012-09-13 19:34:26Z

2

It crashes because head is initialized to NULL. You probably want to make a dummy head node, depending on your design, or check if its NULL before using it in addItem().

This is how things go down:

SortedLinkedLis

t::SortedLinkedList() // ctor is called
...
head = NULL

SortedLinkedList::addItem(int)
sslNode* cur;
...

cur = head;
...

bool moreToSearch (cur != NULL) // this is surely false
...

if (prev = NULL)
{
    newNode->next = head->next;
 ...//BUT head == NULL ! crash!

edited Sep 13, 2012 at 19:34

answered Sep 13, 2012 at 19:12

Realz Slaw

3,3181 gold badge28 silver badges40 bronze badges

2 Comments

Borgleader Over a year ago

No that gets skipped because the while clause says if cur != NULL but you just said it cur = head which is null.

Zzz Over a year ago

Thanks for the answer, I corrected that and a few other mistakes that I found and everything works great!

Collectives™ on Stack Overflow

Cannot Insert into Ordered Linked List

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related