// DoubleList.java

class DoubleList<Type> {
    // a Node of the list
    private class Node {
        public Type data;
        public Node next;
        public Node prev;
    }

    // we keep references to the first and last nodes
    private Node head;
    private Node tail;

    // the list starts empty
    public DoubleList() {
        head = null;
        tail = null;
    }

    // add an item to the start of the list
    public void addStart(Type item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = head;
        newNode.prev = null;
        if (tail == null) {
            tail = newNode;
        } else {
            head.prev = newNode;
        }
        head = newNode;
    }

    // add an item to the end of the list
    public void addEnd(Type item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.prev = tail;
        newNode.next = null;
        if (head == null) {
            head = newNode;
        } else {
            tail.next = newNode; 
        }
        tail = newNode;
    }

    // loop through the list forwards
    void print() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    // loop through the list backwards
    void printBackwards() {
        Node current = tail;
        while (current != null) {
            System.out.println(current.data);
            current = current.prev;
        }
    }

    // remove an item based on the value
    public void remove(Type item) {
        Node current = head;

        while (current != null) {
            if (current.data.equals(item)) {
                // remove current from list
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    head = current.next;
                }

                if (current.next != null) {
                    current.next.prev = current.prev;
                } else {
                    tail = current.prev;
                }
            }

            current = current.next;
        }
    }
}