///////     File :  CharList.java    ///////
//  linked list objects

public class CharList
{ 
    public CharList() { }            // empty list constructor 
    public CharList(char c)  // list with first cell
    { head=new ListCell(c,null); }
    public ListCell first() { return head; } // first cell
    public ListCell last() // last cell
    {     ListCell p = head;
          while( p != null && p.next != null )
                 p =  p.next; 
          return(p);
    }
    public ListCell find(char c) // first item == c
    {   for( ListCell p = head; p!=null ; p = p.next )
           if( p.item == c )
               return(p);
        return(null);  // c not on list
    }
    public boolean substitute(char r, char s) // r for first s on list
    {     ListCell p = find(s);
          if( p == null ) return(false);     // s not on list
          p.item = r;
          return(true);
    }
    public int remove(char c) // c from entire list
    {     ListCell p = head;
          int count = 0;
          if ( p == null ) return(count);
          while (p.next != null)      // treat all but head cell
          {  if ((p.next).item == c)
             {   count++;
                 p.next = (p.next).next;
             }
             else
                    p = p.next;
          }
          if( head.item == c ) // treat head cell
          {  head = head.next;
             count++;
          }
          return(count);       // number of items removed
    }
    public int shorten(int n) // remove first n cells
    {    while (n-- > 0 && head != null)
             head = head.next;
         return(-n);
    }
    public void putOn(char c) // insert in front
    {  head = new ListCell(c,head);
    }
    
    public void insert(char c, ListCell e) // insert after cell
    {  e.next = new ListCell(c,e.next);
    }

    public void append(char c)  // insert at end
    {   insert(c, last()); }

    public boolean isEmpty() { return(head == null); }

    public String toString()
    {   return toString(head);  }

    public String toString(ListCell p)
    {   String s = "(";
        while ( p != null )
        {    s = s + p.item;
             if ( (p = p.next) != null ) s = s + " ";
        }
        return( s + ")");
    }
    private ListCell head = null;           // first cell of list
}

class ListCell
{  
    ListCell(char c, ListCell cell)
    { item=c; next=cell; }
    ListCell() { }
    char content() { return item; }

    char item = '\0';
    ListCell next = null;
}

class TestCharList
{
    public static void main(String[] args)
    {    CharList a = new CharList('B');
         a.putOn('A');
         a.append('D'); a.append('E'); a.append('F');
         System.out.println("a = " + a);
         ListCell lp = a.find('B');
         System.out.println(a.toString(lp));
         a.insert('C', lp);
         System.out.println("a = " + a);
         a.remove('E');
         a.shorten(2);
         System.out.println("a = " + a);
         a.remove('C');
         System.out.println("a = " + a);
    }

}