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. · 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

Envie uma dúvida gratuitamente

Sabe a resposta?

Envie uma dúvida gratuitamente

Professores particulares de Java

Envie uma tarefa, lista de exercícios, atividade ou projeto

Últimas dúvidas de Programação - Java

Envie uma dúvida gratuitamente

Disciplinas principais

Encontre um professor e combine aulas particulares Presenciais ou Online

Recursos Profes

O Profes é uma solução completa de aprendizagem, com diversos recursos para
você aprender do jeito mais eficiente e personalizado possível.

Lista duplamente encadeada

Envie uma dúvida gratuitamente

Sabe a resposta?

Envie uma dúvida gratuitamente

Professores particulares de Java

Envie uma tarefa, lista de exercícios, atividade ou projeto

Últimas dúvidas de Programação - Java

Envie uma dúvida gratuitamente

Disciplinas principais

Encontre um professor e combine aulas particulares Presenciais ou Online

Recursos Profes

O Profes é uma solução completa de aprendizagem, com diversos recursos para você aprender do jeito mais eficiente e personalizado possível.

O Profes é uma solução completa de aprendizagem, com diversos recursos para
você aprender do jeito mais eficiente e personalizado possível.