public class DoubleList<T>{
    private DoubleNode<T> first, last;
    public DoubleList(){
        first=null;
        last=null;
    }

    public void addFirst(T o){
        DoubleNode<T> node=new DoubleNode<T>(o);
        node.setNext(first);
        node.setPrev(null);
        if (first != null)
            first.setPrev(node);

        first=node;
        if (last == null)
            last=node;
    }

    public void addLast(T o){
        if (first==null){
            addFirst(o);
        } else {
            DoubleNode<T> node=new DoubleNode<T>(o);
            node.setPrev(last);
            last.setNext(node);
            last=node;
        }
    }

    public void print(){
        for (DoubleNode<T> current=first; current!=null;
             current=current.getNext()){
            current.print();
        }

    }

    public void printReverse(){
        for (DoubleNode<T> current=last; current!=null; current=current.getPrev()){
            current.print();
        }

    }

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

    public T removeFirst(){
        if (first==null)
            throw new
                IllegalArgumentException(
                       "No first element");
        T retVal=first.getData();


        first=first.getNext();
        first.setPrev(null);
        return retVal;
    }

    public void removeLast(){
        if (first==null)
            throw new IllegalArgumentException("Empty");

        last=last.getPrev();
        if (last !=null)
            last.setNext(null);
        else
            first = null;
    }

    public void remove(T key) {
        DoubleNode<T> current=first;
        while (current != null && !current.getData().equals(key)){
            current = current.getNext();
        }

        if (current!=null) {
            remove(current);
        }
    }

    public void remove(DoubleNode<T> node) {
        if (node==first)
            first=node.getNext();

        if (node==last)
            last=node.getPrev();

        if (node.getNext()!=null)
            node.getNext().setPrev(node.getPrev());
        if (node.getPrev()!=null)
            node.getPrev().setNext(node.getNext());
    }


    public static void main(String[] args){
        DoubleList<String> test=new DoubleList<>();
        test.addLast("hello");
        test.addFirst("goodbye");
        test.addLast("are you still here");

        System.out.println("\nForward:");
        test.print();

        System.out.println("\nReverse:");
        test.printReverse();


        System.out.println("\nAfter Removing First:");
        test.removeFirst();
        test.print();


        System.out.println("\nAfter Removing Last:");
        test.removeLast();
        test.print();

        System.out.println("\nAfter Removing Last, again");
        test.removeLast();
        test.print();

        test.addLast("a");
        test.addLast("b");
        test.addLast("c");
        test.addLast("d");
        test.addLast("e");
        test.addLast("f");

        System.out.println("\nRebuilt list");
        test.print();

        test.remove("a");
        System.out.println("\n Remove first, by key");
        test.print();

        test.remove("c");
        System.out.println("\n Remove middle, by key");
        test.print();

        test.remove("f");
        System.out.println("\n Remove last, by key");
        test.print();

    }

}
//