// file MyList2
// Doubly linked lists. Separate List and Node classes, Beginning and
// end pointers. Shared Structures.

public class MyList2<T> {
   private MyNode2<T> first;
   private MyNode2<T> last;

   public boolean emptyList() { return (first==null); }

   public MyNode2<T> getFirst() { return first; }
   public void setFirst(MyNode2<T> x) { first=x; }
   public MyNode2<T> getLast() { return last; }
   public void setLast(MyNode2<T> x) { last=x; }

   public void addFirst(T x) {
       MyNode2<T> n = new MyNode2<T>();
       n.setValue(x);
       if (emptyList()) last=n; // this previously empty.
       else { 
          n.setNext(first);
          first.setPrev(n);
         }
       first = n;
      }
      
   public void addLast(T x) {
       MyNode2<T> n = new MyNode2<T>();
       n.setValue(x);
       if (emptyList()) first=n; // this previously empty.
       else { 
          n.setPrev(last);
          last.setNext(n);
         }
       last = n;
      }

    public MyNode2<T> nth(int n) {  // Find the Nth node. Uses 0-based indexing.
        MyNode2<T> w = first;
        int i = 0;
        while (i < n) {
            w = w.getNext();
            i++;
           }
        return w;
     }

      
    public MyNode2<T> locate(T x) {
        MyNode2<T> n = first;
        while (n != last) {
           if (n.getValue() == x) return n;
           else n=n.getNext();
          }
        if (last.getValue() == x) return last;
         else return null;
     }

// Add X after node A.

    public void addAfter(MyNode2<T> a, T x) {
        if (a==last) 
            addLast(x);
        else {
            MyNode2<T> n = new MyNode2<T>();
            n.setValue(x);
            n.setNext(a.getNext());
            a.getNext().setPrev(n);
            n.setPrev(a);
            a.setNext(n);
         } 
        }

// Add X before node A.
    public void addBefore(MyNode2<T> a, T x) {
        if (a==first) 
            addFirst(x);
        else { 
           MyNode2<T> n = new MyNode2<T>();
           n.setValue(x);
           n.setPrev(a.getPrev());
           a.getPrev().setNext(n);
           n.setNext(a);
           a.setPrev(n);
        } 
      }
    public void delete(MyNode2<T> d) {
        if (d==first) first=d.getNext();
          else d.getPrev().setNext(d.getNext());
        if (d==last) last=d.getPrev();
          else d.getNext().setPrev(d.getPrev());
       }

     public String toString() {
        if (first == null) return "[]";
        MyNode2<T> n=first;
        String s = "[";
        while (n.getNext() != null) {
           s = s + n.getValue().toString() + " ";
           n = n.getNext();
          }
         return s + n.getValue().toString() + "]";
   }

    public static void main(String[] args) {
        MyList2<String> l = new MyList2<String>();
        l.addFirst("The");
        l.addLast("time");
        l.addLast("is");
        l.addLast("come");
        System.out.println(l.toString());

        MyList2<String> m = new MyList2<String>();
        m.setFirst(l.nth(2));
        m.setLast(l.getLast());
        m.addLast("the");
        m.addLast("walrus");
        m.addLast("said");
        l.nth(2).setValue("has");
        System.out.println(l.toString());
        System.out.println(m.toString());
     }
}