// an instance of ListElt is one "link" in a linked list
class ListElt {
  public int item;
  public ListElt next;

  public ListElt(int i, ListElt n) {
    item = i;
    next = n;
  }
}

// linked list with elements of type int
class ListInt {
  public ListElt l;

  public ListInt() {
    l = null;
  }

  // check whether the list contains i
  public boolean contains(int i) {
    ListElt cur = l;
    while (cur != null) {
      if (cur.item==i) {
	return true;
      }
      cur = cur.next;
    }
    return false;
  }

  // insert i, if it's not already in l
  public void insert(int i) {
    if (!contains(i)) {
      l = new ListElt(i, l);
    }
  }

  // remove first occurrence of i from list.
  // if i does not occur in l, this has no effect.
  public void remove(int i) {
    if (l.item==i) {
      l = l.next;
    } else {
      ListElt prev = l;
      ListElt cur = l.next;
      while (cur!=null) {
	if (cur.item==i) {
	  prev.next=cur.next;
	  break;
	} else {
	  prev = cur;
	  cur = cur.next;
	}
      }
    }
  }

  // returns a String representing the contents of the list
  public String toString() {
    String t = "";
    ListElt cur = l;
    while (cur != null) {
      t = t + cur.item + " ";
      cur = cur.next;
    }
    return t;
  }
}

class Worker extends Thread {
  Shared shared;

  Worker(Shared s) {
    shared=s;
  }

  public void run() {
    int i;
    for (i=0; i<1000; i++) {
      shared.l.insert(i);
    }
    for (i=0; i<1000; i++) {
      shared.l.remove(i);
    }
    shared.finished++;
    if (shared.finished==hw1.numThreads)
      System.out.println("final list = " + shared.l);
  }
}

// a single instance of Shared is shared by all Workers
class Shared {
  ListInt l = new ListInt();
  // number of workers that finished
  int finished=0;
}

class hw1 {
  static final int numThreads=2;

  public static void main(String args[]) {
    Shared shared = new Shared();
    int i;

    for (i=0; i<numThreads; i++) 
      (new Worker(shared)).start();
  }
}