double linked list and its deletion

Question

i wrote the following code to delete the nodes at the beginning and at the end of a doubly linked list....but the execution of these functions stopped in between and the program was aborted......

struct nodeb
{
    int value;
    nodeb *next;
    nodeb *pre;   //pre of first node and next of last node point to null...
    nodeb(int a,nodeb *ptr1=0, nodeb *ptr2=0):value(a), next(ptr1), pre(ptr2)
    {}
};

class doublelist
{
private:

nodeb *head1,*head2;

public:

doublelist():head1(0),head2(0)
  {cout<<"double list created"<<endl;}


void deletebeg()//delete beginning node
{
    if(head1->next==0)
    {
        nodeb *ptr=head1;
        head1=head2=0;
        delete ptr;
    }
    else 
    {
        nodeb *ptr=head1->next;
        nodeb *ptr1=head1;
        ptr->pre=0;
        head1=ptr;
        delete ptr1;
    }
}


void deleteend()//delete end node
{
    nodeb *ptr=head1;
    nodeb *ptr1;
    while(ptr->next!=0)
    {
        ptr1=ptr;
        ptr=ptr->next;
    } 

    delete ptr;
    ptr1->next=0;
}
};  //class ends here


int main()
{
    doublelist list1;
nodeb node(8);
nodeb node1(7);
nodeb node2(9);
nodeb node3(4);
list1.insertbeg(node);
list1.insertbeg(node1);
    list1.insertafter(node3,1);
list1.insertend(node2);  //insertbeg,insertafter and insertend are three functions i defined to        attach nodes at the beginning,at a particular location and at  the end of the list 
list1.deletebeg();
} 

can anyone please tell me the problem??this is the link to the three functions for insertions

Answer 1

Now I can see all the code the problem is very simple. Your deletebeg function is deleting the beginning node with delete, but you didn't allocate the node with new. You should only delete memory if you created it using new.

Normally when people write linked list classes they allocate the nodes inside the list methods using new. Then they can safely delete the nodes inside the methods. You are doing the deletes but you are not using new. So you need to rewrite your main function like this

int main()
{
    doublelist list1;
    list1.insertbeg(8); // add 8 to beginning of list
    list1.insertbeg(7); // add 7 to beginning of list
    list1.insertafter(4,1); // add 4 after first item of list
    list1.insertend(9); // add 9 to end of list
    list1.deletebeg();
} 

Then you need to rewrite your methods like this

void insertbeg(int value)//insert beginning
{
    nodeb* a = new nodeb(value); // allocate node inside of method using new
    if(head1==0)
    {
        head1=a;
        head2=a;
        a->next=0;
        a->pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=a;
        a->pre=0;
        a->next=ptr;
        head1=a;
    }
}

I've only shown insertbeg, you need to change all your insert methods in the same way.

I'm not promising that's the only problem, but make this change and you'll be on the right way. If you have more problems then post again, but remember post complete code. It's the only way you'll get help with problems like this.

Answer 2

I'm a little baffled by this code excerpt, but I'll assume this is the entire excerpt for this...

The functions deletebeg and deleteend aren't declared anywhere in the class definition, only after it. Normally, it would look something like:

class List{
    void aFunction(List * argument);
};  

void List::aFunction(List * argument){
    do something
};

But all that aside, do not make your own linked list, it is much faster and will make your life easier using std::list<int> (replacing int with whatever data type you are making a list for).

There are lots of reasons for this, but the main one is that you only don't have to write it, but you don't have to debug it either. The linked list implementation you created, for instance, uses a recursive function to delete itself (when a function calls itself, it's recursive). If the linked list is very large, this can cause a stack overflow, caused by calling too many functions within functions. It's things like this that are a nightmare to track down and find, and distract you from the real reason you are programming. That is assuming that reason isn't making a linked list. :P

Answer 3

While it isn't usual to see functions declared outside a class in C++, it isn't impossible. But that would mean that head1 is a global variable somewhere that isn't shown.

You left out the part of that is actually calling deletebeg and deleteend so it is hard to tell exactly what is happening. Perhaps you are making use of a pointer after it has been deleted.

Also, while NULL is usually zero, there is no guarantee that is the case for your compiler. You should be using NULL instead of zero.

My guess is that you called deleteend with a node that for whatever reason had head1==0, then ptr1 was never initialized, and the program crashed on the last line of deleteend when you tried to dereference the uninitialized pointer.

Answer 4

Further to the comments on my previous answer

This code is wrong

void insertbeg(int value)//insert beginning
{
    nodeb a(value); // create node on the stack
    if(head1==0)
    {
        head1=&a;
        head2=&a;
        a.next=0;
        a.pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=&a;
        a.pre=0;
        a.next=ptr;
        head1=&a;
    }
}

The code above would have the problem you described, when you said 'head1 and head2 will point nowhere'. But this code is completely different

void insertbeg(int value)//insert beginning
{
    nodeb* a = new nodeb(value); // allocate node inside of method using new
    if(head1==0)
    {
        head1=a;
        head2=a;
        a->next=0;
        a->pre=0;
    }
    else
    {
        nodeb *ptr=head1;
        ptr->pre=a;
        a->pre=0;
        a->next=ptr;
        head1=a;
    }
}

It's different because it uses new to create the objects. When you use new the objects don't get destroyed when you exit the function. That's what new means. But when you do use new you also have to use delete when you have finished with the nodes.