0

I was tasked with creating functions to add and delete nodes in a linked list given input data as an int and the char for with function to call. I'm not sure what I'm doing wrong. The only error I was given was: Exited with return code -11 (SIGSEGV). And a compiler method: main.cpp: In function ‘void listInsertValue(ListNode*&, ListNode*&, int)’: main.cpp:111:23: warning: ‘toGoAfter’ may be used uninitialized in this function [-Wmaybe-uninitialized] 111 | toGoAfter->next = head;

Any help is appreciated. Thanks!

#include <iostream>
using namespace std;

struct ListNode
{
    int data;
    ListNode* next;
};

void listRemoveAfter(ListNode*&, ListNode*&, ListNode*);
void listPrepend(ListNode*&, ListNode*&, ListNode*&);
void listDeleteValue(ListNode*&, ListNode*&, int);
void listInsertValue(ListNode*&, ListNode*&, int);
void listInsertAfter(ListNode*&, ListNode*&, ListNode*, ListNode*);

int main()
{
    
    ListNode *head = nullptr, *tail = nullptr;
    ListNode *temp;
   char choice;
   int val;

   //Write a main like you did in the previous lab
   char command;
   int number;
   
   cin >> command;
   while(command != 'Q')
   {
        if(command == 'I')
        {
            cin >> number;
            listInsertValue(head,tail,number);
        }
        else
        {
            cin >> number;
            listDeleteValue(head,tail,number);
        }
        
      cin >> command;
   }
   ListNode* current;
   current = head;
    while (current != nullptr)
    {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
    return 0;

}

//From previous lab - already complete
void listPrepend(ListNode*& h, ListNode*& t, ListNode*& n)
{
    if (h == nullptr)
    {
        h = n;
        t = n;
    }
    else
    {
        n->next = h;
        h = n;
    }
}

//From book, write yourself using the book code in 17.6 as a starting point
void listInsertAfter(ListNode*&head, ListNode*&tail, ListNode* curNode, ListNode* newNode)
{
   if (head->next == nullptr) 
   { 
      head= newNode;
      tail = newNode;
   }
   else if (curNode->next == tail) 
   { 
      tail->next = newNode;
      tail = newNode;
   }
   else 
   {
      newNode->next = curNode;
      curNode->next = newNode;
   }
}


//This function is mostly written, but you will need to add some code near the TODOs to complete the algorithm from the slides
void listInsertValue(ListNode*& head, ListNode*& tail, int val)
{
    ListNode* toGoAfter, *newNode;

   //TODO - create a new ListNode (newNode) with a data value of val (3 lines of code)
   newNode = new ListNode;
   newNode->data = val;
   newNode->next = nullptr;
    //TODO - check whether the list is empty in the if condition
    if (head == nullptr)
    {
        listInsertAfter(head, tail, nullptr, newNode);
    }
    //TODO - use the else if to check whether the the value passed in is smaller than the value in the head
    else if (head->data > val)  //need to add to beginning of the list
    {
        listPrepend(head, tail, newNode);
    }
    else //need to add somewhere else in the list
    {
       //TODO - set toGoAfter to point to the head
      toGoAfter->next = head;
      //loop to find the location to insert the value
        while (toGoAfter->next != nullptr && toGoAfter->next->data < val)
        {
           //TODO - set toGoAfter to point to the node after toGoAfter, like is done in traversals
           toGoAfter = toGoAfter->next;
        }

      //We have found the location, so we can insert
        listInsertAfter(head, tail, toGoAfter, newNode);

    }
}

//modify
void listDeleteValue(ListNode* &head, ListNode*& tail, int val)
{
    ListNode *temp;

   //TODO - check if list is not empty in if condition
    if (head->next == nullptr)
    {
       // TODO - check if value of head matches val passed in
        if (head->data == val)
            listRemoveAfter(head, tail, nullptr);
    }
        else
        {
           //loop searches for value to delete in node following temp
           //TODO - set temp to point to the head
           temp->next = head;
            while (temp->next != nullptr && temp->next->data != val)
            {
               //TODO - set temp to point to the node after temp, like is done in traversals
               temp = temp->next;
            }

         //TODO - make sure a node exists after temp, meaning the value to delete was found
            if (temp->next != nullptr)
                listRemoveAfter(head, tail, temp);
        }
    
}

//From book, write yourself using the book code in 17.7 as a starting point
//Also add to the book's code, the code to delete nodes from memory
void listRemoveAfter(ListNode* & head, ListNode*& tail, ListNode* curNode) 
{
    ListNode *sucNode, *toDelete;
    
     if (curNode->next == nullptr && head->next != nullptr) 
     {
       sucNode = head->next;
      head->next = sucNode;

      if (sucNode->next == nullptr) 
      { // Removed last item
         tail->next = nullptr;
         toDelete = head;
      }
   }
   else if (curNode->next != nullptr)
   {
      sucNode = curNode->next->next;
      curNode->next = sucNode;

      if (sucNode-> next == nullptr)
      { // Removed tail
         tail->next = curNode;
         toDelete = curNode->next;
      }
      
   }

    delete toDelete;  //needed after the if/else if to remove the deleted node from memory

}
4
  • 3
    Advice -- Get rid of the cin statements and call the functions directly with known data that causes the issue. This allows you (and others) to run the code directly without having to type in input every time the program is run. Commented Mar 18, 2021 at 13:49
  • Your first problem is indeed in the listInsertValue function. In your first insertion you call listInsertAfter with head as first param....but you just checked that head == nullptr so....BOOM when you try to check if(head->next == nullptr) :) Another problems await you. Good luck :) Commented Mar 18, 2021 at 14:10
  • I think you might haven issue with toGoAfter->next = head;. You never set toGoAfter to any value but you're still trying to get it's next value. I think in that line you just want toGoAfter = head; so that toGoAfter itself is pointing to head. Commented Mar 18, 2021 at 14:51
  • Linked lists are a very important concept that you want to make sure you understand very well. As you're struggling with it, I'm going to recommend you google for "linked list tutorial" and then find one that looks good. There are some amazing tutorials on YouTube lately, if you learn well that way. It's worth taking the time to really understand. Commented Mar 18, 2021 at 20:15

1 Answer 1

1

For most part you are not handling the case when there ia no element in the list. While inserting handle 4 use cases

  1. Head==nullptr => head =newNode;
  2. head->data > val
  3. Tail->data < val
  4. else case : insert in middle

Generic mistake: accessing ptr-> next, when ptr is nullptr

In general you want to use a debugger and any access to a memory 0x0 (nullptr) will start resolving your issues. ie head is 0x0 and you are doing operationa like head->data ==val

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.