"Segmentation fault" in doubly-linked list implementation

help
, ,
#1

#include

using namespace std;

struct Node
{
int data;
Node* next;
Node* prev;
};

class doublylinkedlist
{
Node *head,*tail,*p;
public:
doublylinkedlist()
{
head=NULL;
tail=NULL;
}
void pushb(int n)
{

    Node* obj=new Node;
    obj->data=n;
    if(head==NULL)
    {
        head=obj;
        head->next=NULL;
        head->prev=NULL;
        tail=head;
    }
    else
    {
        tail->next=obj;
        obj->prev=tail;
        obj->next=NULL;
        tail=obj;
    }
}
void pushf(int n)
{
    Node *obj=new Node;
    obj->data=n;
    if(head==NULL)
    {
        head=obj;
        head->next=NULL;
        head->prev=NULL;
        tail=head;
    }
    else
    {
        obj->next=head;
        obj->prev=NULL;
        head=obj;
    }
}
void popb()
{
    
    
    if(head==NULL)
    {
        cout<<"Empty\n";
    }
    
    else
    {
        p=tail;
        tail=tail->prev;
        tail->next=NULL;
        p->next=NULL;
        p->prev=NULL;
        free(p);
    }
}
void print()
{
    if(head==NULL)
    {
        cout<<"Empty\n";
    }
    else
    {
        p=head;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<"\n";
    }
}

};

int main()
{
doublylinkedlist a;
a.pushf(0);
a.pushb(1);
a.pushf(-1);
a.pushb(2);
a.popb();
a.print();
a.popb();
a.print();
a.popb();//segmentation fault is due to this
a.print();
return 0;
}

These are my push back and pop back functions. Push back is working perfectly. Pop back also works good till there are 2 elements remaining. When I perform pop on 2 elements I get segmentation fault. Can anyone please help me with it?

#2

Please post the entirety of your code, formatted, plus whatever test inputs are causing the problem.

2 Likes
#3

ok sir!

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;
    Node* prev;
};

class doublylinkedlist
{
    Node *head,*tail,*p;
    public:
    doublylinkedlist()
    {
        head=NULL;
        tail=NULL;
    }
    void pushb(int n)
    {
        
        Node* obj=new Node;
        obj->data=n;
        if(head==NULL)
        {
            head=obj;
            head->next=NULL;
            head->prev=NULL;
            tail=head;
        }
        else
        {
            tail->next=obj;
            obj->prev=tail;
            obj->next=NULL;
            tail=obj;
        }
    }
    void pushf(int n)
    {
        a++;
        Node *obj=new Node;
        obj->data=n;
        if(head==NULL)
        {
            head=obj;
            head->next=NULL;
            head->prev=NULL;
            tail=head;
        }
        else
        {
            obj->next=head;
            obj->prev=NULL;
            head=obj;
        }
    }
    void popb()
    {
        
        
        if(head==NULL)
        {
            cout<<"Empty\n";
        }
        
        else
        {
            p=tail;
            tail=tail->prev;
            tail->next=NULL;
            p->next=NULL;
            p->prev=NULL;
            free(p);
        }
    }
    void print()
    {
        if(head==NULL)
        {
            cout<<"Empty\n";
        }
        else
        {
            p=head;
            while(p!=NULL)
            {
                cout<<p->data<<" ";
                p=p->next;
            }
            cout<<"\n";
        }
    }
    
};

int main()
{
    doublylinkedlist a;
    a.pushf(0);
    a.pushb(1);
    a.pushf(-1);
    a.pushb(2);
    a.popb();
    a.print();
    a.popb();
    a.print();
    a.popb();//segmentation fault is due to this
    a.print();
    return 0;
}
1 Like
#4

This doesn’t compile:

[simon@simon-laptop][10:26:59]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling amitpurohit47-blah.cpp
amitpurohit47-blah.cpp: In member function ‘void doublylinkedlist::pushf(int)’:
amitpurohit47-blah.cpp:43:9: error: ‘a’ was not declared in this scope
         a++;
         ^
Failed!!!!!

Please post your actual code.

2 Likes
#5

Sorry sir for the incorrect code!!

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;
    Node* prev;
};

class doublylinkedlist
{
    Node *head,*tail,*p;
    public:
    doublylinkedlist()
    {
        head=NULL;
        tail=NULL;
    }
    void pushb(int n)
    {
        
        Node* obj=new Node;
        obj->data=n;
        if(head==NULL)
        {
            head=obj;
            head->next=NULL;
            head->prev=NULL;
            tail=head;
        }
        else
        {
            tail->next=obj;
            obj->prev=tail;
            obj->next=NULL;
            tail=obj;
        }
    }
    void pushf(int n)
    {
        Node *obj=new Node;
        obj->data=n;
        if(head==NULL)
        {
            head=obj;
            head->next=NULL;
            head->prev=NULL;
            tail=head;
        }
        else
        {
            obj->next=head;
            obj->prev=NULL;
            head=obj;
        }
    }
    void popb()
    {
        
        
        if(head==NULL)
        {
            cout<<"Empty\n";
        }
        
        else
        {
            p=tail;
            tail=tail->prev;
            tail->next=NULL;
            p->next=NULL;
            p->prev=NULL;
            free(p);
        }
    }
    void print()
    {
        if(head==NULL)
        {
            cout<<"Empty\n";
        }
        else
        {
            p=head;
            while(p!=NULL)
            {
                cout<<p->data<<" ";
                p=p->next;
            }
            cout<<"\n";
        }
    }
    
};

int main()
{
    doublylinkedlist a;
    a.pushf(0);
    a.pushb(1);
    a.pushf(-1);
    a.pushb(2);
    a.popb();
    a.print();
    a.popb();
    a.print();
    a.popb();//segmentation fault is due to this
    a.print();
    return 0;
}
#6

The RE is because in pushf, you haven’t done head->prev = obj.

The other mistake is in popb. There is no guarentee tail->prev is not NULL. So doing tail->next=NULL may result in RE.

3 Likes
#7

Thank you very much Sir for the help!! It really worked