[code]public class DLinkedList {
protected DNode head; // nodo cabeça da lista
protected DNode 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;
}
}
} // end class List[/code][code]public class DNode {
private E element;
private DNode next;
private DNode 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 + "]";
}
}
[/code]
Na classe de Lista Dulplamente Encadeada (DLinkedList), preciso criar um método recursivo para realizar a Busca Binária de um determinado elemento E. Utilizando as seguintes assinaturas (público e privado):
[code]public DNode pesquisaSequencialR (E key) {
return pesquisaSequencialR(key, head);
}
private DNode pesquisaSequencialR(E key, DNode n){
}
[/code]
O método de pesquisa binária é
public static int pesquisaBinaria (int tab[], int arg) {
int inf, sup, med;
inf = 0; sup = tab.length-1;
while (inf <= sup) {
med = (inf + sup)/2; //divisão inteira
if (arg == tab[med]) return med;
else if (arg > tab[med]) inf = med + 1; // procura na 2a. metade
else if (arg < tab[med]) sup = med - 1; // procura na 1ª metade
}
return -1;
}
Como eu poderia transformá-lo para mexer com esta lista duplamente encadeada?
