Segmentation Fault using linked list insertion sort

Question

I've been working on this project for a while now and it's completely done. Except that when I run it in Linux I get a segmentation fault. I'm a beginner with C++, and while I understand that a segmentation fault has to do with trying to access already freed memory, I don't understand where I'm going wrong with the memory I am trying to access. Below is the function where I am having the problem. I marked the line of code that I think is causing the problem with a comment. Please let me know if you see what I am doing wrong, I'd really appreciate it!

int TsuPod::SortSongList(string x, string y, int z)
{
    Song InsertSong(x, y, z); //creates song object

    node* newNode = new node; //creates new node

    //initializes all the node's values
    newNode->title = InsertSong.GetTitle();
    newNode->artist = InsertSong.GetArtist();
    newNode->size = InsertSong.GetSize();

    //case 1 - Inserting into an empty list
    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        curr = head;
    prev = NULL;

    //Traverse
    while(curr != NULL)
    {
            if(curr->title >= newNode->title)
        {
            break;
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
        }
    }   

    if(curr == head)
    {
    //case 2 - Insert at head
    newNode->next = head;
    head = newNode;       //Causing Segmentation fault?
    }
    else
    {
    //case 3 - Insert after the head
    newNode->next = curr;
    prev->next = newNode;
    }

    remainingMem = remainingMem - newNode->size;
    slots++;
    return 1;
}

Do you modify head somewhere else in your code? By calling other functions somewhere else? — mostruash
– mostruash, Commented Apr 20, 2014 at 0:02
Does node have a constructor? Otherwise, it looks like newNode->next is not initialized in case 1. — Reto Koradi
– Reto Koradi, Commented Apr 20, 2014 at 0:11
As long as your posting code, post the constructor for node. As written there is no verification that it initializes the next member to NULL, which would be catastrophic to this algorithm (which can be made considerably simpler regardless). It would also make your algorithm much cleaner if all the InsertSong stuff were done in the constructor for node, thereby eliminating the clutter here. — WhozCraig
– WhozCraig, Commented Apr 20, 2014 at 0:20

mostruash · Accepted Answer · 2014-04-20 00:07:46Z

1

The first thing that hits me in the eye is the following:

if(head == NULL)     <--- lets assume that head was null
{
    head = newNode;  <---- executed
}

else
{                    <---- not executed, skipped
    curr = head;     <---- this is skipped, curr is not assigned to head
    prev = NULL;

    //Traverse
    while(curr != NULL) { ... }
}  

if(curr == head)    <----- Huh... What is curr right now? When was 
                           curr last set to a value 
{ ... }

I'm not saying that segmentation fault is caused by this, I'm just saying that this piece of code is fishy.

answered Apr 20, 2014 at 0:07

mostruash

4,1892 gold badges26 silver badges40 bronze badges

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

Collectives™ on Stack Overflow

Segmentation Fault using linked list insertion sort

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related