por Slek VIP
Cuando se trata de ordenar listas enlazadas (LinkedList), la forma más eficiente de hacerlo es utilizando [Enlace externo eliminado para invitados]. Podemos aprovechar las propiedades de las listas enlazadas para realizar todas las operaciones necesarias en tiempo constante. Por tanto, el algoritmo tendrá complejidad en tiempo O(n Log n) y en espacio O(n).

He implementado una lista enlazada que cumple con estas características, SimplyLinkedList. Esta implementación difiere de una implementación estándar en dos métodos:

1. Permite añadir todos los elementos de una SimplyLinkedList a otra, en tiempo constante.

Código: Seleccionar todo

	public void add(SimplyLinkedList<T> l){
		Node n = last.next;
		
		n.next = l.first.next;
		l.first.next = null;
		last.next = l.last.next;
		l.last.next = first;
		
		size += l.size;
		l.size = 0;
	}
2. Permite retirar el primer elemento de una SimplyLinkedList y añadirlo a otra, en tiempo constante y sin duplicar el objeto.

Código: Seleccionar todo

	public void peek(SimplyLinkedList<T> l){
		Node n = l.first.next;
		
		l.first.next = n.next;
		n.next = null;
		last.next.next = n;
		last.next = n;
		
		size++;
		l.size--;
	}
La implementación de la lista, es más bien una cola (Queue) enlazada. La clase SimplyLinkedList consta de dos atributos Node, uno apuntando al primer elemento, y otro al último. La clase Node representa un nodo de la lista enlazada, con dos atributos: el valor, y una referencia al siguiente nodo de la lista.

Restricciones: Se pueden añadir elementos al principio, y al final. Pero sólo se puede eliminar el primer elemento de la lista.

Adjunto el código completo, tanto el algoritmo Merge Sort como la clase SimplyLinkedList.
No tiene los permisos requeridos para ver los archivos adjuntos a este mensaje.
github.com/Slek-Z
Temas similares
Poo en java por Zion-92 en Java
ayuda en java NetBeans por guru1990 en Dudas y Preguntas
Variantes de tema
Responder

Volver a “Fuentes”