insertEnd() linked list

You just need to check if list is empty:

bool LinkedList::insertEnd(T item)
{
     Node* current;
     current = first;

    if ( current != NULL )
    { // List not empty
         while (current->next != 0)
         {
              current = current->next;
         }
         current->next = new Node;
         current = current->next;
    }
    else
    { // List empty
        // Alternatively, you could call "insertStart(item)" here rather than these two ines.
        current = new Node;
        first = current;
    }
    current->value = item;
    current->next = 0;
}

Also, if you gave Node a constructor that set next to NULL and took item as a parameter to initialize value, you could have code like this:

bool LinkedList::insertEnd(T item)
{
     Node* current;
     current = first;

    if ( current != NULL )
    {
         while (current->next != 0)
         {
              current = current->next;
         }
         current->next = new Node(item);
         current = current->next;
    }
    else
    {
        // Alternatively, you could call "insertStart(item)" here rather than these two ines.
        current = new Node(item);
        first = current;
    }
}

And finally, to facilitate inserting at the end, you could keep track of the end node:

bool LinkedList::insertEnd(T item)
{
    if ( last != NULL )
    {
        last->next = new Node(item);
        last = last->next;
    }
    else
    {
        last = new Node(item);
        first = last;
    }
}

This of course adds a little extra code to "insertStart" and any deletion methods.

I think that will work. Here is another quick question for you.

My remove() is invoking the debugger so something is not quite right with it. Can you take a look and let me know what should be changed?

 void LinkedList::remove(T item)
{
      Node *current = first;
      Node *previous;

      //verify value is in the list first...
      if (current->value == item)      
      {
            //reassign
            first = current->next;
            delete current;
      }
      else
      {
            
            previous = current;
            current = current->next;
            while (current->value != item)
            {
                  current = current->next;
            }
            previous = previous->next;
      }
      previous->next = current->next;
      delete current;
}

BTW - the way I am calling this function is simply by passing a word to it. For example, list.remove("Tree");

If your items are character arrays like that, you shouldn't be using == and != to compare them.  That just compares pointers which probably isn't the result you want.

The problem is probably that you don't handle the case where 'item' is not found in the list (likely with the incorrect compare).  The while loop executes until 'current' becomes null at which time you'll get an access violation or something when you try to get 'current->next' with the bad value of 'current'.  The template function will not work with T being char*.  You'll probably have to use std::string which defines == and != to do the right thing.

I'm not clear on exactly what your suggestion of resolution is here. Are you saying I need to add - using namespace std; or something else?

I'm saying that char*, which appears to be 'T' in your present case, does not behave line int or float.  You cannot simply compare pointers.  For instance, you might have 'str1' and 'str2', both of which are char* and presently having the value "My String", but str1 != str2.  You can use std::string which wraps a class around char* so you can take two strings and do 'stdStr1 == stdStr2;'.  It does a proper string compare.

So yes, you could do 'using namespace std;'.  You also need to '#include <string>' and use 'std::string' in your template instantiation.

I was already using namespace std and #include <string> did not help.

Maybe this will help you to help me. Here is what I have in my class...

----------------------------------
LinkedList.h


#include <string>
#include "Node.h"
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

using namespace std;

class LinkedList
{
public:
      //constructor no args
      LinkedList();
      //destructor
      ~LinkedList();
      //insert value into front of list
      void insertFront(T item);
      //insert value into end of list
      bool insertEnd(T item);                                    
      void display() const;
      //return number of values in the list
      int getLength() const;                        
      bool search(T item) const;
      void remove(T item);                                    
      bool empty() const;                  
      void deleteList();                                                

private:
      Node *first;
      int item;
};
#endif
-------------------------------------

Here is what I have in my node.h file


#ifndef NODE_H
#define NODE_H

typedef std::string T;                              

struct Node                                                
{
      T value;
      Node *next;
};
#endif

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

Here is my remove() definition

void LinkedList::remove(T item)
{
      Node *current = first;
      Node *previous;

      //verify value is in the list first...
      if (current->value == item)      
      {
            //reassign
            first = current->next;
            delete current;
      }
      else
      {
            
            previous = current;
            current = current->next;
            while (current->value != item)
            {
                  current = current->next;
            }
            previous = previous->next;
      }
      previous->next = current->next;
      delete current;
}
----------------------------------------

When I call it like this list.remove("Tree"); the program opens the debugger window and basically blows up.

Can you tell me exactly what I need to change now?

Thank you that works.

BTW - do you know a quick way to return the string "True" of "False" instead of 0 or 1 from my empy bool function?

Not a good way.  You can have a macro or inline function:

inline const char* BoolStr(bool val)
{
    val ? "True" : "False";
}

Put that in a header to get included wherever you use that function and then you can put:

   return BoolStr(<condition expression>);

in your functions to return "True" or "False" as characters.  <condition expression> is something that evaluates to a bool.

when i have my empty() like this now

bool LinkedList::empty() const
{
      //return (first == 0);
       return BoolStr(<condition expression>);
}

it tells me

error C2065: 'BoolStr' : undeclared identifier

I just put that inline function in my class definition file with the other functions. was that ok?

Should be.  But then you need to change your empty() method if you want to return the text:

 const char* LinkedList::empty() const
{
     //return (first == 0);
      return BoolStr(first == NULL);
}


Otherwise, you'd keep the old one if you want it to return a bool.

Where exactly did you put BoolStr since the compiler is complaining that it doesn't exist?

drichards,

I'm trying to add a function to this little program called GetFirstNode which basically should return the value at the beginning of the list. Here is what I have, but its not quite working. Can you help me?

------------------------------
Node.h file


#ifndef NODE_H
#define NODE_H

typedef std::string T;                              

struct Node                                                
{
      T value;
      Node *next;
};
#endif
--------------------------------
In my class declaration

T GetFirstValue();

---------------------------
Actual function (does not work though)

T LinkedList::GetFirstValue()
{
      Node *current = first;
      return first;
}

You need to return the value if that's what you're after.  Otherwise, the function should return Node*, not T.

T LinkedList::GetFirstValue()
{
     return first->value;
}

or

Node* LinkedList::GetFirstValue()
{
     return first;
}

I want to return the value of the first node.

I have tried both of these with this call...

      cout << "First value is:  " << endl;
      list.GetFirstValue();

However, no value is displayed. What am I missing?

The code does not give any errors and the list is not empty. It has 3 values ("Tree, Sun, Apple") at the time of the call. It should be returning Tree in this case.

Assuming you're using the first variant of 'GetFirstValue' above to return the std::sring, you do output like this:

    cout << "First value is: " << list.GetFirstValue().c_str() << std::endl;

Your code did not even attempt to output the returned value and you need to use the c_str() method to get a 'const char*' that cout can deal with.  There is no implicit cast to 'const char*' for std::string.  

Thank you.

I'm very much still learning this. Thanks again.

drichards, a quick question for you here. Currently, in main() I am hardcoding the words that I want to insert into the front and end functions. Can you tell me how I would read in a simple text file, say that looks like this...

sun
tree
apple

and have that be the data that gets inserted into the front and end. And then when I search I'm not hardcoding the word I am just looking through the file to see if its there. Does that make sense? Basically, I need to use this little txt file instead of me hard coding the words in. Here is what main() currently looks like.

-------------------------------------------------------
#include "LinkedList.h"
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
      LinkedList list;
      string word;

      //insertFront
      list.insertFront("Tree");

      //insertEnd
      list.insertEnd("Apple");
      list.display();

      //insertFront user input
      cout << "Enter a word:  " << endl;
      cin >> word;
      list.insertFront(word);
      cout << "After user input list now contains:  " << endl;
      list.display();

      //search
      cout << "Search for:  " << endl;
      cin >> word;
      if (list.search(word))
      {
            cout << "Already on list." << endl;
      }

      //list size
      cout << "List size:  " << list.getLength() << endl;

      //return first value
      //use the c_str() method to get a 'const char*' that cout can deal with
      cout << "First value is: " << list.GetFirstValue().c_str() << std::endl;
      //list.GetFirstValue();

      //remove
      list.remove("Tree");
      cout << "After remove() is called list size is:  " << list.getLength() << endl;
      cout << "After remove(Tree) is called values in list are:  " << endl;
      list.display();

      //remove first node
      cout << "Remove First Node:  " << endl;
      list.RemoveFirstNode();
      cout << "Items in list after removing first node:  " << endl;
      list.display();

      //empty
      cout << "Is the list empty:  " << list.empty() << endl;

      //deleteList
      list.deleteList();
      cout << "After deleteList() is called list size is:  " << list.getLength() << endl;

    return 0;
}

You read the file like this:

    string txt;
    ifstream infile;
    infile.open("<file name>"); // use correct file name

    while (!infile.eof())
    {
        std::getline(infile, txt);
        if (!txt.empty())
        {
            // insert string into list...
        }
    }

A couple of questions about that...

1. When you say insert string into list. What I want to do is insert the data that is in the txt file into my insertFront(). So, how do I say that in the code? Is it list.insertFront(infile);

And then when I want to display do I say, list.display(infile);

I'm not sure if this is the right way to pass the values in the text file to the functions.

I'm just really trying to use the data from this text file that I read in instead of saying things like, list.insertFront("Tree");

You know what I mean?

I don't know how to pass the values of the text file to this function or any of them for that matter. For example, I have been saying for say, search(). list.search("Tree"); now I want to be able to call that and say, list.search("any of the words in the text file); Does that make sense?  

Yes, but you'll have to change your search function to do that.  You can put the strings from the file into a vector:

    string txt;
    ifstream infile;
    vector<string> searchStrings;
    infile.open("<file name>"); // use correct file name

    while (!infile.eof())
    {
        std::getline(infile, txt);
        if (!txt.empty())
        {
            searchStrings.push_back(txt);
        }
    }


Then you can write a search method for your list that uses the vector (it's not clear what you would want this to actually do):


<return type> LinkedList::search(vector<string> &searchList)
{
    for (int ii = 0; ii < searchList.size(); ii++)
    {
        <type> result = search(searchList[ii]);  // use your search function that looks for a single string
        if (result == ???)
        {
            // do logic here...
        }
    }
    return ???;
}
   

Ok. Let me clarify here. Maybe this will help. I already have all the functions working. In other words, the program works when I do stuff like this...

list.insertFront("Tree")
list.insertEnd("Bird")
list.display() //this will then display tree and bird
list.search("Tree") // this will the word is already in the list

At this point all I need to do is instead of me hardcoding these words (tree and bird) I have to read the words in from a txt file and use those. My question is how do I do that?

Any further comments after my last post?

>>  I have to read the words in from a txt file and use those. My question is how do I do that?

It is still not clear to me what you're doing with the file.  You can use the code above to read the file and do whatever you want with the words.  Once variant gets the words and adds them to the list.  You don't have to do the list insertion if that's not what you want.  The other one puts the words in a vector and calls a method to look through the list for each element of the vector.  I assume by your last comment that you don't want to add any more methods to the list class, so just don't make the above method a member of the list class.  Either use the first code snippet and call your list search instead of adding the words to the list or use the second code snippet and just make it a regular function rather than a method of the list class.  What exactly are you looking for?

Ok.

1. I can't use vectors for this, so it has to a little easier than that.

Here is what I have so far....maybe this will help to clarify what is happening. To reiiterate I am just simply wanting to use the words in the txt file (tree, sun, star) and insert these to the front, to the end, and then just do a search after the user types in a word to search for. If its on the list then display that it is.

---------------------------------------
LinkedListMain.cpp

#include "LinkedList.h"
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{
      LinkedList list;      
      string word;
      string filename;
      string line;

      cout << "Enter filename:  " << endl;
      cin >> filename;
      
      ifstream fin(filename.c_str());
    if (!fin)
      {
            std::cout << "Error: Unable to open " << filename << '\n';
            return 1;
      }
      else
      {
            std::cout << "File opened" << '\n';
      }
      
      while (getline(fin,line))
      {
            list.insertFront(fin);
      }

      //insertFront
      //list.insertFront("Tree");
      list.display(fin);

      //insertEnd
      //list.insertEnd("Apple");
      list.display();

      //insertFront user input
      cout << "Enter a word:  " << endl;
      cin >> word;
      //list.insertFront(word);
      cout << "After user input list now contains:  " << endl;
      list.display();

      //search
      cout << "Search for:  " << endl;
      cin >> word;
      if (list.search(word))
      {
            cout << "Already on list." << endl;
      }

      //list size
      cout << "List size:  " << list.getLength() << endl;

      //return first value
      //use the c_str() method to get a 'const char*' that cout can deal with
      cout << "First value is: " << list.GetFirstValue().c_str() << std::endl;
      //list.GetFirstValue();

      //remove
      list.remove("Tree");
      cout << "After remove() is called list size is:  " << list.getLength() << endl;
      cout << "After remove(Tree) is called values in list are:  " << endl;
      list.display();

      //remove first node
      cout << "Remove First Node:  " << endl;
      list.RemoveFirstNode();
      cout << "Items in list after removing first node:  " << endl;
      list.display();

      //empty
      cout << "Is the list empty:  " << list.empty() << endl;

      //deleteList
      list.deleteList();
      cout << "After deleteList() is called list size is:  " << list.getLength() << endl;

    return 0;
}
------------------------------------------------

Node.h

#ifndef NODE_H
#define NODE_H

typedef std::string T;                              

struct Node                                                
{
      T value;
      Node *next;
};
#endif
-----------------------------------------

LinkedList.h

#include <string>
#include <fstream>
#include "Node.h"
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

using namespace std;

class LinkedList
{
public:
      //constructor no args
      LinkedList();
      //destructor
      ~LinkedList();
      //insert value into front of list
      void insertFront(ifstream &);
      //insert value into end of list
      bool insertEnd(T item);                                    
      void display() const;
      //return number of values in the list
      int getLength() const;                        
      bool search(T item) const;
      void remove(T item);                                    
      bool empty() const;                  
      void deleteList();
      void RemoveFirstNode();
      T GetFirstValue();



private:
      Node *first;
      int item;
};
#endif
---------------------------------------

LinkedList.cpp

#include <iostream>
#include "LinkedList.h"
#include "Node.h"

using namespace std;

//constructor
LinkedList::LinkedList()
{
      first = 0;
}

//destructor                                                      
LinkedList::~LinkedList()
{
      deleteList();
}

//insertFront()
void LinkedList::insertFront(ifstream &)
{
      Node *another;
      another = new Node;                                          
      another->value = item;                                    
      another->next = first;      
      first=another;
}

//insertEnd()
bool LinkedList::insertEnd(T item)
{
     Node* current;
     current = first;

    if ( current != NULL )
    { // List not empty
         while (current->next != 0)
         {
              current = current->next;
         }
         current->next = new Node;
         current = current->next;
    }
    else
    { // List empty
        current = new Node;
        first = current;
    }
    current->value = item;
    current->next = 0;
}

//display()
void LinkedList::display() const
{
      Node *current;
      current = first;
      
      while (current != 0)
      {
            cout << current->value << endl;
            current = current->next;      
      }
}

//getLength()
int LinkedList::getLength() const
{
      Node* current;
      int count = 0;
      current = first;
      
      while (current != 0)
      {
            ++count;
            current = current->next;
      }
      return count;
}

//search()
bool LinkedList::search(T item) const                  
{
      Node *current = first;
      bool found = false;

      while (current != 0 && current->value != item)
      {
            current = current->next;
      }
      if (current != 0)
      {
            found = true;
      }
      return found;
}

//remove()
void LinkedList::remove(T item)
{
      Node *current = first;
      Node *previous;

      //verify value is in the list first...
      if (current->value == item)      
      {
            //reassign
            first = current->next;
            delete current;
      }
      else
      {
            
            previous = current;
            current = current->next;
            while (current->value != item)
            {
                  current = current->next;
            }
      }
      if (current != NULL)
      {
            previous->next = current->next;
            delete current;
            //previous = previous->next;
      }
}

//empty()
bool LinkedList::empty() const
{
      return (first == 0);
}

//deleteList()
void LinkedList::deleteList()                                    
{
      Node* current = first;
      Node* previous;

      while (current != 0)
      {
            previous = current;
            current = current->next;
            delete previous;
      }
      first = 0;
}

//RemoveFirstNode()
void LinkedList::RemoveFirstNode()
{
      Node* current = first;
      
      //reassign first
      first = current->next;
      delete current;
}

//GetFirstValue()
T LinkedList::GetFirstValue()
{
     return first->value;
}

I changed the main() where it was reading in a txt file a little easier...Now it just looks like this.

      string txt;
    ifstream infile;
    infile.open("words.txt");

    while (!infile.eof())
    {
        infile >> txt;
      }

Then I have list.insertFront(txt);

However, when I call list.display(); nothing appears on the screen. Do I need to pass display() some argument?

Maybe I'm not doing this right.

      string txt;
    ifstream infile;
    infile.open("words.txt");

    while (!infile.eof())
    {
        infile >> txt;
      }

Because when I do this...

cout << txt; nothing appears and cout << infile; displays 000000. So, would that mean nothing is being read in?? I'm probably just missing something simple.

Any thoughts? :)

I'm stumped man. I dont know why this...

      string txt;
    ifstream infile;
    infile.open("words.txt");

      if (!infile)
      {
            std::cout << "Error: Unable to open " << infile << '\n';
            return 1;
      }
      else
      {
            std::cout << "File opened" << '\n';
      }

    while (!infile.eof())
    {
            std::getline(infile, txt);
            list.insertFront(txt); //insert the words in the txt file into the list

cout << txt;
}

does not display the words in the word.txt file?? I mean I don't want to use cout really, just for test purposes. But, shouldn't it be outputting the words??

Can you help me mate just a bit more to get this working?

If 'txt' is a std::string, you cannot do either '(f/c)in >> txt;' or 'cout << txt;'.  You need:

std::getline(fin,txt);
std::getline(cin,txt);

cout << txt.c_str();

Other than that you seem to be on the right track.  You've got a lot of wgat appears to be debug code, so I'm not going to try to clean it up for you.  I think you are just having issues with reading/writing the std::string's.