Segfault while inserting node at mid of a linked list in c++

Question

I am creating a simple singly linked list and trying to insert a node at start, mid and end of the list. But my 'insertAtMid' is not working properly and its crashes the program with error; "Exception occurred. Segmentation fault." Here is the whole program :

/*
    Write a program that creates a singly linked list until user wants and displays it. then insert a node at the beginning, middle, and end of the list.
*/
#include <iostream>
using namespace std;
struct node
{
    int data;
    node *next;
};
class linkedList
{
private:
    node *head, *tail;

public:
    linkedList()
    {
        head = NULL;
        tail = NULL;
    }
    void addNode()
    {
        int item;
        cout << "Enter data for node : ";
        cin >> item;
        node *temp = new node();
        temp->data = item;
        temp->next = NULL;
        if (head == NULL)
        {
            head = temp;
            tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = tail->next;
        }
    }
    node *getHead()
    {
        return head;
    }
    static void display(node *head)
    {
        int i = 1;
        while (head != NULL)
        {
            cout << "Node " << i << " : " << head->data << endl;
            head = head->next;
            i++;
        }
    }
    void insertAtBegining()
    {
        int n;
        cout << "Enter data you want to insert : ";
        cin >> n;
        node *temp = new node();
        temp->data = n;
        temp-> next = head;
        head = temp;
        cout << "Inserted Successfully. Updated list is : "<<endl;
    }
    static void insertAtMid(node * head)
    {
        int n, length=0, middle;
        while (head!=NULL)
        {
           length ++;
           head = head->next;
        }
        middle = length/2;
        while((middle --) > 1)
        {
            head = head->next;
        }
        cout << "Enter data you want to insert : ";
        cin >> n;
        node *temp = new node();
        temp->data = n;
        temp->next = head->next;
        head = temp;
        cout << "Inserted Successfully. Updated list is : "<<endl;
    }
};
int main()
{
    linkedList l1;
    char choice;
    int menuChoice;
    cout << "List is not created yet, please add data to create the list." << endl;
    do
    {
        l1.addNode();
        cout << "Node added. Want to add another node (Y/N) : ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    cout << "List created successfully. Select from options below : "<<endl;
    cout << "1. Display list \n2. Insert at Begining \n3. Insert at Mid \n4. Insert at End \n5. exit"<<endl;
    cin >> menuChoice;
    switch(menuChoice)
    {
        case 1:
            linkedList::display(l1.getHead());
            break;
        case 2:
            l1.insertAtBegining();
            linkedList::display(l1.getHead());
            break;  
        case 3:
            l1.insertAtMid(l1.getHead());
            linkedList::display(l1.getHead());
            break;
        case 4:
            l1.addNode();
            cout << "Successfully inserted node at end of list. Updated list is :"<<endl;
            linkedList::display(l1.getHead());
            break;  
        case 5:
            exit;
            break;
        default:
            cout << "Invalid selection...!!";            
    }
}

The compiler is showing that the error is at line 85 and segmentation error has occurred there. here is the Screenshot of error: Exception has occurred

Answer 1

Wow, you were really confused... For starters, you have a class with private: members head and tail. You do NOT pass head or tail as parameters to your member functions. Your class member functions have access to your class private members.

So you do not do:

    static void display(node *head)
    {
        ...

Instead, simply:

    void display ()
    {
        ...

You Do Not Mix Your Application And Interface

Your application is how you process data obtained from your programs user-interface. You keep the two separate. Your menu is your interface and your linked list is your application (roughly speaking). You do all output and data input within your program interface and you pass the data to your application for handling. This makes your code maintainable and easier to read (and much easier to follow the logic)

You don't bury prompts for data down inside your addnode() function. Instead you get the data to add within the initial part of main() or within your switch() statement and you pass an integer value to addnode(). Example:

    node *addNode (int n)   /* choose meaningful return to indicase success/failure */
    {
        // int item;
        // cout << "Enter data for node : ";  /* don't mix interface & application */
        // cin >> item;
        node *temp = new node();
        
        temp->data = n;
        temp->next = NULL;
        
        if (head == NULL)
            head = tail = temp;
        else {
            tail->next = temp;
            tail = temp;
        }
        
        return temp;        /* return pointer to allcated node */
    }

Then:

    /** this is interface, input/output happens here */
    std::cout << "List is not created yet, please add data to create the list.\n";
    do
    {
        int n;
        if (!(std::cin >> n)) {
            std::cerr << "error: invalid integer input.\n";
            return 1;
        }
        
        if (!l1.addNode (n)) {
            std::cerr << "error: adding node.\n";
            return 1;
        }
        
        std::cout << "Node added. Want to add another node (y/n) : ";
        if (!(std::cin >> choice)) {
            std::cerr << "error: invalid integer input.\n";
            return 1;
        }
    } while (choice == 'y' || choice == 'Y');

(and similarly for your menu within your switch() statement)

You Validate EVERY User-Input

You cannot use any input function correctly unless you check the return. (technically you check the stream state). You do that by checking that EVERY input succeeds or you handle the error. Never cin >> data; and hope data is good. For example (minimally):

                    int n;
                    std::cout << "Enter data for node : ";
                    if (!(std::cin >> n)) {
                        std::cerr << "error: invalid integer input.\n";
                        break;   /* note: this just lets the menu fail before clearing error */
                    }
                    if (l1.insertAtBegining (n)) {
                        std::cout << "Inserted Successfully. Updated list is : \n";
                        l1.display();
                    }
                    break;

With any input using iostream, you must .clear() the stream state before further input can take place and you must empty the contents from the input buffer that caused the error. A more full example is:

        while (!(std::cin >> menuChoice)) {     /* you need to handle error here */
            std::cerr << "error: invalid integer input.\n";
            std::cin.clear();
            std::cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');
            std::cout << "\nchoice: ";
        }

See std::basic_istream::ignore and bookmark the cppreference.com link -- it is your best reference on the internet -- use it.

(you should update the rest of your code to handle the input correctly)

Don't Iterate Using head

Your head pointer points to the node at the beginning of your list. Do NOT use it to iterate over your list. (when you are done -- it no longer points to the beginning of the list and you have lost the pointer to the beginning). Instead, you declare a temporary pointer to iterate with, e.g.:

    void display ()
    {
        int i = 1;
        node *iter = head;
        while (iter != NULL)
        {
            std::cout << "Node " << i << " : " << iter->data << '\n';
            iter = iter->next;
            i++;
        }
    }

Don't get in the habit of using namespace std; See: Why is “using namespace std;” considered bad practice?. While you are at it, have a look at C++: “std::endl” vs “\n”.

Insert At Mid

When you insert at in the middle of the list, you must either naively keep track of the prev and current nodes so you can insert your node so that prev->next = node_to_insert; and node_to_insert->next = current;. Or, you can use pointers correctly iterating both with the address-of-the-node and pointer-to-node so that you can simply replace the contents at the address of the node with the node_to_insert and have node_to_insert->next equal to the pointer-to-node->next. See Linus on Understanding Pointers

If you do it that way, it makes things much eassier. Your insertAtMid() function becomes:

    node *insertAtMid (int n)
    {
        int length=0, middle;
        node *iter = head,
            **iteradr = &head;
        
        while (iter != NULL) {
           length++;
           iter = iter->next;
        }
        
        middle = length/2;
        iter = head;
        
        while (middle--)
        {
            iteradr = &iter->next;
            iter = iter->next;
        }
        
        // cout << "Enter data you want to insert : ";      /* mixing */
        // cin >> n;
        
        node *temp = new node();
        temp->data = n;
        
        if (!head)
            head = tail = temp;
        else {
            *iteradr = temp;
            temp->next = iter;
        }
        
        //cout << "Inserted Successfully. Updated list is : "<<endl;    /* mixing */
        
        return temp;
    }

Putting it altogether, and making many more (slight) changes and fixing your "mixing application and interface" problem, you could do:

#include <iostream>
#include <limits>

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

class linkedList
{
  private:
    node *head, *tail;

  public:
    linkedList()
    {
        head = NULL;
        tail = NULL;
    }
    
    node *addNode (int n)   /* choose meaningful return to indicase success/failure */
    {
        // int item;
        // cout << "Enter data for node : ";  /* don't mix interface & application */
        // cin >> item;
        node *temp = new node();
        
        temp->data = n;
        temp->next = NULL;
        
        if (head == NULL)
            head = tail = temp;
        else {
            tail->next = temp;
            tail = temp;
        }
        
        return temp;        /* return pointer to allcated node */
    }
    
    node *getHead()
    {
        return head;
    }
    
    void display ()
    {
        int i = 1;
        node *iter = head;
        while (iter != NULL)
        {
            std::cout << "Node " << i << " : " << iter->data << '\n';
            iter = iter->next;
            i++;
        }
    }
    
    node *insertAtBegining (int n)
    {
        // cout << "Enter data you want to insert : ";      /* don't mix */
        // cin >> n;
        node *temp = new node();
        temp->data = n;
        temp->next = head;
        head = temp;
        // cout << "Inserted Successfully. Updated list is : "<<endl;
        
        return temp;
    }
    
    node *insertAtMid (int n)
    {
        int length=0, middle;
        node *iter = head,
            **iteradr = &head;
        
        while (iter != NULL) {
           length++;
           iter = iter->next;
        }
        
        middle = length/2;
        iter = head;
        
        while (middle--)
        {
            iteradr = &iter->next;
            iter = iter->next;
        }
        
        // cout << "Enter data you want to insert : ";      /* mixing */
        // cin >> n;
        
        node *temp = new node();
        temp->data = n;
        
        if (!head)
            head = tail = temp;
        else {
            *iteradr = temp;
            temp->next = iter;
        }
        
        //cout << "Inserted Successfully. Updated list is : "<<endl;    /* mixing */
        
        return temp;
    }
};

int main (void)
{
    linkedList l1;
    char choice;
    int menuChoice;
    
    /** this is interface, input/output happens here */
    std::cout << "List is not created yet, please add data to create the list.\n";
    do
    {
        int n;
        if (!(std::cin >> n)) {
            std::cerr << "error: invalid integer input.\n";
            return 1;
        }
        
        if (!l1.addNode (n)) {
            std::cerr << "error: adding node.\n";
            return 1;
        }
        
        std::cout << "Node added. Want to add another node (y/n) : ";
        if (!(std::cin >> choice)) {
            std::cerr << "error: invalid integer input.\n";
            return 1;
        }
    } while (choice == 'y' || choice == 'Y');
    
    std::cout << "List created successfully. Select from options below : \n";
    
    for (;;) {  /* loop continually */
        std::cout << "\n  1. Display list\n  2. Insert at Begining\n"
                    "  3. Insert at Mid\n  4. Insert at End\n  5. exit\n\n"
                    "choice: ";
        
        while (!(std::cin >> menuChoice)) {     /* you need to handle error here */
            std::cerr << "error: invalid integer input.\n";
            std::cin.clear();
            std::cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');
            std::cout << "\nchoice: ";
        }
        
        switch(menuChoice)
        {
            case 1:
                l1.display();
                break;
            case 2: {
                    int n;
                    std::cout << "Enter data for node : ";
                    if (!(std::cin >> n)) {
                        std::cerr << "error: invalid integer input.\n";
                        break;
                    }
                    if (l1.insertAtBegining (n)) {
                        std::cout << "Inserted Successfully. Updated list is : \n";
                        l1.display();
                    }
                    break;
                }  
            case 3: {
                    int n;
                    std::cout << "Enter data for node : ";
                    if (!(std::cin >> n)) {
                        std::cerr << "error: invalid integer input.\n";
                        break;
                    }
                    if (l1.insertAtMid (n)) {
                        std::cout << "Inserted Successfully. Updated list is : \n";
                        l1.display();
                    }
                    break;
                }
            case 4: {
                    int n;
                    std::cout << "Enter data for node : ";
                    if (!(std::cin >> n)) {
                        std::cerr << "error: invalid integer input.\n";
                        break;
                    }
                    if (l1.addNode (n)) {
                        std::cout << "Inserted Successfully. Updated list is : \n";
                        l1.display();
                    }
                    break;
                }  
            case 5:
                return 0;
                break;
            default:
                std::cout << "Invalid selection...!!\n";
                break;
        }
    }
}

(note: you should add a destructor that frees the list memory for the times when you use a list in other than main())

And NEVER name a list l1 (ell, one). Do you have any idea how hard that is for old eye to catch?

Example Use/Output

$ ./bin/ll_class_menu
List is not created yet, please add data to create the list.
1
Node added. Want to add another node (y/n) : y
2
Node added. Want to add another node (y/n) : y
3
Node added. Want to add another node (y/n) : y
4
Node added. Want to add another node (y/n) : y
5
Node added. Want to add another node (y/n) : n
List created successfully. Select from options below :

  1. Display list
  2. Insert at Begining
  3. Insert at Mid
  4. Insert at End
  5. exit

choice: 1
Node 1 : 1
Node 2 : 2
Node 3 : 3
Node 4 : 4
Node 5 : 5

  1. Display list
  2. Insert at Begining
  3. Insert at Mid
  4. Insert at End
  5. exit

choice: 2
Enter data for node : 6
Inserted Successfully. Updated list is :
Node 1 : 6
Node 2 : 1
Node 3 : 2
Node 4 : 3
Node 5 : 4
Node 6 : 5

  1. Display list
  2. Insert at Begining
  3. Insert at Mid
  4. Insert at End
  5. exit

choice: 3
Enter data for node : 7
Inserted Successfully. Updated list is :
Node 1 : 6
Node 2 : 1
Node 3 : 2
Node 4 : 7
Node 5 : 3
Node 6 : 4
Node 7 : 5

  1. Display list
  2. Insert at Begining
  3. Insert at Mid
  4. Insert at End
  5. exit

choice: 4
Enter data for node : 8
Inserted Successfully. Updated list is :
Node 1 : 6
Node 2 : 1
Node 3 : 2
Node 4 : 7
Node 5 : 3
Node 6 : 4
Node 7 : 5
Node 8 : 8

  1. Display list
  2. Insert at Begining
  3. Insert at Mid
  4. Insert at End
  5. exit

choice: 5

There is a lot here, so go though it slowly. Make sure you understand the changes and why they were made. Let me know if you have further questions.

Answer 2

According to your instance of code, you are counting the number of nodes and you are moving the head pointer till the end of the list.

Before the below statement gets executed, the head will be at currently pointing the last node.

while((middle --) > 1)
        {
            head = head->next;
        }

As soon as this statement head = head->next; gets executed, then head will point to nowhere, or you could say, its pointing to NULL. That is the reason you are getting an segmentation error, cause head->next tries to give a reference to an address, which is an garbage. Nothing exists there.

Instead using head to iterate, use a temporary node, assign it to head and then count the length of the list.

   node *tmp = new node();
   tmp = head;
   int length = 0;
   while(tmp != NULL){
       length++;
       tmp = tmp->next;
   }

   middle = ((length % 2) == 0) ? (length /2 ) : (length + 1)/2);
   tmp = head;
   while((middle --) > 1){
        tmp = tmp->next;
   }
 
   cout << "Enter data you want to insert : ";
   cin >> n;
   node *curr = new node();
   curr->data = n;
   curr->next = temp->next;
   temp->next = curr;

I would suggest you not to use the head pointer, for iterating, as it may lead to dangling reference.