Solved

insertEnd() linked list

Posted on 2004-09-24
33
308 Views
Last Modified: 2013-12-14
Currently this is what I have for my insertEnd(). I'm trying to use a linked list and basically insert a value at the end of the list. However, In InsertEnd() I must check for the list being empty.  The way it is coded at the moment it causes a problem during the first call to InsertEnd().  'first' is 0, so 'current' is set to 0.  Then I am using 'current->next' in the while loop condition.  Since 'current' is 0 this will cause the program to crash.  I have to treat the list being empty as a special case within the InsertEnd() function. My question is what do I need to change in order to do this...

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

      while (current->next != 0)
      {
            current = current->next;
      }
      current->next = new Node;
      current = current->next;
      current->value = item;
      current->next = 0;
}
0
Comment
Question by:jandhb
  • 21
  • 12
33 Comments
 
LVL 19

Expert Comment

by:drichards
ID: 12149365
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12150300
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;
}
0
 
LVL 1

Author Comment

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

Expert Comment

by:drichards
ID: 12150872
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12151747
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?
0
 
LVL 19

Expert Comment

by:drichards
ID: 12151778
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12151826
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?
0
 
LVL 19

Accepted Solution

by:
drichards earned 25 total points
ID: 12151890
At the bottom of the method, remove the indicated line.  I missed this last time.  You still need to handle the case where item is not found, so I added that as well.

   else
   {
         
          previous = current;
          current = current->next;
          while (current->value != item)
          {
               current = current->next;
          }
//          previous = previous->next;  <--- remove this line.  This sets previous to current which you are about to delete.
     }
     if ( current != NULL )
     {
         previous->next = current->next;
         delete current;
     }
}
0
 
LVL 1

Author Comment

by:jandhb
ID: 12151982
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?
0
 
LVL 19

Expert Comment

by:drichards
ID: 12152141
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12152187
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?

0
 
LVL 19

Expert Comment

by:drichards
ID: 12153323
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?
0
 
LVL 1

Author Comment

by:jandhb
ID: 12156311
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;
}

0
 
LVL 19

Expert Comment

by:drichards
ID: 12156326
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;
}

0
 
LVL 1

Author Comment

by:jandhb
ID: 12156343
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?
0
 
LVL 1

Author Comment

by:jandhb
ID: 12156347
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.
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 19

Expert Comment

by:drichards
ID: 12156429
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.  
0
 
LVL 1

Author Comment

by:jandhb
ID: 12156442
Thank you.

I'm very much still learning this. Thanks again.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12176377
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;
}
0
 
LVL 19

Expert Comment

by:drichards
ID: 12180983
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...
        }
    }
0
 
LVL 1

Author Comment

by:jandhb
ID: 12181540
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12181655
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?  
0
 
LVL 19

Expert Comment

by:drichards
ID: 12181984
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 ???;
}
   
0
 
LVL 1

Author Comment

by:jandhb
ID: 12182456
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?
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185242
Any further comments after my last post?
0
 
LVL 19

Expert Comment

by:drichards
ID: 12185521
>>  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?
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185590
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;
}
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185618
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?
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185641
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.
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185709
Any thoughts? :)
0
 
LVL 1

Author Comment

by:jandhb
ID: 12185762
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??
0
 
LVL 1

Author Comment

by:jandhb
ID: 12186236
Can you help me mate just a bit more to get this working?
0
 
LVL 19

Expert Comment

by:drichards
ID: 12189953
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.
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now