Sorting a Linked List

[sgtledbetter]

I have the entire program written, but I can't figure out a way to sort the data structures by time. Any help or ideas would be very appreciated.
Here is my header file:

#ifndef ASSIGNMENT6_HEADER
#define ASSIGNMENT6_HEADER

#include <iostream>
#include <string>
#include <iomanip>
#include <stdlib.h>
using namespace std;

struct Appointment
{
       int hour;
       int minutes;
       string name;
       string complaint;
       Appointment *next;
};

class List
{
      private:
              Appointment *head;
      public:
List() { head = NULL; }
              
void insert (int a, int b, string c, string d)
{
     Appointment *newAppt;
     Appointment *ApptPntr;
     newAppt = new Appointment;
     newAppt->hour = a;
     newAppt->minutes = b;
     newAppt->name = c;
     newAppt->complaint = d;
     newAppt->next = NULL;
     if(!head)
              head = newAppt;
     else
     {
              ApptPntr = head;
              while(ApptPntr->next)
                                ApptPntr = ApptPntr->next;
              ApptPntr->next = newAppt;
     }
}



void remove(string& RemoveName)
{
  Appointment *curr = head, *prev = NULL;

  while (curr && !(curr->name == RemoveName))
  {
     prev = curr;
     curr = curr->next;
  }

  if (curr)
  {
    if (! prev)
      head = curr->next;
    else
      prev->next = curr->next;
    delete curr;
    cout << RemoveName << " has been removed.\n";
  }
  else
    cout << "Item to be removed not found\n";
}      

Appointment *get_head() { return head; }

};

#endif 

And this is the main program file:

#include "assignment6.h"
#include <string>
#include <iostream>
#include <iostream>
#include <string>
#include <iomanip>

main()
{   
    List X;
    int newhour; 
    int newminutes;
    string newname; 
    string newcomplaint;
    char cont, cont2;
    Appointment *p = X.get_head();
    cout << "Appointment Book" << endl << endl;
    cout << "Enter a new Appointment? Enter y or n.\n";
    cin >> cont;
    while (cont == 'y' || cont == 'Y')
    {
          cout << endl;
          cout << "Enter the hour of the appointment. Entry must be between 08 and 16.\n";
          cin >> newhour;
          while (newhour < 8 | newhour > 16)
          {
                      cout << endl << "Hour must be entered as a number between 08 and 23.\n";
                      cout << "Enter the hour of the appointment.\n";
                      cin >> newhour;
          }
          cout << endl << "Enter 00, 15, 30, or 45 for the minute slot of the appointment.\n";
          cin >> newminutes;
          while (newminutes % 15 != 0)
          {
                         cout << endl << "You must enter the minute slot you want as 00, 15, 30, or 45.\n";
                         cout << "Enter the new minute slot.\n";
                         cin >> newminutes;
          }
          cout << endl << "Enter the Patient's Last Name.\n";
          cin >> newname;
          cout << endl << "Enter the Patient's complaint.\n";
          cin >> newcomplaint;
          X.insert(newhour, newminutes, newname, newcomplaint);
          p = X.get_head();
          int ct = 0;
          while(p)
          {   
              if(p->hour == newhour && p->minutes == newminutes)
              {
                 ++ct;
                 p = p->next;
              }
              else
                 p = p->next; 
          }    
          if(ct == 2)
              {
                     cout << "This appointment is already taken. Please Try again.\n";
                     X.remove(newname);
              }
          cout << endl << "Would you like to enter another new appointment? Enter y or n.\n";
          cin >> cont;
    }
    string removename;
    cout << endl;
    cout << "Would you like to remove an appointment? Enter y or n.\n";
    cin >> cont2;
    while (cont2 == 'y' || cont2 == 'Y')
    {
          cout << endl << "Enter the last name of the patient to remove from the schedule.\n";
          cin >> removename;
          X.remove(removename);
          cout << endl << "Remove another appointment? Enter y or n.\n";
          cin >> cont2;
    }
    cout << endl << "The schedule for today is: \n";
    p = X.get_head();
    while (p)
    {
          cout << endl << "Time: " << p->hour << ":" << p->minutes << endl;
          cout << "Patient Name: " << p->name << endl;
          cout << "Complaint: " << p->complaint << endl;
          cout << endl;
          p = p->next;
    }
    return 0;
}

[Zaita]

Ok. This is How I would do it; I am bit unconventional even at the best of times.

1. Create new function called sort.
2. Create new pointer of type Appointment and point this to the head Object.
3. Move the Class Pointer of Head to 0 (NULL).

Note: At this point you have moved your entire Linked List into another pointer. So you are free to rebuild the class's member pointer with your sorted list.

4. Loop through the local list finding the highest/lowest time value you want to use (with time, it's easiest to compare it in reverse e..g MSSSMMHHDDMMYY as this makes it numerically comparable).

5. Add the first value into the class pointer, remove it from the local linked list. Rinse, and Repeat.

Hopefully that makes sense. It's a very simple way to sort your list without having to allocate or de-allocate any memory. So it's going to be highly efficient.

Just remember when removing from the Locally created Linked List to fill in the Next* pointer to the following element so you don't end up with gaps.

Any questions?

[sgtledbetter]

I'm a bit of a newbie. Can you give me an example of how to write the code? This is the first time I've worked with nodes in a linked list, and I'm not really sure what you mean.