Ola!
Bom pessoal, estou com uma dúvida de como usar o método quicksort para uma lista duplamente encadeada.
Preciso de um método que faça mais ou menos isso:
Este, recebe uma Lista Duplamente Encadeada (no caso DLinkedList), e utilizando o método QuickSort, ele ordena esta lista.
Eu já vi o método quicksort, porém ele faz isto apenas com vetores normais.
Eu tinha uma ideia de fazer este método da seguinte forma: Ps.: este método fica dentro da classe DLinkedListpublic DLinkedList<E> ordenaDLinkedList(DLinkedList<E> dll){
int sizedll = (int) dll.size; //número de nós da lista
DNode<E> current = head; //auxiliar para percorrer a lista duplamente encadeada
E[] vetor = new E[sizedll]; //esta linha não compila, diz o seguinte "Cannot created generic array of E"
for(int i = 0;i<vetor.length;i++ , current = current.getNext()){ //este for pegaria cada elemento da lista e adicionaria em uma posição do array
vetor[i] = current.getElement(); //atribui nó ao indice i do vetor
}
QuickSort.sort(dll); //chamando o método quicksort ele ordenaria o array
current = tail; // auxiliar que neste caso fica sendo o último nó da lista duplamente encadeada
DLinkedList<E> ordenada = new DLinkedList<E>(); //lista que ficara ordenada
for(int i = vetor.length;i>0;i--,current=current.getPrevious()){ //atribui os valores do vetor ordenado para a nova lista
ordenada.addFirst(vetor[i]);
}
return ordenada; //retorna a lista
}
Porém este método não funciona, devido ao erro da linha 4.
Alguém têm sugestões de como eu póssa fazer?
Grato por enquanto...
Segue as classes da Lista Duplamente Encadeada e o restante que é necessário para ela.
public class DLinkedList<E> {
protected DNode<E> head; //nodo cabeça da lista
protected DNode<E> tail; //nodo cauda da lista
protected long size; //número de nodos da lista
public DLinkedList() {
size = 0;
head = tail = null;
}
public boolean isEmpty() {
return head == null;
}
public E getFirst() throws UnderflowException {
if (isEmpty())
throw new UnderflowException();
return head.getElement();
}
public E getLast() throws UnderflowException {
if (isEmpty())
throw new UnderflowException();
return tail.getElement();
}
public void addFirst(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
if (isEmpty()) {
head = tail = n;
} else {
head.setPrevious(n);
n.setNext(head);
head = n;
}
size++;
}
public void addLast(E insertItem) {
DNode<E> n = new DNode<E>(insertItem);
if (isEmpty()) {
head = tail = n;
} else {
tail.setNext(n);
n.setPrevious(tail);
tail = n;
}
size++;
}
public E removeFirst() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
E removedItem = head.getElement();
if (head == tail) {
head = tail = null;
} else {
head = head.getNext();
head.setPrevious(null);
}
size--;
return removedItem;
}
public E removeLast() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
E removedItem = tail.getElement();
if (head == tail) {
head = tail = null;
} else {
DNode<E> penultimo = tail.getPrevious();
tail = penultimo;
tail.setNext(null);
}
size--;
return removedItem;
}
public void print() {
System.out.println("Exibindo a lista:");
DNode<E> current = head;
while (current != null) {
System.out.println(current.getElement());
current = current.getNext();
}
}
public DNode<E> find(E key) {
DNode<E> current = head;
while (current != null) {
if (current.getElement().equals(key)) {
return current;
}
current = current.getNext();
}
return null;
}
public boolean addBefore(E el, E chave) {
DNode<E> current = find(chave);
if (current == null) {
return false;
} else if (current == head) {
addFirst(el);
return true;
} else {
DNode<E> n2 = new DNode<E>(el);
DNode<E> before = current.getPrevious();
before.setNext(n2);
n2.setPrevious(before);
n2.setNext(current);
current.setPrevious(n2);
return true;
}
}
public static void main(String args[]) {
DLinkedList<Integer> list = new DLinkedList<Integer>();
list.addLast(2);
list.addLast(4);
list.addLast(6);
list.addLast(1);
list.addLast(8);
list.addLast(9);
list.print();
/*try {
list.removeFirst();
} catch (UnderflowException e) {
e.printStackTrace();
}
list.print();*/
System.out.println(list.find(1));
System.out.println(list.addBefore(5, 6));
list.print();
}
} // end class List
public class DNode<E> {
private E element;
private DNode<E> next;
private DNode<E> previous;
public DNode(E element) {
this (element, null, null);
}
public DNode(E element, DNode<E> next, DNode<E> previous) {
super();
this.element = element;
this.next = next;
this.previous = previous;
}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public DNode<E> getNext() {
return next;
}
public void setNext(DNode<E> next) {
this.next = next;
}
public DNode<E> getPrevious() {
return previous;
}
public void setPrevious(DNode<E> previous) {
this.previous = previous;
}
public String toString() {
return "DNode [element=" + element + "]";
}
}
public class UnderflowException extends Exception {
public String toString() {
return "UNDERFLOW!";
}
}
