Lista duplamente encadeada

Question

Considere que se tem a implementação de uma DoubleLinkedList com os métodos
size() — retornando um inteiro —, isEmpty() — retornando um booleano — e
getHead() e getLast() — retornando objetos da classe DoubleLinkedListNode, que,
por sua vez, possui os seguintes métodos: getData() — retornando uma string —,
isNIL() — retornando um booleano — e getNext() e getPrevious() — retornando
objetos da classe DoubleLinkedListNode. Escreva um método em Java que, dada uma
lista de strings do tipo DoubleLinkedList, indique se há ocorrências de uma determinada
string na lista. Comente o comportamento assintótico do seu método.

boolean haOcorrencia(DoubleLinkedList palavras, String p) {
//...
}

Ilze O. · Accepted Answer

boolean haOcorrencia(DoubleLinkedList palavras, String p) {   DoubleLinkedListNode current = palavras.getHead();   while (!current.isNIL()) {     if (current.getData().equals(p)) {       return true;     }     current = current.getNext();   }   return false; }  Este método percorre a lista encadeada da cabeça até a cauda, comparando cada elemento com a string p. Se a string p for encontrada, o método retorna true. Caso contrário, se a lista inteira for percorrida sem encontrar p, o método retorna false.  O comportamento assintótico deste método é O(n), onde n é o tamanho da lista encadeada. Isso ocorre porque, no pior caso, o método precisa percorrer toda a lista para verificar se a string p está presente ou não.

Lista duplamente encadeada

Um professor já respondeu

Envie suas dúvidas pelo App. Baixe agora

Precisa de outra solução? Conheça