// ORDERED LINKED LIST
// Insertions and deletions done at the appropriate position.

#include "stdstuff.h"

class LNode {
public:
  int data;
  LNode *next;
  LNode () { data = 0; next = NULL; }
  LNode (int data, LNode *next) {
    this -> data = data; this -> next = next;
  }

};


int main () {


  LNode *head = NULL, *n /* new */, *p /* previous */, *c /*current */;
  int option, value;

  for (;;) {

    cout << "\nEnter option\n"
         << "  1 = insert\n"
         << "  2 = delete\n"
         << "  3 = list contents\n"
         << "  4 = quit\n"
         << "Option: ";
    cin >> option;

    switch (option) {

    case 1:

      cout << "\nEnter a value: ";
      cin >> value;
      p = NULL; c = head;
      while (c != NULL && c -> data < value) { // expression order important!
        p = c; c = c -> next;
      }
      n = new LNode (value, c);
      if (p == NULL) {
        head = n;
      } else {
        p -> next = n;
      }
      break;

    case 2:

      cout << "\nEnter a value: ";
      cin >> value;
      p = NULL; c = head;

      // PC walk until we find the value that we're looking for
      // or a bigger value
      while (c != NULL && c -> data < value) { // expression order important!
        p = c; c = c -> next;
      }

      if (c == NULL || c -> data != value) {
        cout << "That value is not on the list.\n";
        break;
      }

      if (p == NULL) { // was first value in list
        head = c -> next;
      } else { // was not first value in list
        p -> next = c -> next;
      }
      delete c;
      cout << "Value successfully deleted.\n";

      break;

    case 3:

      if (head == NULL) {
        cout << "\nThe list is empty.\n";
      } else {
        cout << "\nThe list contains:";
        for (c = head; c != NULL; c = c -> next) {
          cout << " " << c -> data;
        }
        cout << endl;
      }
      break;

    case 4:

      // no need to clean up the list as the program is about to terminate
      pause();
      return 0;

    }

  }


}