Inserting node into Doubly Linked List

Question

I am wanting to insert a newnode that will contain a name into the correct position of the Doubly Linked List. Basically an Insertion sort is what I want to achieve here.

This is the code for the insert function however there is problems:

• It breaks the Doubly Linked List if you insert a node with the same value more than once!
• It is not properly sorting the list.

Here is the code for the class:

class Doubly
{
private:
        struct node
           {
              string name; //stores name
              node* next; //points to next node
              node* prev; //points to previous node
           };

           node* head; //points to the first node in the list
           node* last; //points to the last node in the list

        public:

            Doubly(); //cstrctr
            ~Doubly(); //dstrctr

       bool empty() const { return head==NULL; }
       void insert(const string& );
       void remove(const string& );
       void print(ostream& OutStream) const;
       void sort (bool);
};

Here is the code for insert:

void Doubly::insert (const string& input)
{
    // Insertion into an Empty List.

if(empty()) //create a new list with one node = Head/Null
    {

       node* name = new node;
       head = name;
       last = name;
       name -> prev = NULL;
       name -> next = NULL;
       name -> name = input; //

    }

    //Insertion into a populated list
else
    {
        node* newnode;
        newnode = head;

        while (input > newnode -> name && newnode -> next != last -> next)
                        newnode = newnode -> next;

            if (newnode == head)
                {
                     node* name = new node;
                     name -> name = input;
                     name -> prev = newnode;
                     name -> next = NULL;
                     head -> next = name;
                     last = name;
                }

           else
           {
               if (newnode == last && input > last -> name) //Add the name to the end of the linked list
                   {
                         last -> next = new node;
                         (last -> next) -> prev = last;
                         last = last -> next;
                         last -> next = NULL;
                         last -> name = input;  
                   }
               else
                   {
                     node* name = new node;
                     name -> name = input;
                     name -> next = newnode;
                     (newnode -> prev) -> next = name;
                     name -> prev = newnode -> prev;
                     newnode -> prev = name;
                   }
          }
    }
}

Solution

I think the problem is when inserting at the head of the list, and you only have one element, the while (input > newnode -> name && newnode -> next != last -> next) can exit because of 2 reasons, and you are asuming that if the pointer is still at the head you have to insert it afterwards, but maybe it just went out of the while because there was only one element and you have to insert the new one before the head.

So you probably have to do something like:

   if (newnode->next == head->next) { 
        // Create the node and set the common values for all the cases 
        node* name = new node;
        name->name = input;
        if (input > newnode->name) { // Insert as second element
             name->prev = newnode;
             name->next = NULL;
             newnode->prev = NULL;
             newnodw->next = name;  
             head = newnode;
             last = name;                
        }
        else { // Insert as first element
             name->prev = NULL;
             name->next = newnode;
             newnode->prev = name;
             newnodw->next = NULL; 
             head = name;
             last = newnode;
        }

Comments

[sarnold]

It's harder than I expected to read newnode -> name; all those extra spaces are hard to get over. :)

[Jan Hudec]

One recommendation: Make the list head look enough like a list item and make the list circular. With empty list being a head pointing to itself with both "next" and "prev", you can always access "next" and "prev" of anything, so you'll have just one case instead of four, reducing the amount of code and thus possible places for mistake four times.

[Jan Hudec]

Another recommendation: Unless you are doing a homework (you should tag your question as such if you do), don't implement lists yourself. You tagged the question C++, so you have STL and if you need something special, can pull in boost. It's good to understand linked lists, but never write them yourself in practice.

[pmqtr]

Well I thought I would insert a new node into the correct position of the Doubly Linked List rather than do a seperate sort function later on to make sure all names are in Alphabetical order.

[Aki Suihkonen]

IMO, more people should be fluent in implementing all basic algorithms and data structures, do it in regular basis and do it well -- which points to another interesting thought: should homework be firmly connected to reality or be "just academic" exercises? (which is another common expression of the flawed practical/theoretical dichotomy.)

[tucuxi]

It is confusing to use "name" both for the "data" field of your list and for node pointers. Confusion leads to errors.

[tucuxi]

There is a lot of duplicate code in both branches of your if - you can make it more readable by refactoring.

[tucuxi]

Copying and pasting a lot of code without comments is generally frowned upon. It is a lot better to explain what the problem is in the original code.

[pconcepcion]

@tucuxi not a lot of code, but you are right, some refactoring to improve it was a good option