// Search structure implemented as unsorted list
// sorting is pointless because you cannot do binary search anyway

class SearchList implements SearchStructure{
    private ListNode head;
    private int size;
    private ListNode current;  // set during search
    private ListNode previous; // set during search
    
    public SearchList() { }

    private class ListNode {
        public Object item;
        public ListNode next;
        public ListNode(Object o, ListNode n) {
            item = o;
            next = n;
        }
        public String toString() {
            String temp = item.toString();
            if (next != null) 
                temp += " " + next.toString();
            return temp;
        }
    }

    public void insert(Object o) {
	// if o is not already in list
	if (!search(o)) {
	    // stick into head of list:
	    head = new ListNode(o,head);
	    size = size + 1;
	}
    }
    
    // remove objects equal to o 
    public void delete(Object o) {
	// If not in list, nothing to do:
	if (!search(o)) 
	    return;
	// Otherwise, use the two cursors current and previous
	// we know that current is non-null
	// previous will be null if element to be deleted is first in list
	if (previous == null) {
	    // need to remove first element of list (see search method)
	    head = head.next;
	}
	else // splice out current element of list
	    previous.next = current.next;
	// Account for deleted node:
	size = size - 1;
    }
    
  // linear search for node with item o:
  public boolean search(Object o) {
      // walk down the list
      // set current and previous cursors while walking
      current = head;
      previous = null;
      while (current != null) {
	  Comparable item = (Comparable)(current.item);
	  if (item.compareTo(o) == 0) 
	      return true;
	  else {
	      previous = current;
	      current = current.next;
	  }
      }
      return false;
  }


    public int size() {
	return this.size;
    }
    
    public String toString() {
	return head.toString();
    }
}


public class TestSearchList {
    public static void main(String[] args) {
	SearchList s = new SearchList();
	s.insert(new Integer(5));
	s.insert(new Integer(1));
	s.insert(new Integer(2));
	s.insert(new Integer(5));
	System.out.println(s);
	s.delete(new Integer(5));
	System.out.println(s);
	System.out.println(s.size());
	System.out.println(s.search(new Integer(1)));
    }
}