List.java [lista ordenada]

import java.lang.Comparable;
import java.util.Iterator;

public class List<E extends Comparable<E>> implements Iterable<E> {
    /**
     * Campos en la estructura interna o privada de la clase
     */
    private Node head;
    private int count;
    private Node tail;

    /**
     * Getter para count
     *
     * @return cantidad de elementos en la lista
     */
    public int getCount() {
        return this.count;
    }

    /**
     * Constructor por defecto
     */
    public List() {
        this.head = null;
        this.count = 0;
        this.tail = null;
    }


    /**
     * Agrega al principio
     * Este código puede y debe mejorarse
     *
     * @param item elemento que se agrega a la lista
     */
    public void AddFirst(E item) {
        // si esta vacía
        if (this.count == 0) {
            // se crea un nodo con el elemento a agregar
            // el nuevo nodo es el primero y el último
            this.head = this.tail = new Node(item, null, null);
            // incrementa la cuenta de elementos
            ++this.count;
        }
        else {
            // se crea un nodo con el elemento a agregar
            Node temp = new Node(item, null, null);
            // el siguiente del nuevo nodo es el actual primero
            temp.next = this.head;
            // el anterior del actual primero es el nuevo nodo
            this.head.prev = temp;
            // el nuevo nodo se convierte en el primero
            this.head = temp;
            // incrementa la cuenta de elementos
            ++this.count;
        }
    }


    public void BetterAddFirst(E item) {
        Node temp = new Node(item, this.head, null);
        if (this.count == 0) {
            this.tail = temp;
        }
        else {
            this.head.prev = temp;
        }
        this.head = temp;
        ++this.count;
    }


    /**
     * Agrega al final
     * Este código puede y debe mejorarse
     *
     * @param item elemento que se agrega a la lista
     */
    public void AddLast(E item) {
        if (this.count == 0) {
            // se crea un nodo con el elemento a agregar
            // el nuevo nodo es el primero y el último
            this.head = this.tail = new Node(item, null, null);
            // incrementa la cuenta de elementos
            ++this.count;
        }
        else {
            // se crea un nodo con el elemento a agregar
            Node temp = new Node(item, null, null);
            // el anterior del nuevo nodo es el actual último
            temp.prev = this.tail;
            // el siguiente del actual último es el nuevo nodo
            this.tail.next = temp;
            // el nuevo es ahora el último
            this.tail = temp;
            // incrementa la cuenta de elementos
            ++this.count;
        }
    }


    public void BetterAddLast(E item) {
        Node temp = new Node(item, null, this.tail);
        if (this.count == 0) {
            this.head = temp;
        }
        else {
            this.tail.next = temp;
        }
        this.tail = temp;
        ++this.count;
    }


    public void AddInOrder(E item) {
        if (this.count == 0) {
            // se crea un nodo con el elemento a agregar
            // el nuevo nodo es el primero y el último
            this.head = this.tail = new Node(item, null, null);
            // incrementa la cuenta de elementos
            ++this.count;
        }
        else {
            if (item.compareTo(this.head.item) <= 0) {
                // es menor o igual que el primero
                this.AddFirst(item);
            }
            else {
                if (item.compareTo(this.tail.item) > 0) {
                    // es mayor que el último
                    this.AddLast(item);
                }
                else {
                    Node skip = this.head;
                    for ( ; (skip != null) && (item.compareTo(skip.item) > 0); skip = skip.next) { }
                    // skip es null o el nodo cuyo valor es mas grande que item
                    if (skip == null) {
                        // esto no debería ocurrir por las dudas hacemos programación defensiva
                        throw new RuntimeException("Algo está mal en el orden de los elementos de la lista...");
                    }
                    else {
                        // se debe insertar antes de skip
                        Node temp = new Node(item, skip, skip.prev);
                        skip.prev.next = temp;
                        skip.prev = temp;
                        ++this.count;
                    }
                }
            }
        }

    }

    /**
     * Extrae y devuelve el primer elemento de la lista
     *
     * @return el elemento que se encuentra al principio de la lista
     * @exception Lista vacía
     */
    public E RemoveFirst() {
        if (this.count == 0) {
            throw new RuntimeException("La lista está vacía...");
        }

        // toma el elemento que está en el primer nodo
        E item = this.head.item;
        // avanza el primer nodo al siguiente
        this.head = this.head.next;
        // si no hay mas nodos
        if (this.head == null) {
            // vaciar la lista
            this.tail = null;
        }
        else {
            // suprimir la referencia al anterior en el actual primero
            this.head.prev = null;
        }
        // decrementa la cuenta de elementos
        --this.count;
        // regresar el elemento
        return item;
    }



    /**
     * Extrae y devuelve el último elemento de la lista
     *
     * @return el elemento que se encuentra al final de la lista
     * @exception Lista vacía
     */
    public E RemoveLast() {
        if (this.count == 0) {
            throw new RuntimeException("La lista está vacía...");
        }

        E item = this.tail.item;

        // si es el único nodo
        if (this.head.next == null) {
            // vacía la lista
            this.head = this.tail = null;
        } else {
            // accede al penúltimo nodo que ahora será el último
            this.tail = this.tail.prev;
            // anula la referencia al siguiente nodo
            this.tail.next = null;
        }
        // decrementa la cuenta de elementos
        --this.count;
        // regresa el elemento
        return item;

    }


    public boolean FindAndRemove(E item) {
        if (this.count == 0) {
            return false;
        }

        Node skip = this.head;
        for ( ; (skip != null) && !(item.compareTo(skip.item) == 0); skip = skip.next) { }
        // skip es null o el nodo cuyo valor es igual que item
        if (skip == null) {
            // no esta
            return false;
        }
        else {
            // se debe extraer el nodo skip
            if (skip.prev == null) {
                // es el primero
                this.RemoveFirst();
                return true;
            }
            else {
                if (skip.next == null) {
                    // es el último
                    this.RemoveLast();
                    return true;
                }
                else {
                    skip.prev.next = skip.next;
                    skip.next.prev = skip.prev;
                    skip.prev = skip.next = null;
                    return true;
                }
            }
        }
    }









    /**
     * Clase privada para los nodos de la lista
     */
    private class Node {
        /**
         * Campos en la estructura interna o privada de la clase
         */
        public E item;
        public Node next;
        public Node prev;

        /**
         * Constructor por defecto
         */
        public Node() {
            this(null, null, null);
        }

        /**
         * Constructor especializado
         *
         * @param item elemento a mantener en el nodo
         */
        public Node(E item) {
            this(item, null, null);
        }

        /**
         * Constructor especializado
         *
         * @param item elemento a mantener en el nodo
         * @param next referencia al siguiente nodo
         */
        public Node(E item, Node next) {
            this(item, next, null);
        }

        /**
         * Constructor especializado
         *
         * @param item elemento a mantener en el nodo
         * @param next referencia al siguiente nodo
         * @param prev referencia al nodo anterior
         */
        public Node(E item, Node next, Node prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }

        /**
         * Devuelve una cadena de texto que representa el contenido
         * del elemento que está en el nodo
         *
         * Esto es un ejemplo de "delegación"
         */
        public String toString() {
            return this.item.toString();
        }
    }



    @Override
    public Iterator<E> iterator() {
        return new MyIterator(this.head);
    }

    /**
     * Implementación de un iterador para la clase List
     *
     */
    private final class MyIterator implements Iterator<E> {
        private Node current;

        public MyIterator(Node start) {
            this.current = start;
        }

        @Override
        public boolean hasNext() {
            return this.current != null;
        }

        @Override
        public E next() {
            if (!this.hasNext()) {
                throw new RuntimeException("La lista está vacía...");
            }
            E item = this.current.item;
            this.current = this.current.next;
            return item;
        }

    }



}