Splitting in a linked list class

[FloatingButter]

I'm trying to develop a program that stores a list of hw assignments in the form of "Date,Assignment name,grade". I have functions that add,remove, and delete from a list, but I would also like to search and delete a particular date found in the list. From here, split - Splitting a string in C++ - Stack Overflow I've tested Evan Teran's method to split a string, but I'm unsure of how to implement it in my code.

List.h

#ifndef LIST_H
#define    LIST_H
#include <string>
using namespace std;
class List{
private: 
    
   typedef struct node{
       string hw;
       string grade;
       string date;
     
       
        node* next;
        
        
    }* Node;
    
    
    Node head;
    Node current;
    Node temp;

    
public:    
    List();
    void AddAssign(string addData);
    void DeleteAssign(string delData);
    void PrintList();
      
    
};


#endif    /* LIST_H */

List.cpp

#include <cstdlib>
#include <iostream>
#include <string>
#include "List.h"
using namespace std;

List::List(){
    head = NULL;
    current = NULL;
    temp = NULL;
    
}

/*
 @function - addAssign
 * @pre - 
 * @post
 * @return - adds a list of elements to 
 * assignment list. 
 */
void List::AddAssign(string addData){
    Node n = new node;
    n->next = NULL;
    n->hw = addData;//initializes hw
    
    if(head != NULL){
        current = head;
        while(current->next != NULL){//next node is not at end of list
            current = current->next;//go to next node 
        }
        current->next = n;//next node is new
    }
    else{
        head = n;//newest node is head of list
    }
}

void List::DeleteAssign(string delData){
    Node delPtr = NULL;
    temp = head;
    current = head;
    while(current != NULL && current->hw != delData){
     temp = current;
     current = current->next;
        
        
        
    }
    
    if(current == NULL){
    cout << delData << " was not in the list\n";
    delete delPtr;
    
}else{
        delPtr = current;
        current = current->next;
        temp->next = current;
        if(delPtr == head){
            head = head->next;
            temp = NULL;
            
        }
        delete delPtr;
        cout << "The Value " << delData << " was deleted\n";
}
   
    
    
}

 void List::PrintList(){
        current = head;
        while(current!= NULL){//is not last node
            cout << current->hw << endl;
            current = current->next;
        }
                
    }

listmain.cpp

#include <cstdlib>
#include "List.h"
#include <string>
#include <iostream>
#include <list>
using namespace std;


int main(int argc, char** argv) {
    
    List assign;
    string date = "3/9/13";
    

    assign.AddAssign("3/4/13,Calculus,77");
    assign.AddAssign("3/7/13,Programming,88");
    assign.AddAssign("3/15/13,English,89");
    assign.AddAssign("3/23/13,Physics,78");
    
    cout<<"Starting list..." << endl; 
    assign.PrintList();
  
    
   
      
    return 0;
}

[FloatingButter]

Alright. I think I've figured out a way to implement Evan's split method into my code. I've create a method "search_and_remove" that takes each line of my list, splits it, and compares the date with the one I'm searching for, then removes that line in my list if found. The problem that I'm having is, I've placed it in this for loop and I'm unsure of what condition to break it from being infinite. I want each it to delete all occurances of a specific date in the list, so far it only deletes it if it is the first line in the list (and if the next one/s following it also contain that date).

With my cpp and h files all I did was add the following lines of
code to them, everything else looks the same as the code posted above. The only code I've posted up completely is my main file.

#ifndef LIST_H
#define    LIST_H
#include <string>
#include <vector>
#include <sstream>

  
   string splitData(const string &data, char delim);
   
   string &splitData(const string &data, char delim, vector<string> &elems) {
    stringstream ss(data);
   string item;
    while(getline(ss, item, delim)) {
        elems.push_back(item);
     
    }
   return elems[1];
   elems.clear();
}
};

List.cpp File:

 /*
  Searches the current date in the list and 
  * deletes the assignment from the list 
  * if found. Else prints  error message. 
  */
 
 void List::search_and_remove(string findData){
     

   current = head;
 //this loop prints the error message infinitely.
  for(current;current != NULL;current->next){
  string splitdata =  splitData(current->hw,',');
       if(splitdata == findData){
           DeleteAssign(current->hw);
       }else {
           cout << findData << " not found in list\n"; 
           
       }
  
   }
   
 }
 

 

  /*
   Takes a string and puts it in a vector.
   * Calls splitData to split the string.
   */
 string List::splitData(const string &data, char delim) {
    vector<string> elems;
   
    return   splitData(data, delim, elems);
}

#include <cstdlib>
#include "List.h"
#include <string>
#include <iostream>

using namespace std;


int main(int argc, char** argv) {
    


    List assign;    
  assign.AddAssign("Statistics,3/9/13,43");
   assign.AddAssign("Geometry,3/9/13,43");
  assign.AddAssign("Calculus,3/4/13,45");
     assign.AddAssign("Java,3/9/13,43");
     assign.AddAssign("Biology,3/6/13,55");
   
    
     cout << "Printing list... \n";
  
   assign.PrintList();
  
   assign.search_and_remove("3/9/13");
   cout << "Removes line with date 3/9/13\n";
   assign.PrintList();
 
     
 

  
      
    return 0;
}

[whiteflags]

I think you would have an easier time deleting nodes from the list if you had a search function. Write a function that returns a pointer to a node that matches the homework criteria. Then use that pointer to destroy the node. If it is null, then you know you've deleted all of the homework that matches (or that there was no match in the first place).

void List::deleteAllOf (const string& thisDate)
{
  while ( ( found = search(thisDate) ) != NULL ) {
    delete found;
  }
}

search() should be written so that a found node is separated from the list. It does not have to be public.

The whole split string thing kind of baffles me. That is something I would leave to client code and not build into a linked list class, but that is just my opinion.

[FloatingButter]

"found" is a node right?

I've modified my code a bit again, instead of the user entering one long string into addAssign, I've created three parameters to be initialized with the three string in struct node(name,date,grade). From here it makes searching for each date easier.

My function "SearchAssign" doesn't return the node found from the list but it returns a message with the found node in it. From there it calls "DeleteAssign" to delete the line from the node.

Although DeleteAssign does what I want it to do, I am curious as to why it deletes my entire line of assignment instead of just current->date since that is what is being called in "SearchAssign". Also how could a insert a new assignment at the location where I've deleted the searched date?I'm thinking that I would need to keep a counter each time I add a new assignment to the list and in my search function, or maybe in a new one, insert a new assignment at the number of the deleted assignment.

Here's my cpp file:

/* 
 * File:   main.cpp
 * Author: Jeremiah
 *
 * Created on March 3, 2013, 6:45 PM
 */

#include <cstdlib>
#include <iostream>
#include <string>
#include "List.h"
#include <vector>
#include <sstream>
#include <algorithm>
#include <iterator>

using namespace std;

List::List(){
    head = NULL;
    current = NULL;
    temp = NULL;
    
}

/*
 @function - addAssign
 * @pre - 
 * @post
 * @return - adds a list of elements to 
 * assignment list. 
 */
void List::AddAssign(string addDate,string addName,string addGrade){
    Node n = new node;
    n->next = NULL;
    n->date = addDate;
    n->name = addName;
    n->grade = addGrade;
  
    
    if(head != NULL){
        current = head;
        while(current->next != NULL){
            current = current->next;
        }
        current->next = n;
    }
    else{
        head = n;
    }
}
/*
 * Deletes each line of string.
 */
void List::DeleteAssign(string delData){
    Node delPtr = NULL;
    temp = head;
    current = head;
    while(current != NULL && current->date  != delData){
     temp = current;
     current = current->next;  
    }
    if(current == NULL){
    cout << delData << " was not in the list\n";
    delete delPtr;
    
}else{
        delPtr = current;
        current = current->next;
        temp->next = current;
        if(delPtr == head){
            head = head->next;
            temp = NULL;
            
        }
        delete delPtr;
        cout << "The Value " << delData << " was deleted\n";
} 
}


/*
 Prints the list.
 */
 void List::PrintList(){
        current = head;
        while(current!= NULL){
           
            
   cout << current->date<< ","<<current->name <<","
           <<current->grade <<endl;
    
            current = current->next;
        }
                
    }
 
 /*
  Searches the current date in the list and 
  * deletes the assignment from the list 
  * if found. Else prints  error message. 
  */
 
 void List::searchAssign(string findData){
     current = head;
     cout << "Searching for date...\n";
     while(current!= NULL){
         if(current->date == findData){     
             cout << current->date << " found\n";
             DeleteAssign(current->date);
         }else{
             cout << current->date << " data not found\n"; 
         } 
    current = current->next;
     }
         
     
 }

[whiteflags]

"found" is a node right?

A pointer to a node, actually.

My function "SearchAssign" doesn't return the node found from the list but it returns a message with the found node in it. From there it calls "DeleteAssign" to delete the line from the node.

That's fine.

I am curious as to why it deletes my entire line of assignment instead of just current->date since that is what is being called in "SearchAssign".

I thought that's what you wanted.

Also how could a insert a new assignment at the location where I've deleted the searched date?

Actually... how can I put this? If you are simply erasing the dates of given assignments and then changing them, it might be better performance wise if you simply overwrite assignments. For example, you will have an additional field in an assignment that marks when it is "done." From there on, the assignment doesn't matter. When you have a new assignment to put in its place, you can first look for done assignments to overwrite with new data, and mark them not done.

If the list gets too long, you can write a purge function to actually delete the nodes from memory.

I'm recommending this approach mainly because if you do it this way, you can invoke new less often. You would only need to invoke it when there are no old assignments around to reuse. And since this way leaves the list in tact, no special effort is required to find out where an old assignment was. In fact, after you delete an object normally there is really no guaranteed way of going back to that.

[FloatingButter]

I thought that's what you wanted.

It is, I was just having a hard time understanding how its delete it. Originally,I wasn't sure whether or not my "DeleteAssign" function would work correctly. I thought that since "current->date" was going into DeleteAssign, that only that specific
string in the list that had been found would be deleted and when I had called "PrintAssign", it would print the following:

"Statistics,43"
//... 
"English 101,100"

instead of removing the whole line itself.

Also how could a insert a new assignment at the location where I've deleted the searched date? Actually... how can I put this? If you are simply erasing the dates of given assignments and then changing them, it might be better performance wise if you simply overwrite assignments. For example, you will have an additional field in an assignment that marks when it is "done." From there on, the assignment doesn't matter. When you have a new assignment to put in its place, you can first look for done assignments to overwrite with new data, and mark them not done.

If the list gets too long, you can write a purge function to actually delete the nodes from memory.

I'm recommending this approach mainly because if you do it this way, you can invoke new less often. You would only need to invoke it when there are no old assignments around to reuse. And since this way leaves the list in tact, no special effort is required to find out where an old assignment was. In fact, after you delete an object normally there is really no guaranteed way of going back to that.

I apologize, I was reading my hw assignment wrong. In addition to searching for a due date and removing the assignment, my program is also suppose to search for a due date and insert a new assignment after that due date instead of removing it and inserting a new one at that location.

[FloatingButter]

I've managed to figure out how to insert an assignment after I've found a certain due date. I've ended up making two search function: "search_and_remove" and "search_and_insert" that removes and inserts a new assignment in a list. I've tested it a couple of times and it seems to work ok, except when the date to be searched is the last one in the list.


I'm excluding my h file since all I've added was my function
definitions for each search function. Any other critics on how I could improve my code would be appreciated as well.
list.cpp

#include <cstdlib>
#include <iostream>
#include <string>
#include "List.h"



using namespace std;

List::List(){
    head = NULL;
    current = NULL;
    temp = NULL;
    
}

/*
  adds a list of elements to 
 * assignment list. 
 */
void List::AddAssign(string addDate,string addName,string addGrade){
    Node n = new node;
    n->next = NULL;
    n->date = addDate;
    n->name = addName;
    n->grade = addGrade;
  
    
    if(head != NULL){
        current = head;
        while(current->next != NULL){
            current = current->next;
        }
        current->next = n;
    }
    else{
        head = n;
    }
}
/*
 Deletes an Assignment 
 */
void List::DeleteAssign(string delData){
    Node delPtr = NULL;
    temp = head;
    current = head;
    while(current != NULL && current->date  != delData){
     temp = current;
     current = current->next;  
    }
    if(current == NULL){
    cout << delData << " was not in the list\n";
    delete delPtr;
    
}else{
        delPtr = current;
        current = current->next;
        temp->next = current;
        if(delPtr == head){
            head = head->next;
            temp = NULL;
            
        }
        delete delPtr;
        cout << "The Value " << delData << " was deleted\n";
} 
}

/*
 Prints the list.
 */
 void List::PrintList(){
        current = head;
        while(current!= NULL){
           
            
   cout << current->date<< ","<<current->name <<","
           <<current->grade <<endl;
    
            current = current->next;
        }
                
    }
 
 /*
  Searches the current date in the list and 
  * deletes the assignment from the list 
  * if found.  
  */
 
 void List::search_and_remove(string findDate){
     current = head;

     while(current!= NULL){
         if(current->date == findDate){     
             cout << current->date << " found\n";
            DeleteAssign(current->date);
         } 
    current = current->next;
     }
         
     
 }
 
/*
 Searches and inserts a new assignment if a date is found.
 */
 void List::search_and_insert(string findDate,string date,string name,string grade){
       current = head;
             Node insertData = new node;
             insertData->date = date;
             insertData->name = name;
             insertData->grade = grade;
            
     while(current!= NULL){
         if(current->date == findDate){     
             cout << current->date << " found\n";
          //inserts the new assignment
            insertData->next = current->next;
             current->next = insertData;
         }                            
    current = current->next;
     }
     
 }

listmain.cpp

#include <cstdlib>
#include "List.h"
#include <string>
#include <iostream>

using namespace std;


int main(int argc, char** argv) {
 
//Tests a linked list.

    List assign;   
    
    
  assign.AddAssign("3/14/13","Statistics","43");
   assign.AddAssign("3/12/13","Geometry","43");
  assign.AddAssign("3/4/13","Calculus","45");
     assign.AddAssign("3/12/13","Java","43");
     assign.AddAssign("4/11/13","Biology","55");    
  assign.AddAssign("5/13/13","Economics","77");
   assign.AddAssign("3/11/13","English 101","100");
  assign.AddAssign("3/9/13","French","86");
     assign.AddAssign("5/23/13","Spanish","55");
     assign.AddAssign("3/3/13","Biology","55");
   
  cout << "Printing list...\n";
   assign.PrintList();
  
   
   cout << "Deleting assignments with 3/12/13\n";
   assign.search_and_remove("3/12/13");
   
   cout<< "New list without dates 3/12/13\n";
   assign.PrintList();


   cout << "search assignments with dates 3/9/13\n";
   assign.search_and_insert("3/9/13","3/24/13","PhysicsII","89");

   cout << "updated list with inserted assignment"
           " 3/24/13 PhysicsII 89 \n";
   assign.PrintList();
     cout << "End of list. \n"; 

return 0;
}

[whiteflags]

Really? It seems to work alright for me.

I compiled your code, and added these lines to the tail end of the main function of the program:

  cout << "search assignments with date 3/3/13 \n";
  assign.search_and_insert("3/3/13", "3/11/13", "Humanities", "90");
  assign.PrintList();

If I put a breakpoint before there, I get the following output:

Printing list...
3/14/13,Statistics,43
3/12/13,Geometry,43
3/4/13,Calculus,45
3/12/13,Java,43
4/11/13,Biology,55
5/13/13,Economics,77
3/11/13,English 101,100
3/9/13,French,86
5/23/13,Spanish,55
3/3/13,Biology,55
Deleting assignments with 3/12/13
3/12/13 found
The Value 3/12/13 was deleted
3/12/13 found
The Value 3/12/13 was deleted
New list without dates 3/12/13
3/14/13,Statistics,43
3/4/13,Calculus,45
4/11/13,Biology,55
5/13/13,Economics,77
3/11/13,English 101,100
3/9/13,French,86
5/23/13,Spanish,55
3/3/13,Biology,55
search assignments with dates 3/9/13
3/9/13 found
updated list with inserted assignment 3/24/13 PhysicsII 89
3/14/13,Statistics,43
3/4/13,Calculus,45
4/11/13,Biology,55
5/13/13,Economics,77
3/11/13,English 101,100
3/9/13,French,86
3/24/13,PhysicsII,89
5/23/13,Spanish,55
3/3/13,Biology,55
End of list.

This is after the date found in the list. Continuing ...

search assignments with date 3/3/13
3/3/13 found
3/14/13,Statistics,43
3/4/13,Calculus,45
4/11/13,Biology,55
5/13/13,Economics,77
3/11/13,English 101,100
3/9/13,French,86
3/24/13,PhysicsII,89
5/23/13,Spanish,55
3/3/13,Biology,55
3/11/13,Humanities,90

Isn't this OK? That is what I would expect, given the code.

[FloatingButter]

^ I hadn't tested the search and insert function yet, but for the search and remove function, If I tried to run the following code below, It'll print out the entire list but not run my search and remove function. I think there might be something wrong with my "DeleteAssign" function.

   
  assign.AddAssign("3/14/13","Statistics","43");
   assign.AddAssign("3/12/13","Geometry","43");
  assign.AddAssign("3/4/13","Calculus","45");
     assign.AddAssign("3/12/13","Java","43");
     assign.AddAssign("4/11/13","Biology","55");    
  assign.AddAssign("5/13/13","Economics","77");
   assign.AddAssign("3/11/13","English 101","100");
  assign.AddAssign("3/9/13","French","86");
     assign.AddAssign("5/23/13","Spanish","55");
     assign.AddAssign("3/3/13","Biology","55");
   
  cout << "Printing list...\n";
   assign.PrintList();


   //Deletes another assignment
      cout << "Deleting assignments with dates 3/3/13\n";
   assign.search_and_remove("3/3/13");
   cout << "New list without 3/3/13\n";
   assign.PrintList();
   /*

[FloatingButter]

I know whats wrong, I have to implement a condition to check if the delPtr is at the end of the list and then delete it. I know that in order to do this I have to point the tail of the node to the one previous to it, then link the new tail to null, and delete it. I'm unsure of where to place it in my deleteAssign function though.

[whiteflags]

I see, well if you want my recommendation, do this:

node *remove (node *head, node *old)
{
  node *before = head;
  if ( head != old ) {
    while ( before->next != old )
      before = before->next;

    before->next = old->next
  } else {
    head = old->next;
  }
  delete old;

  return head;
}

Because unless you are keeping track of where the tail is, or something, it should not be a special case.

No matter where you are deleting from in the list, you always need the pointer to the previous node. In fact this is one of the reasons why doubly linked lists are good, because you can delete any node with just a pointer to the node...

[FloatingButter]

Is the old node the tail or the previous node?

[whiteflags]

Neither. The old node will be removed. I find out where the previous node is using the loop in the function.

[FloatingButter]

Ok. I ended up redoing that function, and now it can delete from the end of the list(see code for new version). The only problem that I am having now is getting my search and insert function to insert a new assignment if it finds a date more than once instead of the list. When I
test this in main it doesn't printout everything that it should.


This is my delete function(all of my other functions haven't changed):

.
/*
 Deletes an Assignment 
 */

void List::DeleteAssign(string delData){
    //if the list is empty at head.
    if(head == NULL){
        cout << "error cannot delete from empty list\n";
    }else{
        current = head;
       
       while(current != NULL){
           if(current->date == delData){
               break;
           }else{
               previous = current;
               current = current->next;
           }
       } 
        //case 2 node with name not found.
        if(current == NULL){
            cout << "name not found\n";
        }else{
            //deletes head node
            if(head == current){
                head = head->next;
            }else{
               //deletes beyond head.
                previous->next = current->next;
            }
               cout << "The value " << delData << " was deleted\n";
            delete current;
        }
    }
    
    
}

My main function tests:

#include <cstdlib>
#include "List3.h"
#include <string>
#include <iostream>

using namespace std;


int main(int argc, char** argv) {
 
    List assign;
       
  assign.AddAssign("3/14/13","Statistics","43");
   assign.AddAssign("3/12/13","Geometry","43");///3/12 deletes
  assign.AddAssign("3/9/13","Calculus","45");
     assign.AddAssign("3/12/13","Java","43");
     assign.AddAssign("4/11/13","Biology","55");   
  assign.AddAssign("5/13/13","Economics","77");
   assign.AddAssign("3/11/13","English 101","100");
  assign.AddAssign("3/9/13","French","86");//inserts physics 
     assign.AddAssign("5/23/13","Spanish","55");
     assign.AddAssign("3/3/13","Biology","55");
    
  cout << "Printing list...\n";
   assign.PrintList();
   
    //deletes two assignments from list
   cout << "Deleting assignments with 3/12/13\n";
   assign.search_and_remove("3/12/13");
    
   cout<< "New list without dates 3/12/13\n";
   assign.PrintList();
    
   //Does not work with two of the same dates in list
 
   cout << "search assignments with dates 3/9/13\n";
   assign.search_and_insert("3/9/13","3/24/13","PhysicsII","89");
 
   cout << "updated list with inserted assignment"
           " 3/24/13 PhysicsII 89 \n";
   assign.PrintList();
     cout << "End of list. \n"; 
     
    return 0;

//Should print out this list:
// instead it leaves out the assignments in bold..

   /*
   3/14/13,Statistics,43
3/9/13,Calculus,45
    * 3/24/13,PhysicsII,89
    4/11/13,Biology,55
5/13/13,Economics,77
3/11/13,English 101,100
3/9/13,French,86
    * 3/24/13,PhysicsII,89
    * 5/23/13,Spanish,55
3/3/13,Biology,55
    */
   



}

[whiteflags]

My function has this loop in it:

    // stop when before->next points to old
    while ( before->next != old )
      before = before->next;

    //Therefore, before points to the previous node
    // Unlink the old node by fixing the previous link to the next node.
    before->next = old->next

Your function stops when you find delData.

       while(current != NULL){
           if(current->date == delData){
               break;
           }else{
               previous = current;
               current = current->next;
           }

Obviously, finding delData is important and should happen, but since we are interested in finding the node that points to the node that has this data, the new deleteAssign() has some significant differences from the implementation I showed you.