/*
A linked list is a data structure that can be viewed from many perspectives.

From an abstract perspective, it is an inductively defined,
mathematical structure.  In this setting we say that there are two
kinds of lists: 

    (base case): null is a list, the empty list
    (inductive case): new cell(n,L) is a list if n is an int 
                      and L is an existing list.  
    Each list have a "head" (the data stored there) and a "tail" that
    represents the rest of the list.

A more low-level view of linked list is that it consists of a series of
memory cells.  each cell consists of two parts:

      head:  the data stored in the cell
      tail:  the memory address (pointer) of the next cell.

"null" is the empty pointer, and so represents an empty cell.

These two views of linked lists are consistent, and you need to understand
both. 
*/

class cell
{

   private int head;
   private cell tail;

    // constructor
    cell(int h, cell t) { head=h;  tail=t; }

    /*
      To use the constructor to create a list of 4 integers, for example, we could use

      cell L = new cell(2, new cell(4, new cell(6, new cell(8, null))));

      The empty pointer null is used to represent the empty list.

      One subtle question that many beginning students get confused about is 

        "What is the tail of L?".

      The "head" of L is the data stored in the cell, in this case 2.
      BUT THE TAIL OF L IS NOT 4!!!

      The tail of L POINTS TO THE REST OF THE LIST, that is,

      L.tail is the list

         new cell(4, new cell(6, new cell(8, null)));

      One rule that will help you to understand the structure of lists intuitively
      is to read the above expression INSIDE-OUT.  That is, starting with null,
      we create a new cell with 8 at the head.  Then, given this cell, we can
      create another cell with 6 as the head, etc ... 

         What's WRONG with the following expressions?

         int x = L.head.tail;   

             (L.head is an int, not a cell; it doesn't have a tail)
      
         cell a = L.tail.head;  

             (L.tail.head is the second INT in the list; it's not a cell)


         if (L.head == null) {...}

             (L.head is an int, not a pointer to a cell, 
              so it can't be compared with null)

         L.tail.tail.tail.tail.head

            (L.tail.tail.tail.tail is null, which doesn't have a head)

    
You must think hard about this.  Understanding lists in the wrong way is as bad as
not understanding it at all.  

*/

    // Now we define some basic operations on lists

    // The following "accessor methods" offers read-only access to
    // the head and tail from outside of the cell class:

    public int head() { return head; }
    public cell tail() { return tail; }

    // length counts the number of elements in the list
    public int length()
    {
	cell i = this;    // "this" refers to the object the function is invoked on
        int answer = 0;
	while (i!=null) { answer++; i=i.tail; }
	return answer;
    }

    // find the largest number in the list
    // compare this to the arrays version
    public int largest()
    {
	int answer = this.head;
	cell i = this.tail;
	while (i!=null)
	    {
		if (i.head > answer) answer = i.head;
		i = i.tail;
            }
	return answer;
    }//largest

    // determining if an int appears in a list
    public boolean member(int x)
    {
	boolean answer = false;
	cell current = this;
	while (current != null && !answer)
	    {
		answer = (x == current.head);
		current = current.tail;
	    }
	return answer;
    }

    // determine if x is inside list A, functional, recursive style
    public static boolean member(int x, cell A)
    {
	return (A!=null && (x==A.head || member(x,A.tail)));
    }


    // returns a string representation of list starting at "this"
    public String toString()
    {
	String s = ""; // string to be built
	cell current = this;
	while (current != null)
	    {
		s = s + current.head+" "; 
		current = current.tail;
	    }
	return s;
    } // toString


    ////////////////////// functions from 10/11 class:  ***********

    // sum of all the numbers
    public int sum()
    {  int ax = 0;
       cell i = this;
       while (i!=null) 
	   {  ax += i.head;
   	      i=i.tail; 
	   }
       return ax;
    } 

    //adding a cell to the END of a list:
    public void addToEnd(int x)
    {
	// first, we have to find the last cell:
	cell current = this;
	while (current.tail != null) current = current.tail;
	current.tail = new cell(x,null);
    }

    // adding a cell to the front is actually trickier!
    public cell addToFront(int x)
    { return new cell(x,this); }
    /*
      Why does addToFront return a value and addToEnd does not?  You must
      understand pointers carefully here.  When we're given a "cell", we're
      not just looking at one cell containing one piece of data, but the
      the starting point of an entire list.  AddToEnd changes the last cell
      of the list to a new cell, thereby extending the list.  The first cell
      with which we use to access the entire list DOES NOT CHANGE.

      In contrast, addToFront needs to create a completely new first
      cell.  Thus, technically it's not just making one cell but a new
      way to access an entire list.  Whoever calls addToFront need to
      have access to this new front-of-the-list cell that was created.
      In other words, instead of just calling

             A.addToFront(x);

      You must do
 
             A = A.addToFront(x);
    */


    // the following function returns the nth cell of a list,
    // it returns null if there is no such cell.
    // the 0th element is the first cell of a list (this)
    public cell nthcell(int n)
    {
	cell current = this;
	while (n>0 && current !=null) { current=current.tail; n--; }
        return current;
    }

    // the above method is written in the oop style, the following
    // static version uses the functional style, where all data are
    // passed in as parameters:
    public static cell nth(int n, cell L)
    {
	cell current = L;
	while (n>0 && current !=null) { current=current.tail; n--; }
        return current;
    }
    // so to call the static version, you'll have to pass in the list
    // you want to look at also.  All of the methods here can be written
    // in either the functional or the oop style.  Recursive functions
    // are usually better with the functional style.  Also, since this
    // static function is really independent of any cell object, we didn't
    // really have to put it in the cell class.  However, if we put it
    // in another class, we won't have direct access to its private elements,
    // and would instead have to call the accessor methods head() and tail().
    // See the length function in the public class below for example.


    //reversing a list.  We start with a null list and add elements
    //in front of it in the manner of a stack.  This function is
    //"constructive" in the sense that it doesn't change the old list, 
    //but creating a new one.  

    public cell reverse()
    {
	cell ax = null; // our accumulator this time is an empty stack;
	cell i = this; // pointer to traverse the "this" list
	while (i!=null)
	    {
		ax = new cell(i.head, ax); // add element to front of ax
		i=i.tail;
	    }
	return ax;
    }
    // Although this function doesn't change the original list, you can
    // still fulfill that purpose with A = A.reverse();

   // static, recursive version of reverse; 
   // pass in null as initial value of ax:
   public static cell rev2(cell L, cell ax)
   {
      if (L==null) return ax; else return rev2(L.tail, new cell(L.head,ax));
   }



//////////////////// For 10/18 class

/* Now we get to the two critical operations on lists: insert and delete.
   There are several variations on these operations (for example, we can
   insert/delete by position, or by looking for a certain value).  However,
   they all have to mind the following subtleties:

      1. There is the potential that the first cell of the list may change,
         therefore the operations should always RETURN a value.
      2. The while loop should stop at a point right BEFORE the cell that's
         to be inserted/deleted.
*/

// insert element x at position n. if n is too big, add it to the end
public cell insertAt(int x, int n)
{
    // take care of special case first: adding cell to front of list 
    if (n==0) return new cell(x,this);
    cell current = this;  // we know current!=null since this is oop style
    while (current.tail !=null && n>1) {current=current.tail; n--;}
    current.tail = new cell(x,current.tail);
    return this; // the first cell doesn't change.
}

// delete nth cell from list, do nothing if n is too big.
public cell deleteAt(int n)
{
    if (n==0) return this.tail;     // special case, delete front cell
    cell current = this;
    while (current.tail!=null && n>1) {current=current.tail; n--;}
    // careful: at this point, current.tail might be null
    if (current.tail!=null) current.tail = current.tail.tail;
    return this;
}

// The following method implements another version of delete: we search
// for an integer x in a list that is assumed to be sorted (and unique),
// and delete the cell containing it

public cell deleteX(int x)
{
    // special case:
    if (this.head==x) return this.tail;
    cell i = this;
    boolean stop = false;
    while (i.tail!=null && !stop)
	{
	    if (i.tail.head == x)
		{
		    i.tail = i.tail.tail;
		    stop = true;
		}
	    else if (i.head > x) { stop = true; }
	    i = i.tail;
        }
}

// in another variation on delete, we construct a new list instead of
// destructively altering the old list.  In this version of delete, we
// delete all occurrences of the element x (all cells with head==x).  We
// use (like in the reverse example), an accumulator list (ax) that represents
// the new list we're trying to build.  We use another technique: to make
// sure that ax is not null, we first initialize it to a dummy cell, which
// we discard at the end.

public cell deleteAll(int x)
{
    cell i = this;  // "current" cell pointer
    cell ax = new cell(0,null);  // list to be built, with a dummy 1st cell
    cell lastax = ax; // moving pointer to keep track of end of ax list.
    while (i!=null)
	{
	    if (i.head!=x) 
		{
		    lastax.tail = new cell(x,null);
		    lastax = lastax.tail;
		}
	}
   return ax.tail; // discard dummy element
}//deleteAll


///// the above function works better with recursion:
public static cell deleteAll(int x, cell A)
{
    if (A==null) return null; 
    else if (A.head==x) return deleteAll(x,A.tail);
    else return new cell(A.head,deleteAll(x,A.tail));
}

// following up, we write a constructive function that returns a new list
// that represents the old list with all duplicate elements deleted:
public static cell remdups(cell A)
{
    if (A==null) return null;
    else return new cell (A.head,remdups(deleteAll(A.head,A.tail)));
}

// The key to understanding these functions is first to read INSIDE-OUT, and
// then accept that the recursive calls will give you the correct answers on
// the smaller data structure.  If you truly understand these two examples,
// and can write similar programs yourself, then you've basically mastered 
// recursion.


} // cell class

public class lists
{

    // recursive function to compute length of a list, outside of cell class:
    // Note that we need to say A.tail() instead of just A.tail since
    // tail is private and this function is outside of the cell class:
    public static int length(cell A)
    { if (A==null) return 0; else return 1+length(A.tail()); }

    public static void main(String[] args)
    {
	cell A = new cell(2,new cell(4,new cell(6,null)));
	cell B = new cell(3,new cell(5, new cell(8,new cell(9,null))));
	System.out.println(B.largest());
	System.out.println(A.length());
	System.out.println(cell.member(7,B));
	System.out.println(cell.rev2(B,null));
	B = B.insertAt(3,2);
	B = B.insertAt(9,0);
	System.out.println("B is now "+B);
	B = cell.remdups(B);
	System.out.println("after remdups, B is now "+B);
    } // main
}