Ordenamiento en linea en una lista simple.

ListaOrdenada_2019.java

package edu.upb.estalg.ordenacion.quiz4;

import java.util.Iterator;

public class ListaOrdenada_2019<T extends Comparable<T>> implements Iterable<T>{

    private Node first;
    private int N;

    private class Node {
        T item;
        Node next;
        Node(T dato, Node sig) {
            item=dato;
            next=sig;
        }
    }

    public void insert(T dato) {
        if (first==null) {
            // Si la lista esta vacia
            first = new Node(dato, null);
        }
        else {
            // Sino, buscar la posicion que le corresponde e insertarlo en la lista
            Node anterior = null;
            for(Node i=first; i!=null; i=i.next) {
                if (dato.compareTo(i.item)<0) {
                    // Aqui se debe insertar
                    if (anterior==null) {
                        first = new Node(dato, first);
                    }
                    else {
                        anterior.next = new Node(dato, anterior.next);
                    }
                    N++;
                    return;
                }
                anterior = i;
            }
            // Si es mayor a todos, se agrega al final
            anterior.next = new Node(dato, anterior.next);
        }
        N++;
    }

    public Iterator<T> iterator() {
        return new IteratorListaOrdenada();
    }

    private class IteratorListaOrdenada implements Iterator<T> {

        private Node pos = first;

        @Override
        public boolean hasNext() {
            return pos!=null;
        }

        public T next() {
            T item = pos.item;
            pos=pos.next;
            return item;
        }

    }


    public static void main(String[] args) {
        ListaOrdenada_2019<String> lista = new ListaOrdenada_2019<>();

        lista.insert("Perro");
        lista.insert("Gaviota");
        lista.insert("Gato");
        lista.insert("Ornitorrinco");
        lista.insert("Murcielago");
        lista.insert("Albatroz");
        lista.insert("Tiburon");

        System.out.println(lista.N);
        for(String s: lista)
            System.out.println(s);
    }


}