#include <iostream>

using namespace std;

// finding, adding and deleting items from linked list of char

class node
  {
  public:
    char item;                               // content
    node* link;                              // ptr to next node
    node();                                  // default constructor
    node(char, node*);                       // another constructor
  private:
    friend class list;                       // 'list' fns can see all of node
    friend ostream& operator<< (ostream &, const node &);  // overloaded print op.

  };
  
class list
  {
  public:
    node* head;                              // ptr to head of list
    list();                                  // default constructor
    list(const char[]);                      // another constructor
    ~list();                                 // destructor
    list(const list& in_list);               // copy constructor
    list& operator=(const list& in_list);    // overloaded asgt op

         // add item after first occurence of 'after'
    bool add_iter(char new_item, char after);

         // delete first occurence of item
    bool del_iter(char del_item);

  private:
    friend ostream& operator<< (ostream &, const list &);  // overloaded print op.
    void reset();                            // reset to null
  };
  
// ***********************************


int main() 

{

  list list3("");
  cout << "list is " << list3 << endl << endl;

  list3.add_iter('a', 'x' );
  cout << "list is " << list3 << endl << endl;

  list3.add_iter('d', 'a');
  cout << "list is " << list3 << endl << endl;

  list3.add_iter('b', 'a');
  cout << "list is " << list3 << endl << endl;

  list3.add_iter('c', 'b');
  cout << "list is " << list3 << endl << endl;

  list3.add_iter('x', 'y');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('x');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('b');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('a');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('d');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('c');
  cout << "list is " << list3 << endl << endl;

  list3.del_iter('x');
  cout << "list is " << list3 << endl << endl;

  return 0;
}

  
// ***********************************

list::list()                        // default constructor
  {
    head = 0;
  }

list::list(const char* in_str)          // another constructor
  {
    int sub;
    node* p = 0;
    node* prev_p;

    head = 0;
    for (sub = 0; sub < strlen(in_str); sub++)
      {
	prev_p = p;
	p = new node(in_str[sub], 0);
	if (sub == 0)
	  head = p;
        else
          prev_p -> link = p;
      }

  }

list::~list()                       // destructor
  {

    if (head != 0)                        // reset list to null
      reset();

  }

void list::reset()                       // reset list to null
  {
    node* p;
    node* p_next;

    if (head != 0)
      {
        p = head;
        while (p != 0)
          {
	    p_next = p -> link;     // get next link while it's still available
            delete p;
	    p = p_next;
          }
        cout << endl;
        head = 0;
      }
  }

list::list(const list& in_list)            // copy constructor
  {
    node* p;
    node* q;
    node* prev_q;

    head = 0;
    if (in_list.head != 0)
      {
	p = in_list.head;
	while (p != 0)
	  {
	    q = new node(*p);        // get new node, copy data members
	    q -> link = 0;           // ... zero out new link,
            if (head == 0)           // ... and make someone point to it
	      head = q;
            else
	      prev_q -> link = q;
	    p = p -> link;
	    prev_q = q;
	  }
      }
  }

list& list::operator=(const list& in_list)    // overloaded asgt op
  {
    node* p;
    node* q;
    node* prev_q;

    if (this != &in_list)                        // Make sure not same object
     {

       if (head != 0)                            // free old result
         reset();

       if (in_list.head != 0)
	 {
	   p = in_list.head;                     // create & fill new list
	   while (p != 0)
	     {
	       q = new node(*p);        // get new node, copy data members
	       q -> link = 0;           // ... zero out new link,
               if (head == 0)           // ... and make someone point to it
	         head = q;
               else
	         prev_q -> link = q;
	       p = p -> link;
	       prev_q = q;
	     }
	 }
     }
    return *this;                          // return ref for chained asgt
  }

ostream& operator<< (ostream& ostr, const list& in_list)
{
  node* p;

  p = in_list.head;
  if (p == 0)
    cout << "empty";
  while (p != 0)
    {
      ostr << *p;
      p = p -> link;
    }

  return ostr;
}

node::node()                        // default constructor
  {
    link = 0;
  }

node::node(char in_item, node* in_link)          // another constructor
  {
    item = in_item;
    link = in_link;
  }

ostream& operator<< (ostream& ostr, const node& in_node)
{
  ostr << in_node.item;

  return ostr;
}

bool list::add_iter(char new_item, char after)
{
// add 'new_item' to list after 'after':

// if list is empty, add new_item to list
// else
// if 'after' in list
//    add new_item after 'after'
//    else
//    return false

  node* new_node;
  node* p;

  cout << "attempt to add " << new_item << " after " << after << endl;

  if (head == 0)
    {
      cout << "empty list, OK" << endl;
      new_node = new node;
      new_node -> item = new_item;
      new_node -> link = 0;
      head = new_node;
      return true;
    }

  p = head;
  while (p != 0)
    {
      if (p -> item == after)
	{
	  new_node = new node;
	  new_node -> item = new_item;
	  new_node -> link = p -> link;
	  p -> link = new_node;
          return true;
	}
      p = p -> link;
    }
  cout << after << " not found, nothing added" << endl;
  return false;
}


bool list::del_iter(char del_item)
{
// delete first instance of 'new_item' from list:

// if list is empty or item is not found, return false

  node* p;
  node* q;

  cout << "attempt to delete " << del_item << endl;

  if (head == 0)
    {
      cout << "empty list, can't delete" << endl;
      return false;
    }

  if (head -> item == del_item)
    {
      cout << "deleting first item" << endl;
      head = head -> link;
      return true;
    }

  p = head -> link;
  q = head;
  while (p != 0)
    {
      if (p -> item == del_item)
	{
	  cout << "deleting " << del_item << endl;
	  q -> link = p -> link;
          delete (p);
          return true;
	}
      q = p;
      p = p -> link;
    }
  cout << del_item << " not found, nothing deleted" << endl;
  return false;
}