Question

Working on a c++ data structures assignment.  

Linked List add node. I have the head case and the tail case working but the middle/general case I can not get to work for the life of me. I have included the header file and the data struct file below  

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include "data.h"

#include <iostream>   //take this out

using std::cout;

class LinkedList{

    public:

        LinkedList();

        ~LinkedList();

        bool addNode(int, string);

        bool deleteNode(int);

        bool getNode(int, Data*);

        void printList(bool = false);

        int getCount();

        void clearList();

        bool exists(int);

    private:

        Node *head;

};

#endif

----------------------------------------------------------------------------

#ifndef DATA_H

#define DATA_H

#include "string"

using std::string;

struct Data {

    int id;

    string data;

};

struct Node {

    Data data;

    Node *next;

    Node *prev;

};

#endif /* DATA_H */

---------------------------------------------------------------------------------------------------

bool LinkedList::addNode(int id, string data){

   bool success = false;

    Node *newNode = new Node;

    newNode -> data.id = id;

    newNode -> data.data = data;

    newNode -> next = NULL;

    newNode -> prev = NULL;

    Node *current;

    current = head;

    

     if(current == NULL && id > 0){                     

        head = newNode;                    

        success = true;

     }else if(newNode -> data.id <= current -> data.id && data != "" && id > 0 && id != current -> data.id){

        newNode -> next = current;

        newNode -> prev = NULL;

        head = newNode;

        success = true;

     }else {

         success = false;                 

     }

    

    while(current != NULL){

        if((current -> data.id < id) && data != "" && (current -> next == NULL)){            //tail case  

             current -> next = newNode;

             newNode -> prev = current;

             success = true;

         }else{

             current = current -> next;

         }  

    }

    while(current != NULL){

        if((current -> data.id < id) && (current -> prev -> data.id > id) && data != "" && (current -> next != NULL)){  //general or middle case

            cout << "test2" << std::endl;

            newNode -> next = current;  

            newNode -> prev -> next = newNode;

            current -> prev = newNode;

            success = true;

         }else{

             current = current -> next;

         }

    }

   return success;

}

Answer 1

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include "data.h"

#include <iostream>   //take this out

using std::cout;


class LinkedList{

    public:

        LinkedList();

        ~LinkedList();

        bool addNode(int, string);

        bool deleteNode(int);

        bool getNode(int, Data*);

        void printList(bool = false);

        int getCount();

        void clearList();

        bool exists(int);

    private:

        Node *head;


};



#endif

----------------------------------------------------------------------------

#ifndef DATA_H

#define DATA_H

#include "string"

using std::string;

struct Data {

    int id;

    string data;

};

struct Node {

    Data data;

    Node *next;

    Node *prev;

};

#endif /* DATA_H */

---------------------------------------------------------------------------------------------------

bool LinkedList::addNode(int id, string data){

   bool success = false;

    Node *newNode = new Node;

    newNode -> data.id = id;

    newNode -> data.data = data;

    newNode -> next = NULL;

    newNode -> prev = NULL;

    Node *current;

    current = head;

    

     if(current == NULL && id > 0){                     

        head = newNode;                    

        success = true;

     }else if(newNode -> data.id <= current -> data.id && data != "" && id > 0 && id != current -> data.id){

        newNode -> next = current;
        
        // Added to maintain the previous pointer of the current node
        current->prev = newNode;

        newNode -> prev = NULL;

        head = newNode;

        success = true;

     }else {

         success = false;                 

     }

    

    while(current != NULL){

        if((current -> data.id < id) && data != "" && (current -> next == NULL)){            //tail case  

             current -> next = newNode;

             newNode -> prev = current;

             success = true;

         }else{

             current = current -> next;

         }  

    }

    //Reset the current pointer
    current = head;
    
    if(data!="" && id>0)
    {
        while(current != NULL){
            
            //Check id is greater if yes then add the node to the next of current
            if(current -> data.id < id){  //general or middle case
    
                cout << "test2" << std::endl;
    
                //NewNode next is current next
                newNode-> next = current -> next;
            
                //NewNode Previous us current 
                newNode -> prev = current;
            
                //Current next is new node
                current -> next = newNode; 
                
                //If node added then making the flag as true
                success = true;
                
                //After adding the node ignores the iteration of the other nodes
                break;
    
             }else{
    
                 current = current -> next;
    
             }
        }
    }

   return success;

}

Updated the code for adding the nodes on middle of the link list and updated the code for adding the head node in order to maintain the previous pointer.