class Listnode<K,D> {
  K key;
  D data;
  Listnode<K,D> pred, succ;
  public Listnode(K k, D d) {
    key = k; data = d; pred = null; succ = null; }
  public void delete() {
    pred.succ = succ; succ.pred = pred; }
  public void copy(Listnode<K,D> n) {
    key = n.key; data = n.data; }
  void append(Listnode<K,D> newnode) {
    newnode.succ = succ; newnode.pred = this;
    succ.pred = newnode; succ = newnode; }
}

public class List<K,D> extends Dictionary<K,D> {
  Listnode<K,D> head;
  public List() {
    head = new Listnode<K,D>(null, null);
    head.pred = head.succ = head;
  }

  public void insert(K k, D d) {
    Listnode<K,D> n = findnode(k);
    if(n!=null) n.copy(new Listnode<K,D>(k, d));
    else head.append(new Listnode<K,D>(k, d));
  }

  public boolean iselement(K k) {
    return find(k) != null;
  }

  public void append(K k, D d) {
    head.pred.append(new Listnode<K,D>(k, d));
  }

  public void prepend(K k, D d) {
    head.append(new Listnode<K,D>(k, d));
  }

  Listnode<K,D> firstnode() {
    return head.succ;
  }

  Listnode<K,D> lastnode() {
    return head.pred;
  }

  Listnode<K,D> findnode(K k) {
    Listnode<K,D> n;
    head.key = k;
    for(n=head.succ; !n.key.equals(k); n=n.succ) ;
    head.key = null;
    if(n==head) return null;
    return n;
  }

  public D find(K k) {
    Listnode<K,D> n = findnode(k);
    if(n==null) return null;
    return n.data;
  }

  public void delete(K k) {
    Listnode<K,D> n = findnode(k);
    if(n!=null) n.delete();
  }

  public Iterator<K,D> iterator() {
    ListIterator<K,D> iter = new ListIterator<K,D>(this);
    return iter;
  }
}

class ListIterator<K,D> extends Iterator<K,D> {
  List<K,D> l;
  Listnode<K,D> n;
  public ListIterator(List<K,D> l) {
    this.l = l;
    n = l.head.succ;
  }
  public boolean more() { return n!=l.head; }
  public K key() { return n.key; }
  public D data() { return n.data; }
  Listnode<K,D> node() { return n; }
  public void step() { n = n.succ; }
  public void delete() {
    Listnode<K,D> temp = n;
    n.delete();
    n = temp;
  }
  public void append(K k, D d) { n.append(new Listnode<K, D>(k, d)); }    
  public void prepend(K k, D d) { n.pred.append(new Listnode<K, D>(k, d)); }
}