Lists.java

package u5a1;

import java.util.NoSuchElementException;
import list.List;

public class Lists {	
	/**
	 * Returns a string representation of the list.
	 * 
	 * @return a comma-separated list of the list values
	 */
	public static String toString(List list)
	{
		if (list == null) return "null";
		
		StringBuffer buf = new StringBuffer();
		buf.append(list.value).append(", ").append(toString(list.next));
		return buf.toString();
	}
	
	/**
	 * Adds a value to at the beginning of a list.
	 * 
	 * @param list the list to which the value is added
	 * @param value the value which is added to the list
	 * @return a new list with the new element first followed by the given list
	 */
	public static List add(List list, int value)
	{
		return new List(value,list);
	}
	
	/**
	 * Retrieves the size of a list.
	 * 
	 * @param list the list in question
	 * @return the number of values in the list.
	 */
	public static int size(List list)
	{
		if(list==null) return 0;
		return size(list.next) + 1;
	}

	/**
	 * Aggregates the sum of all list values.
	 * 
	 * @param list the list in question
	 * @return the sum of all list values
	 */
	public static int sum(List list)
	{
		if(list==null) return 0;
		return list.value + sum(list.next);
	}	

	/**
	 * Retrieves the last element of a list.
	 * 
	 * The last element of the empty list is the empty list.
	 * 
	 * @param list the list in question.
	 * @return the last element of the given list.
	 */
	public static List last(List list) 
    {
		if(list == null) return list;
		if(list.next == null) return list;
		return last(list.next);
	}

	/**
	 * Retrieves a sublist of a list.
	 * 
	 * @param list the list in question
	 * @param index a position in the list starting at zero for the head value
	 * @return the sublist with the element indexed by index as head element
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
		if(size(list)<index || index < 0) throw new IndexOutOfBoundsException();
		if(index==0) return list;
		return sublist(list.next,index-1);
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
		if(size(list)-1<index || index < 0) throw new IndexOutOfBoundsException();
		if(index==0) return list.value;
		return valueAt(list.next,index-1);
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
		if(list==null) throw new NoSuchElementException();
		if(list.value == value) return 0;
		return index(list.next,value) + 1;
	}
}

MutableLists.java

package u5a2;

import list.List;
import u5a1.*;
public class MutableLists {
	/**
	 * Appends a value at the end of a list.
	 * 
	 * @param list the list in question; may not be empty
	 * @param value the value which is appended
	 * @throws IllegalArgumentException if list is empty
	 */
	public static void append(List list, int value) throws IllegalArgumentException
	{
		if(list==null) throw new IllegalArgumentException();
		Lists.last(list).next = new List(value,null);
	}
	
	/**
	 * Concatenates two lists.
	 * 
	 * @param head the list to which the other list is appended; may not be empty
	 * @param tail the list which is appended to the other list
	 * @throws IllegalArgumentException if head is empty
	 */
	public static void concat(List head, List tail) throws IllegalArgumentException
	{
		if(head == null) throw new IllegalArgumentException();
		Lists.last(head).next = tail;
	}

	/**
	 * Inserts a new value into a list at an arbitrary position.
	 * 
	 * @param list the list into which the value is inserted.
	 * @param index the position after which the given value is inserted, starting with zero for the head
	 * @param value the value which is added
	 * @throws IndexOutOfBoundsException if the position is greater than the size of the list
	 */
	public static void insertAt(List list, int index, int value) throws IndexOutOfBoundsException
	{
		if(Lists.size(list)-1<index || index < 0) throw new IndexOutOfBoundsException();
		if(index==0){
			list.next = new List(value, list.next);
		}
		else{
			insertAt(list.next,index-1,value);
		}
	}
	
	/**
	 * Inserts a list into a list at an arbitrary position.
	 * 
	 * @param list the list into which the other list is inserted.
	 * @param index the position after which the other list is inserted, starting with zero for the head
	 * @param newList the list which is inserted into the other list
	 * @throws IndexOutOfBoundsException if the position is greater than the size of the list
	 */
	public static void insertAt(List list, int index, List newList) throws IndexOutOfBoundsException
	{
		if(Lists.size(list)-1<index || index < 0) throw new IndexOutOfBoundsException();
		if(index==0){
			if(newList == null){
				list.next = null;
			}
			else{
				List tmp = list.next;
				list.next = newList;
				Lists.last(newList).next = tmp;
			}
		}
		else{
			insertAt(list.next,index-1,newList);
		}
	}

	/**
	 * Removes a value from a list
	 * 
	 * @param list the list from which the value is removed. 
	 * After the operation the state of this list is undefined.
	 * Don't use it any more. Use the returned list instead.
	 * @param index the position of the value which is removed, starting with zero for the head
	 * @return the list with the required value removed
	 * @throws IndexOutOfBoundsException if position is greater than the size of the list
	 */
	public static List remove(List list, int index) throws IndexOutOfBoundsException
	{
		if(Lists.size(list)-1<index || index < 0) throw new IndexOutOfBoundsException();
		if(index == 0){
			return list.next;
		}
		else{
			List tmp = Lists.sublist(list, index + 1);
			insertAt(list,index-1,null);
			concat(list,tmp);
			return list;
		}
	}
}

SortedLists.java

package u5a3;

import list.List;
public class SortedLists {
	/**
	 * Inserts a value into a sorted list so that the resulting list is still sorted.
	 * The sort order is ascending.
	 * 
	 * @param list a sorted list. 
	 * After the operation the state of this list is undefined.
	 * Don't use it any more. Use the returned list instead.
	 * @param value the value which is inserted into the list
	 * @return
	 */
	static List save = null;
	static int it = 0;
	public static List insertSorted(List list, int value)
	{
		if(list == null){
			return new List(value,null);
		}
		if(list.value >= value){
			List tmp = new List(value,list);
			return tmp;
		}
		if(list.next == null){
			list.next = new List(value,null);
			if(it != 0){
				it = 0;
				return save;
			}
			return list;
		}
		if(list.next.value >= value ){
			List res = new List(value,list.next);
			list.next = res;
			if(it != 0){
				it = 0;
				return save;
			}
			return list;
		}
		else{
			if(it == 0) save = list;
			it++;
			return insertSorted(list.next,value);
		}
	}
	
	/**
	 * Sorts a list in ascending order.
	 * 
	 * @param list the list which is sorted.
	 * After the operation the state of this list is undefined.
	 * Don't use it any more. Use the returned list instead.
	 * @return the sorted variant of the given list
	 */
	static List sorted = null;
	static int itSort = 0;
	public static List sort(List list)
	{	
		if(itSort == 0) sorted = null;
		if(list == null){
			itSort = 0;
			return sorted;
		}
		else{
			itSort++;
			sorted = insertSorted(sorted, list.value);
			return sort(list.next);
		}
	}
}

Stack.java

package u5a4;

import java.util.EmptyStackException;

import list.List;
import u5a1.Lists;

/**
 * Dynamically growing stack.
 */
public class Stack {
	private List list;

	/**
	 * Creates a new stack
	 */
	public Stack()
	{
		list = null;
	}

    /**
	 * Converts the stack to a string representation.
	 * 
	 * @return A ", "-separated list of the numbers, enclosed in square brackets. Top  numbers come first. 
	 */
	public String toString() 
	{
		StringBuffer buf = new StringBuffer("[");
		if (list != null) {
			buf.append(list.value);
			toString(list.next, buf);
		}
		buf.append("]");
		return buf.toString();
	}
	
	private static void toString(List lst, StringBuffer buf)
	{
		if (lst == null) return;
		buf.append(", ");
		buf.append(lst.value);
		toString(lst.next, buf);
	}
	
	/**
	 * Pushes a number onto the top of this stack.
	 * 
	 * @param number the number which is pushed onto this stack. 
	 */
	public void push(int number)
	{
		list = Lists.add(list, number);
	}
	
	/**
	 * Removes the number at the top of this stack and returns it as the value of this function. 
	 * 
	 * @return The number at the top of this stack
	 * @throws EmptyStackException if this stack is empty
	 */
	public int pop() throws EmptyStackException 
	{
		if(list == null) throw new EmptyStackException();
		else{
			int tmp = list.value;
			list = list.next;
			return tmp;
		}
	}
	
	/**
	 * Looks at the number at the top of this stack without removing it.
	 * 
	 * @return the number at the top of this stack
	 * @throws EmptyStackException if this stack is empty
	 */
	public int peek() throws EmptyStackException
	{
		if(list == null) throw new EmptyStackException();
		else{
			return list.value;
		}
		
	}

	/**
	 * Tests if this stack is empty. 
	 * 
	 * @return true if and only if this stack contains no items; false otherwise.
	 */
	public boolean empty()
	{
		return (list==null);
	}
	
	/**
	 * Get the size of this stack.
	 * 
	 * @return the current number of items on this stack
	 */
	public int size() 
    {
		return Lists.size(list);
	}
}