Need to complete Insert function

[bobby1]

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;
}

[dhayden]

Why do you have getNext() and getPrevious() functions wihen prev_p and next_p are public?

There are two parts to the insert() method. First you have to figure out where to insert the item, and then you have to actually do it.

You can figure out where to insert it by walking down the list, comparing the current node to the name. Once you get to a node that whose name is >= the name you're inserting, then you've found the node that you to insert before. Put another way, the current node is the one that will come after the new node. The current node pointer might be nullptr, which means the new node gets inserted at the end.

Next, create a pointer to the node that comes before the new one. Remember, if the current node pointer is nullptr, that means the new node goes at the end of the list.

Now you have a pointer to the node that comes before (or nullptr if it goes at the beginning), and a pointer to the node that comes after (or nullptr if it goes at the end). Time to make some links!