//package linkedLists;

/** Singly linked list with just a head storing strings*/
public class SLinkedList1 {

    private Node head;  //head node of the list
    private long size;  //number of nodes in the list
    
    /** Default constructor that creates an empty list */
    public SLinkedList1(){head=null; size=0;}

    /** add node to front of list containing the String s */
    public void addFront(String s){
	head = new Node(s,head);
	size++;
    }
	
    /**return the size of the list */
    public long size(){return size;}
	
    /**return the head of the list*/
    public Node getHead(){return head;}
	
    /**is the list empty?*/
    public boolean isEmpty(){return head == null;}	
	
    /** remove node from front of list */
    public void removeFirst() throws ListException {
	if (!isEmpty()){head=head.getNext(); size--;}
	else throw new ListException("attempted removal from an empty list");
    }
	
    /** is the string s in the list? */
    public boolean isPresent(String s){
	boolean found = false;
	Node cursor =head;
	while(cursor != null && !found){
	    found = cursor.getElement().equals(s);
	    cursor = cursor.getNext();
	}
	return found;
    }
	
    /** Add new value in non-decreasing order into list */
    public void insert(String s){
	if (head == null) addFront(s);                                  // <1>
	else if (s.compareTo(head.getElement()) <= 0)                   // <2>
	    head = new Node(s,head);
	else {
	    Node cursor = head;                                         // <3>
	    Node next = cursor.getNext();
	    while (next != null && s.compareTo(next.getElement()) <= 0){
		cursor = next; next = next.getNext();
	    }
	    cursor.setNext(new Node(s,next));
	}
	size++;                                                   
    }
	
	
    /** remove all nodes containing element with a given value */
    public void remove(String s){
	Node temp=head;
	Node prev=null;
	while(temp!=null){
	    if(temp.getElement().equals(s)){
		if (temp==head) removeFirst();
		else {prev.setNext(temp.getNext());size-=1;}}
	    else prev=temp;
	    temp=temp.getNext();
	}
    }
	
    /** String representation of list */
    public String toString(){
	Node cursor = head;
	String s = "(";
	while(cursor != null){
	    s = s + cursor.getElement();
	    cursor = cursor.getNext();
	    if (cursor != null) s = s + ",";
	}
	return s + ")";
    }

}