// ---------------------------------------------------------------------------
// Example of using Singly linked lists in C++ with Structs
// For 605.201, Introduction to C++ Programming, Summer 1997
// Paul McNamee
//
// Although somewhat different, see F&K section 14.3 for a similiar example.
// ---------------------------------------------------------------------------

#include <stdlib.h>
#include <iostream.h>

struct node {
    node *next;
    int item;         // We'll store lists of ints
};

// Add a new node to front of list, containing the int x.  Return pointer
// to new node, which is the head of the list.

node *Add_Node(node *list, int x) {
  node *p = new node;  // Make a new node
  p->next = list;
  p->item = x;
  // Don't delete p now!
  return p;
}

// Find the list node containing x and return it
node *Find_Item(node *list, int x) {
  node *p = list;        // p is a pointer pointing to the list
  while (p != NULL) {
    if (p->item == x)
      return p;
    p = p->next;
  }
  return NULL;             // To indicate failure.
}

// Find item *before* the list node containing x and return it
node *Find_Item_Before(node *list, int x) {
  // P will be the "parent" of q 
  node *p = list, *q = list;   // p and q point to the list
  while (q != NULL) {
    if (q->item == x)
      return p;
    p = q;
    q = q->next;
  }
  return NULL;             // To indicate failure.
}

// Similar to Find.  Print list until find a NULL pointer.
void Print_List(node *list) {
  node *p = list;        // p is a pointer pointing to the list
  cout << "Head:";
  while (p != NULL) {
    cout << " [" << p->item << "]" ; 
    p = p->next;
  }
  cout << " Tail." << endl;
  return;
}

// Delete node with x in it
node *Delete_Node (node *list, int x) {
  node *p = Find_Item_Before(list, x);
  // If p is NULL, item isn't in list, otherwise we want
  // to delete item
  if (p != NULL) {
    node *q;
    if ((p == list) && (p->item == x)) {
      // the node to be deleted is the 1st node
      q = p->next;
      delete p;
      return q;
    } else {
      q = (p->next)->next;  // q is the node after the item
      delete p->next;             // delete the item with x
      
      // p->next is now invalid (dangling pointer)
      p->next = q;                // Now done!
    }
  } else
    return list;                  // No deletion!
  return list;                    // Deletion
}

// Add new node with y, after occurance of x
node *Insert_After (node *list, int x, int y) {
  node *p = Find_Item(list, x);
  // If p is NULL, item isn't in list, other p is node containing x 
  if (p != NULL) {
    node *q = p->next;          // q is the node after the item
    p->next = new node;         // splice in new node
    (p->next)->next = q;        // attach rest of list
    (p->next)->item = y;        // put y in new node
    return p->next;             // Return pointer to node with y
  }
  return NULL;
}


// ---------------------------------------------------------------------------
// Let's test the code!

int main () {
  node *lst = new node;
  lst->item = 50;
  lst->next = NULL;

  Print_List(lst);
  
  cout << "Now I'll add a node with 4 to the front" << endl;
  lst = Add_Node(lst, 4);
  Print_List(lst);

  cout << "Now I'll add a node with -7 to the front" << endl;
  lst = Add_Node(lst, -7);
  Print_List(lst);

  cout << "Try to delete a node with 30 in it" << endl;
  lst = Delete_Node(lst, -30);
  Print_List(lst);

  cout << "Try to delete a node with 4 in it" << endl;
  lst = Delete_Node(lst, 4);
  Print_List(lst);

  cout << "Try to delete a node with -7 in it" << endl;
  lst = Delete_Node(lst, -7);
  Print_List(lst);

  delete lst;
  
  cout << "Done" << endl;
  return 1;
}

// ---------------------------------------------------------------------------
// Output:

// Head: [50] Tail.
// Now I'll add a node with 4 to the front
// Head: [4] [50] Tail.
// Now I'll add a node with -7 to the front
// Head: [-7] [4] [50] Tail.
// Try to delete a node with 30 in it
// Head: [-7] [4] [50] Tail.
// Try to delete a node with 4 in it
// Head: [-7] [50] Tail.
// Try to delete a node with -7 in it
// Head: [50] Tail.
// Done