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 sua pergunta

Aprenda do seu jeito, no seu ritmo

Envie atividades, projetos ou exercícios para um professor resolver no seu prazo.

Envie suas dúvidas pelo App

Escaneie o QR Code para baixar