appending or insertion at last in doubly linked list

Question

I am trying to insert a value at the end of a doubly linked list , I get successful in inserting the value at head or first node but the second value is not getting inserted

The issue here is while entering the second value

class d_list
{
private:

    struct node
    {
        double data;
        node *next;
        node *previous;
    };

    node *first;
    node *last ;
public:
    d_list(void)
    {
        first = nullptr;
        last = nullptr;
    };
    void append(double);

};

void d_list::append(double num)
{
    node *ptr;
    node *toinsert;
    if(!first)
    {
        first = new node;
        first->previous= nullptr;
        first->data = num;
        last= new node;
        first->next= last->previous;
        last->previous = first->next;
        last->next= nullptr;

    }
    else
    {
        if(last->next == nullptr)
        {
            ptr = new node;
            ptr->next =last->previous;
            ptr->data=num;
            last->previous = ptr->next  ;
        }


        last->next= nullptr;
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    d_list aa;
    cout<<"going to append first"<<endl;
    aa.append(44);
    cout<<"going to append second"<<endl;
    aa.append(50.5);

    return 0;
}

Answer 1

You have a number of problems in your code:

• Your node next and previous members are never initialized anywhere and as a result are undefined when used. Either add a constructor to node or ensure they are initialized after allocation.
• The addition of a node to an empty list is not correct. first->next is left undefined and why are you creating two nodes, both first and last? In a list with one element then first == last. The setting of next/previous in first/last doesn't make any sense either.
• In a well formed double-linked list then last->next should always be null, as should first->previous.
• The addition of a node into a non-empty list is also incorrect.
• While you don't show it in the example, you'll eventually need a destructor as well as a copy operator and copy constructor (the rule of three). At the moment you are leaking memory and if you try to delete nodes you'll likely result in a double-free and crash.

I would suggest taking a step back from the code for a bit to ensure you properly understand the concepts behind a doubly-linked list. Draw out a list on paper with next/prev arrows and see how they need to be changed when adding nodes to an empty/non-empty list as well as how to delete and move nodes around. Once you figure out how next/prev should be set then translating that into code should be relatively straight forward.

Edit to answer comment: To add a new node you can technically add it anywhere but it is usually added at the end (at least from what I've seen). See the other answers for a complete and correct code for adding new nodes in an empty and non-empty list.

Answer 2

...
if(last->next == nullptr)
{
  ptr = new node;
  ptr->next =last->previous; // <- is not correct
  ptr->data=num;
  last->previous = ptr->next  ; // <- does not do anything useful
  ...

You don't append your new node to the list.

...
if(!last->next)
{
  ptr = new node;
  ptr->previous=last->previous;
  ptr->next =last;
  ptr->data=num;
  last->previous = ptr  ;
  ...

should be better. By the way: delete the allocated memory in a destructor!

Answer 3

I would write your double linked list in following code:

    #include <iostream>
    using namespace std;
    class d_list
    {
    private:

        struct node
        {
            double data;
            node *next;
            node *previous;
        };

        node *first;
        // node *last ; no need for bidirectional list
    public:
        d_list(void)
        {
            first = nullptr;
            //last = nullptr;
        };
        void append(double);

    };

    void d_list::append(double num)
    {
        node *ptr = new node;
        ptr->data = num;
        node *toinsert;
        if(!first)
        {
            first = ptr;
            first->previous=first->next=first;
        }
        else
        {
            if(first->next == first)
            {
                ptr->next = ptr->previous = first;
                first->next = first->previous = ptr;
            }
            else{
                node *last = first->previous;
                ptr->next = first;
                ptr->previous = last;
                last->next = ptr;
                first->previous = ptr;
            }
        }
    }


    int _tmain(int argc, _TCHAR* argv[])
    {
        d_list aa;
        cout<<"going to append first"<<endl;
        aa.append(44);
        cout<<"going to append second"<<endl;
        aa.append(50.5);

        return 0;
    }

Answer 4

Why have you inserted the declarations node *ptr; and node *toinsert; if you don't use them? Also it should be obvious that if you insert a single node at the end, then only one new element should be created(and you call new twice if first is null).

Answer 5

Try this code...

class d_list 
{


private:
      struct node
      {
         double data;
         node *next;
         node *previous;
     };
      node *first;
     node *last ;

 public:
     d_list(void)
     {
         first = nullptr;
         last = nullptr;
     };

     void append(double);
  }; 

 void d_list::append(double num)
 {
     node *ptr;
     node *toinsert;
     if(!first)
     {
         first = last = new node;
         first->previous= nullptr;
         first->next = nullptr;
         first->data = num;
     }
     else
     {
             ptr = new node;
             ptr->next =last->previous;
             ptr->data=num;
             last->previous = ptr->next  ;
     }
  }


 int _tmain(int argc, _TCHAR* argv[])
 {
     d_list aa;
     cout<<"going to append first"<<endl;
     aa.append(44);
     cout<<"going to append second"<<endl;
     aa.append(50.5);
      return 0;
 }