#include 
#include 
using namespace std;

struct sNode {
  string data;
  sNode *next;
};

class List {
public:
  List();
  void insert(string word);
  void print();
private:
  sNode *head;
};

List::List() {   head = NULL; }

void List::print() {
  sNode *cur = head;
  while (cur != NULL) {
    cout << cur->data << '\t';
    cur = cur->next;
  }
  cout << endl;
}

void List::insert(string word) {
  sNode *temp = new sNode; // ignore memory problems
  temp->data = word;
  temp->next = NULL;



  // check for and insert into empty list
  if (head == NULL) { 
    head = temp;   
    return;
  }

  // check for and insert into 
  // beginning of list of the list
  if (word < head->data) {
    temp->next = head;
    head = temp;
    return;
  }

  // otherwise insert it somewhere into the list
  // after the first node
  sNode *prev = head;
  sNode *cur  = head->next;

  // find the node to insert word before
  while (cur != NULL) {
    if (word < cur->data) { // insert word before cur
      prev->next = temp;
      temp->next = cur;
      return;
    }
    prev = prev->next;
    cur = cur->next;
  }

  // insert node into end of list
  prev->next = temp;
}

int main() {
  List l;

  l.insert("ham");
  l.print();
  l.insert("tang");
  l.print();
  l.insert("clam");
  l.print();
  l.insert("spam");
  l.print();
  return 0;
}