Linked List

[sudhirs18]

Hi,

I'm new to c++. My program below uses a linked list to add / remove / display / query data of type string.

Issue faced:

There is no problem with the program and it executes as desired.

However, if multiple data elements are to be used - as opposed to just the string type - say add data element roll_number of type int to the existing 'class Node', how do i go about it?

Could any of the expert(s) please have a look at the code and suggest modifications (with code wherever required). Would be of much help.

Many thanks,
Sudhir

//compiler used Dev c++ 4.9.9.2

#include<iostream>
#include<fstream>
#include<string.h>
#include<conio.h>
using namespace std;
//program implementing linked list for insertion, deletion, search & traversal of data

class Node
   {
     public:
     string name;
     
     Node *next;
     
     //the default initialization of the 'next' pointer to NULL
     Node(const string &s, Node *n = '\0'): name(s), next(n)//constructor of node
      {
       name = s;//the name is initialized by a user supplied string
       
       next = n;//initializes the next field of new node to START
      }
   };

class List
   {
     Node *START;//pointer variable pointing to first node in the list
     Node *CURRENT;/*used by queryNode() and delNode(). Pointer to 
                     current node*/
     Node *PRECEDE;//--ditto--. Pointer to the node just before the current node
     
     public: 
     List()
       {
         //memeber pointers of class List initialized to NULL
         START = '\0';
         CURRENT = '\0';
         PRECEDE = '\0';
       }

     void addNode(const string &s)
       {

         //if list does not exist or string to be added at the START
         if((START == '\0')||(s <= START -> name))
           {
          
         /*constructor for node updates 'next' to either NULL or to START depending 
           on the state of the list (empty / existing)*/
             START = new Node(s,START);
             return;//no other steps need to be performed

           }
         Node *previous, *current;/*pointers declared local to addNode()
          if the list has existing nodes, the pointers previous and current to 
          be psoitioned on required nodes*/

         for(previous = current = START; current != '\0' && s >= current -> name; 
         previous = current, current = current -> next)
           {
             if(s == current -> name)
               {
                 cout<<"\nDuplicate names not allowed\n";
                 return;
               }
           }
         Node *n = new Node(s,current);//next field of new node points to current 
                                        node
         previous -> next = n;//next field of previous node points to new node 
                                represented by 'n'
       }

     void traverse()//displays contents(data) of the nodes
       {

         for(Node *temp = START; temp != '\0'; temp = temp -> next)
           {

             cout<<temp -> name<<endl;

           }

       }

     bool queryNode(const string &s)//search for a given data (string in this case)                     
                                     in the list
     /*the pointer 'CURRENT' is positioned at the node that contains the name, 
       which matches the user supplied string. the pointer 'PRECEDE' is positioned 
       at the node just before the node pointed to by CURRENT*/
       {

         for(PRECEDE = CURRENT = START; CURRENT && s != CURRENT -> name; 
             PRECEDE = CURRENT, CURRENT = CURRENT -> next)
         //pointers initially initialized to START
         //both conditions to evaluate to False, return True (display string) else 
           vice-versa 
         /*if conditions evaluate to True, move PRECEDE to node pointed by CURRENT 
           And CURRENT to the next node in sequence, to match and display string 
           searched for*/
           {

             cout<<CURRENT -> name<<endl;

           }  
         /*after exiting loop, if pointer CURRENT contains NULL then entire list 
           Traversed and reached end of list without finding the string 
           specified*/         
         return(CURRENT != '\0');//returns True if string is found in the list

       }

     bool delNode(const string &s)//search a given string and delete from the list
       {

         if(queryNode(s) == false)/*use queryNode function to check whether user 
         supplied string is present in any of the nodes in the list*/
           { 

             return false;//nothing else needs to be done

           }
           /*if last statement of queryNode() returns true, the pointer CURRENT 
             is positioned at the the node (found at middle or end of list) to 
             be deleted and the pointer PRECEDE positioned at the node that is 
             just before the node pointed by CURRENT.*/
         PRECEDE -> next = CURRENT -> next;//logical delinking of node from list 
          (logical deletion)
         if(CURRENT == START)/*if node to be deleted is found at beginning of list 
         i.e if pointer CURRENT points to the first node represented by START, 
         reposition START*/
           {

             START = START -> next;//pointer START moved to the next node in  
             sequence

           }
         delete CURRENT;//free memory allocated to current node for deletion 
         (physical deletion)
         return true;//if user supplied string present in the list

       }
   };

int main()
   {
     List obj;
     char ch;
     while(1)//loop condition always true
       {
         cout<<endl<<"1. Enter customer name"<<endl;
         cout<<"2. Display the names of all customers"<<endl;
         cout<<"3. Search for a customer"<<endl;
         cout<<"4. Delete a customer name"<<endl;
         cout<<"5. Exit"<<endl;
         cout<<"Enter choice(1 / 2 / 3 / 4 or 5)"<<endl;
         cin>>ch;
         switch(ch)
           {
             case '1':
               {
                 cout<<endl<<"Enter a name"<<endl;
                 string s;
                 cin.ignore();
                 getline(cin,s);
                 obj.addNode(s);
               }
               break;
             case '2':
                  obj.traverse();
                  break;
             case '3':
               {
                 cout<<endl<<"Enter a name"<<endl;
                 string s;
                 cin.ignore();
                 getline(cin,s);
                 if(obj.queryNode(s) == false)
                   {
                     cout<<"Customer "<<s<<" not found in list"<<endl;
                   }
                 else
                   {

                     cout<<"Customer "<<s<<" found in list"<<endl;
                   }
               }
               break;
             case '4':
               {
                 cout<<endl<<"Enter a name"<<endl;
                 string s;
                 cin.ignore();
                 getline(cin,s);
                 if(obj.delNode(s)== false)
                    {
                      cout<<"Customer "<<s<<" not found. Deletion not 
                      possible!"<<endl;
                    }
                 else
                    {
                      cout<<"Customer "<<s<<" found and deleted!!. Confirm by  
                      entering 2"<<endl;
                    }
               }
               break;
             case '5':
                  exit(0);
                  break;
             default:
                  cout<<endl<<"Enter a correct choice(between 1-5)";
           }      
       }   
     getch();
     return 0;
   }
     

[hamsterman]

Just add it to node class and to it's constructor. That should be all. Or were you asking about templates?

By the way, using '\0' instead of 0 or NULL is really weird..

[sudhirs18]

Thanks for your reply.

Yes, it should be 0 or NULL.....sorry about that :)

Just add it to node class and to it's constructor. That should be all.

1. What about the functions addNode(), queryNode() and delNode(). Should the roll_number be added as type int to the existing String parameter? [at the time of function declaration and calling from main()]

2. Should it be extended to the if conditions and for loops within the functions like say,

void addNode(int rollnum, const string &s)
       {

         //if list does not exist or string to be added at the START
         if((START == '\0')||(s <= START -> name && rollnum <= START -> roll_number))
           {
          
         /*constructor for node updates 'next' to either NULL or to START depending 
           on the state of the list (empty / existing)*/
             START = new Node(rollnum, s,START);
             return;//no other steps need to be performed

           }

Could you pls clarify the above.

[hamsterman]

whoops. didn't notice your list was sorted.
you're right. roll_number should be added everywhere name is used.
note though that s <= START -> name && rollnum <= START -> roll_number isn't good. will ["a", 10] go before ["b", 5] or after it? either way this line will return 0.
a thing that could help you understand would be a NodeData class, which would contain the string and the integer. it would also have it's operators < and ==. then write a list of nodes that contain NodeData objects without thinking about their contents (pretty much just replace "string" with "NodeData").