Linked List segmentation fault, class

Question

Wrote this program in Cpp for Linked Lists. I am getting an error in insert when trying to insert at the front of the linked list as a segmentation fault. I couldn't print the list with list.printList(), but if I use push_back() and then printList(), it works fine. Spent a lot of time pondering but couldn't figure out? Please help me!

#include<iostream>

using namespace std;

class Node {
    private:
        int data;
        Node* next;
    public:
        Node() {
            data = 0;
            next = NULL;
        }

        void setData(int data) {
            this->data = data;
        }

        int getData() {
            return data;
        }

        void setNextNode(Node* node) {
            this->next = node;
        }

        Node* getNextNode() {
            return next;
        }
};

class LinkedList {
    private:
        Node Head_node;
    public:
        void createList(int n) {
            int x;
            cin >> x;
            Head_node.setData(x);
            n--;
            while (n) {
                cin >> x;
                push_back(x);
                n--;
            }
        }
        
        Node* lastNode() {
            Node* temp = &Head_node;
            while ( (*temp).getNextNode() != NULL)  //while is not last node
            {
                temp = (*temp).getNextNode();
            }
            return temp;
        }

        void push_back(int x) {
            Node* temp = lastNode();    //move to last node
            Node* a = new Node;         // create a new node
            (*temp).setNextNode(a);     //link new node to list
            (*a).setData(x);            //set new node data
        }

        void push_front(int x) {
            Node* a = new Node;
            (*a).setData(x);
            
            Node join = Head_node;
            (*a).setNextNode(&join);
            this->Head_node = (*a);
        }

        void printList() {
            Node* temp = &Head_node;
            do {
                cout << (*temp).getData() << " ";
                temp = (*temp).getNextNode();
            } while (temp != NULL);
        }
};

int main() {
    int n;
    cin >> n;
    LinkedList list;
    list.createList(n);
    list.push_front(29);
    list.printList();
    return 0;
}

I ran code and it said "segmentation fault" But if I run list.push_back(29); list.printList(); instead, everything is still fine!

You're interchanging pointers and scalars, seemingly at random. Do you understand the difference between `Node` and `Node*`? Because the code you've shown indicates that you think they're equivalent. — Silvio Mayolo, Aug 10 '22 at 04:17
Meant to say join probably _shouldnt_ be a local variable. Returning the address of something on the stack is a recipe for a crash. You should run your code through sanitizers. — Taekahn, Aug 10 '22 at 04:24
Have you ran this in a debugger yet? This seems a good time to start using one, step through your code one line at a time until it crashes. That is where your bug will be. Also the recommendation in C++ is not to use new/delete, but to use std::make_unique to avoid memory leaks. — Pepijn Kramer, Aug 10 '22 at 04:25
Your Node class has sham encapsulation. Just leave the data members public and remove all the getters and setters. You don't need them. — n. m. could be an AI, Aug 10 '22 at 05:16
You cannot distinguish an empty linked list from a linked list with one element. That's because you have `Node Head_node;`. That's a mistake. You should have `Node *Head_node;` and change *everything* accordingly. — n. m. could be an AI, Aug 10 '22 at 05:23
Please use *idiomatic* `x->y` notation instead of `(*x).y`, the latter means exactly the same but is harder to type, harder to read, and may earn you a "thank you we will (never) call you back" at a job interview. — n. m. could be an AI, Aug 10 '22 at 05:27
@PepijnKramer a unique_ptr in a linked list is a very bad idea. — n. m. could be an AI, Aug 10 '22 at 05:27
@n.1.8e9-where's-my-sharem. There is also a common implementation approach, where the list indeed contains a head node. Instead of testing for NULL in the last real node, you test if it is the head node. And instead of setting Node->next to NULL, you set it to &headNode. Of course, an empty list is then headNode.next == &headNode. That approach is probably more common for double linked listes, though. — BitTickler, Aug 10 '22 at 05:27
@BitTickler Crawl before you run before you fly. This approach should be learned when enough fluency in pointer manipulation is achieved, otherwise it's *premature optimisation*. — n. m. could be an AI, Aug 10 '22 at 05:31
Thank you very much for all your help! I understood the problem. I'm a newbie, so I really appreciate to your help! — thanguyen165, Aug 10 '22 at 08:37

score 1 · Accepted Answer · answered Aug 10 '22 at 05:13

The root cause of the segmentation violation lies in the following lines:

Node join = Head_node;
(*a).setNextNode(&join);
this->Head_node = (*a);

You are storing the address of the function local variable join in the linked list. When the function returns, the pointer becomes a dangling pointer. Accessing that pointer causes undefined behavior. In your case, that manifests as segmentation violation.

One way to resolve the problem will be:

Create a new Node that stores the data of Head_node.
Change the data of Head_node to store the new data.
Make sure that the "next" pointers are adjusted accordingly.

The following updated version of the function works for me.

void push_front(int x) {
    Node* headCopy = new Node;
    headCopy->setData(Head_node.getData());
    headCopy->setNextNode(Head_node.getNextNode());

    Head_node.setNextNode(headCopy);
    Head_node.setData(x);
}

Thank you very much! I understood the problem. I'm a newbie, so I really appreciate to your help! — thanguyen165, Aug 10 '22 at 08:09

Linked List segmentation fault, class

1 Answers1