/* linked lists in Java, first version. 

Assuming you've seen linked lists in C++ or some other language, here we
shall implement it in Java.  Please note the following:

1. Two classes are used: cell and list0. 'cell' is defined inside
   list0 so it cannot be easily referenced outside (though this is
   optional).  A basic 'cell' contains an item and a pointer to the
   next cell.  This is the most basic structure of linked lists.
   There are two constructors for cell, disambiguated by the number of
   parameters.  We can create a simple linked list of, say, strings,
   by calling new cell("hello",new cell "world",null).  The next
   pointer of the last cell is null.

2. The outer class is "generic" or "parameterized" by a type variable T.
   Anything declared inside <> represents a type.  The corresponding feature
   in C++ is template<classname T>  but there are fundamental differences.
   This allows us to implement linked lists of any data type:

   list0<String> A = new new list0<String>(); //creates list of strings
   list0<Integer> B = new list0<Integer>(); // creates list of Integer objects.

   We used "Integer" instead of "int" in the above because type variables in
   Java can only be instantiated by referenced types (types of objects).  
   Similarly, we will have to use "Double" instead of "double" for lists of
   floating point numbers.

3. The outer list0 class contains a pointer to the first cell called 'first',
   which is initially set to null.  The methods supported are push/pop for
   stack operations, append for queuing, length, contains (membership) and
   an operation that returns the nth element.  Of these, only push and pop
   are O(1), constant time, operations.  All other methods are O(n), linear
   time. 
*/



public class list0<T>
{

protected class cell    // interior class  ############
{
   T item;  //  item is "public" within same file
   cell next;
   public cell(T i, cell n) {item=i; next=n;}
   public cell(T i) {item=i; next=null; }
}// cell

    protected cell first = null;
    
    public list0()
    { first= null; }

    // first, assume no last or size:

    // add to the front value x
    public void push(T x)
    {
        first = new cell(x,first);
    }
    // delete from the front (and return value)
    public T pop()
    {
        if (first==null) throw new Error("empty stack");
        T answer = first.item;
	first = first.next;
	// C++ will require one more step
        return answer;
    }
    // find length of list
    public int length()
    {
        cell i = first;
	int cx = 0;
        while (i!=null)
	    { cx++;  i = i.next; }
	return cx;
    }
    // add to end of list:
    public void append(T x)
    {
	cell n = new cell(x);
	if (first==null) // special case
	    {
		first = n;
	    }
	else
	    {
		cell i = first;
		while (i.next!=null) i=i.next;
		i.next = n;
	    }
    }//append

    public String toString()  // overrides Object.toString
    {
	String ax = "";
	for(cell i=first; i!=null; i=i.next)
	    {
		ax = ax + i.item + " ";
	    }
	return ax;
    }

    // find and return nth element of list // not recommended
    public T nth(int n) // first element is 0th element
    {
	cell i = first;
	while (n>0 && i!=null) i = i.next;
	if (i!=null) return i.item;
	else throw new Error("no such value in list");
    }

    public boolean contains(T x)
    {
	boolean answer=false;
	cell i = first;
	while (i!=null && !answer)
	    { if (i.item.equals(x)) answer=true;
		i = i.next;
	    }
	return answer;
    }

    public boolean empty() // returns true if list is empty
    { return first==null; }

}//list0 class

/*
This type of linked list is best used for implementing stacks because
push/pop are O(1) operations:

list0<String> S = new list0<String>();
S.push("c");
S.push("b");
S.push("a");
while (!S.empty()) 
   System.out.print(S.pop()); // prints abc
*/