Need to complete insert function

[bobby118]

Need to create the insert function all other code is complete and cant be changed, struggling to get this to work at all, have tried creating a node however got no further, any help would be great, the more detailed the better

This is the part i need to complete

// Insert the given string into the linked-list such that the
// entries in the linked-list are in alphabetical order
bool List::insert(const char *string_p)
{
  // Please write the list insert function
  return SUCCESS;
}

FULL CODE

  
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

#define SUCCESS 0
#define FAIL    1

// Represents an entry object in the linked-list
class ListEntry
{
  public:
    explicit     ListEntry();
    explicit     ListEntry(const char *string_p);
                 ~ListEntry();
    string       getData();
    void         setData(const char* string_p);
    void         setData(string string);
    ListEntry   *getNext();
    ListEntry   *getPrevious();
    ListEntry   *prev_p;   // pointer to previous entry in the linked-list
    ListEntry   *next_p;   // pointer to next entry in the linked-list

  private:
    string          data;      // entry's string
};

// Represents the linked-list object
class List
{
  public:
    List();
    ~List();

    bool printForward();
    bool printReverse();
    bool insert(const char *string_p);

  private:
    int        entryCount;  // number of entries present in the linked-list
    ListEntry *head_p;      // pointer to the first entry in the list
    ListEntry *tail_p;      // pointer to the last entry in the list
};

// ListEntry constructor
ListEntry::ListEntry()
{
  this->prev_p = NULL;
  this->next_p = NULL;
  return;
}

// ListEntry constructor
ListEntry::ListEntry(const char *string_p)
{
  this->data   = string_p;
  this->prev_p = NULL;
  this->next_p = NULL;
  return;
}

// List entry destructor 
ListEntry::~ListEntry()
{
  return;
}

// Return the stored string object
string ListEntry::getData()
{
  return this->data;
}

// Set the internal string data from a char*
void ListEntry::setData(const char* string_p)
{
  this->data = string_p;
}

// Set the internal string data from a string
void ListEntry::setData(string string)
{
  this->data = string;
}
 
// Returns reference to the next entry in the list
ListEntry *ListEntry::getNext()
{
  return this->next_p;
}

// Returns reference to the previous entry in the list
ListEntry *ListEntry::getPrevious()
{
  return this->prev_p;
}

// List constructor
List::List()
{
  this->entryCount = 0;
  this->head_p     = NULL;
  this->tail_p     = NULL;
}

// List destructor
List::~List()
{
  // Delete all entries in the list
  ListEntry *entry_p   = this->head_p;
  ListEntry *current_p = this->head_p;

  while (entry_p != NULL)
  {
    current_p = entry_p; 
    entry_p = entry_p->getNext();
    delete current_p;
  }
 }

// Output linked list in order from head to tail
// printing out the string data from each list entry
bool List::printForward()
{
  ListEntry *entry_p = this->head_p;
  int count = 0;

  cout << "FORWARD: " << this->entryCount << " entries\n";
  while (entry_p != NULL)
  {
    cout << entry_p->getData() << " ";

    if (++count % 5 == 0 || entry_p == this->tail_p)
    {
      cout << endl;
    }

    entry_p = entry_p->getNext();
  }

  return SUCCESS;
}

// Output linked list in reverse order from tail to head
// printing out the string data from each list entry
bool List::printReverse()
{
  ListEntry *entry_p = this->tail_p;
  int count = 0;

  cout << "REVERSE: " << this->entryCount << " entries\n";
  while (entry_p != NULL)
  {
    cout << entry_p->getData() << " ";

    if (++count % 5 == 0 || entry_p == this->head_p)
    {
      cout << endl;
    }

    entry_p = entry_p->getPrevious();
  }

  return SUCCESS;
}

// Insert the given string into the linked-list such that the
// entries in the linked-list are in alphabetical order
bool List::insert(const char *string_p)
{
  // Please write the list insert function
  return SUCCESS;
}

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

  const char *places[] = { "Aberdeen", "Bakewell", "Cocking", "Dogdyke",
                           "Eastbourne", "Farranfadda", "Gaggin", "Hadfield",
                           "Irnham", "Jameston", "Kendal", "Langley",
                           "Malmesbury", "Netherhampton", "Ogmore", "Pant",
                           "Quedgeley", "Ramsbottom", "Sallynoggin",
                           "Talla Bheith Forest", "Upchurch", "Victoria Bridge",
                           "Wacton", "Xeroxillington", "Yelling", "Zetland" };
  
  unsigned char indexes[] = { 1, 14, 17, 3, 22, 0, 5, 18, 24, 11, 4, 6, 13, 21,
                              2, 12, 25, 19, 10, 16, 7, 9, 23, 15, 20, 8 };


  List placesList;

  // Insert every word in the places array into the
  // linked-list.
  cout << "INSERT:\n";
  for (unsigned int count = 0; count < sizeof(indexes); count++)
  {
    cout << places[indexes[count]] << " ";

    //Add a new line for console readability
    if( count > 0 && count % 5 == 0)
    {
      cout << endl;
    }

    placesList.insert(places[indexes[count]]);
  }
  cout << endl;

  // print out the list in alphabetical order
  placesList.printForward();
  cout << endl;

  // print out the list in reverse alphabetical order
  placesList.printReverse();
  cout << endl;

  return SUCCESS;
}

[VictorN]

Do you know how the linked-list is designed and how it works?
Do you know how to iterate through the list?
Do you know how to compare the strings?

[2kaud]

The list is doubly linked with next and previous pointers. So to insert an item into the list so that it maintains a required ascending sorted order, you simply traverse the list from the head until the value of the node at entry->next is greater than the value to be inserted. When this is true then you insert the new element after the current node - adjusting all pointers as needed and the list count. There are a couple of edge conditions to consider - the list is empty, the value of the first element in the list is greater than the insert value and entry->next is NULL.

Note that current good practice is to use nullptr rather than NULL to signify that a node pointer doesn't point to another valid node.

[bobby118]

Do you know how the linked-list is designed and how it works?
Do you know how to iterate through the list?
Do you know how to compare the strings?

I understand how the linked list is designed and works, however I do not understand how to iterate through the list or compare the strings, sorry im very basic in c++ coding.

[VictorN]

I understand how the linked list is designed and works, however I do not understand how to iterate through the list or compare the strings, sorry im very basic in c++ coding.

Well, now 2kaud explained you both these "problems". So try to implement it in code!

[2kaud]

I do not understand how to iterate through the list

Look at how printForward() is coded. That iterates through the linked list starting at the head.

or compare the strings

As the data is of type string, comparison is very easy. If entry_p is a pointer to a list node and you want to test for equality to say variable s1 which is of type string then

string s1 = "test";
...
if (entry_p->getData() == s1) {
  //statements for equality true here
}

all other code is complete and cant be changed

Is this code that you're written or has this been provided?

[bobby118]

This has been provided so it needs to maintain that form, I see the code to iterate through the list is

 	                ListEntry *entry_p = this->head_p;
			cout << "ALPHA: " << this->entryCount << " entries\n";
				while (entry_p != NULL)
				{
					cout << entry_p->getData() << " ";
		
					if (++count % 5 == 0 || entry_p == this->tail_p)
					{
						cout << endl;
					}
		
					entry_p = entry_p->getNext();
				}

[VictorN]

This has been provided so it needs to maintain that form, I see the code to iterate through the list is

 	                ListEntry *entry_p = this->head_p;
			cout << "ALPHA: " << this->entryCount << " entries\n";
				while (entry_p != NULL)
				{
					cout << entry_p->getData() << " ";
		
					if (++count % 5 == 0 || entry_p == this->tail_p)
					{
						cout << endl;
					}
		
					entry_p = entry_p->getNext();
				}

What could/should mean this line? The left part of it?

[bobby118]

I understand that there is a std::sort() function that could sort through the words, however for the if statement it would need to compare the entrys and put it to the front or back of the list if its alphabetical.

[2kaud]

This has been provided

Well it's not the best way of coding this in modern c++. It could do with updating to use current c++ good practice....

I see the code to iterate through the list

Good. Now do you understand it? So now you can attempt to code insert().

[2kaud]

I understand that there is a std::sort() function that could sort through the words, however for the if statement it would need to compare the entrys and put it to the front or back of the list if its alphabetical.

To insert the words alphabetically into the list, you don't need the sort() function. I explained how to insert to ascending order in post #3. What don't you understand about that?

[bobby118]

I understand what it supposed to do, and that it needs to compare the values, however im not sure how to code this in C++, even this is very basic i dont know how to code this

[2kaud]

What have you covered in your lessons? What book are you using? Has your teacher not covered list insertion in class?

[VictorN]

I understand what it supposed to do, and that it needs to compare the values, however im not sure how to code this in C++, even this is very basic i dont know how to code this

Now you should learn how and where to get any useful info about what you seem to need...
The first step - use google search like https://www.google.ch/webhp?sourceid...mpare+string&*
The next step - try to find the more useful info applying to your concrete problem (in your case there would be the first three links)
And finally - find the proper documentation together with the appropriate sample code!

[bobby118]

Our teacher has not covered this at all, we have only been taught very basic c++