Why I am getting a segmentation fault here?

Question

I have really no idea why this is happening, I am accessing a member of class node. The node's next and prev values by default are NULL. The function where I am getting this error is Stack.push when the control comes to the line where memory new node is being allocated to the *node->next, it gives error.

// question: Implement stacks using linked lists
#include <iostream>
using namespace std;

class node
{
public:
    int data;
    node *next = NULL;
    node *prev = NULL;
};

class Stack
{
    // LIFO : LAST IN FIRST OUT
    node *top;

public:
    void push(int data)
    {
        top->next = new node; // here ,getting a segmentation fault while debugging :(
        top->next->prev = top;
        top = top->next;
        top->data = data;
    }

    int pop()
    {
        node *old_top = top;
        top = top->prev;
        delete old_top;
        return top->data;
    }

    friend void print_Stack(Stack *s);
};

void print_Stack(Stack *s)
{
    node* cur = s->top;

    while(cur->prev != NULL)
    {
        printf("%d<", cur->data);
        cur = cur->prev;
    }
    cout << cur->data << endl;

}

int main()
{
    /* code */
    Stack* S = new Stack;
    int i = 10;
    
    while (i--)
        S->push(i);

    print_Stack(S);
    return 0;
}

And when you fix that, your push() can't deal with an empty stack. And it has more problems too. — Avi Berger, Aug 03 '22 at 00:10
I'd suggest that you review how a stack works and then go though your code slowly, explaining it in detail to [R. Duck](https://en.wikipedia.org/wiki/Rubber_duck_debugging) — Avi Berger, Aug 03 '22 at 00:19
Well, immediately after you properly initialize `top` to `nullptr`, what do you think happens the first order of business, in `push()`, when it attempts to set `top->next`??? `push()`'s logic is completely broken. What you need to do is [explain every line of your program to your rubber duck](https://en.m.wikipedia.org/wiki/Rubber_duck_debugging). — Sam Varshavchik, Aug 03 '22 at 00:43
Regarding "other problems", the most obvious are: 1) Your class leaks memory (it does not implement a destructor that cleans up); 2) Does not follow the [Rule of Three](https://stackoverflow.com/q/4172722/1553090) and so copying a stack will result in undefined behavior; 3) Const-correctness: `print_Stack` function ought to operate on a `const Stack*` (or preferably a `const Stack&`; 4) Calling `pop` on an empty stack (or even a stack with 1 element) is undefined behavior, and you have no method to query the empty state; 5) `pop` returns the wrong data. 6) `pop` does not update `next` pointer. — paddy, Aug 03 '22 at 01:37
*"The node's `next` and `prev` values by default are `NULL`."* -- a default value is not relevant to code that overwrites the value. Looks like you might have been so focused on `next` that you did not see what came right before `next` in the problematic line. Don't let your focus blind you to other possibilities. — JaMiT, Aug 03 '22 at 02:24

score 0 · Accepted Answer · answered Aug 03 '22 at 03:36

A number of problems. People in the comments have mentioned top is uninitialized. That will fix some problems.

Here's your code:

void push(int data)
{
    top->next = new node; // here ,getting a segmentation fault while debugging :(
    top->next->prev = top;
    top = top->next;
    top->data = data;
}

The first time, top is either uninitialized (which you have to fix) or once fixed, is nullptr. But you don't check if it's nullptr. A better implementation:

 void push(int data) {
      node * newNode = new node;
      newNode->data = data;
      newNode->next = top;
      if (top != nullptr) {
          top->prev = newNode;
      }
      top = newNode;
 }

Now, let's look at pop:

int pop()
{
    node *old_top = top;
    top = top->prev;
    delete old_top;
    return top->data;
}

You don't check for old top being nullptr when this is called. Furthermore, is that the value you really want to return? Normally pop() would return the value on the top of the stack before popping it off.

Also, stacks grow upwards. Think not of top and bottom but of front and back. You push and pop at the front. But your code is doing it the other way around (sort of).

So if you push in order 5 7 4, top should normally point to the 4. Pop and top points to the seven, and pop again and it points to the 5.

So a better implementation of pop() --

int pop() {
    int rv = -1; // Or whatever your error return is going to be
    if (top != nullptr) {
        node * oldTop = top;
        rv = top->data;
        top = top->next;
        if (top != nullptr) {
             top->prev = nullptr;
        }
        delete oldTop;
    }
    return rv;
 }

Note that top can be null at the beginning. It can also become null, so you have to check that. And because your stack is bidirectional, you have to nullify the new top's prev pointer or you'll be pointing to data you've freed.

Note that my methods won't work with your printStack -- because I'm seeing stacks in the traditional fashion, so my pointers are opposite of yours. You're also not printing the top of the stack.

Why I am getting a segmentation fault here?

1 Answers1