Principais estruturas de dados e algoritmos em Java que você precisa saber



Este blog sobre Estruturas de Dados e Algoritmos em Java o ajudará a entender todas as principais estruturas e algoritmos de dados em Java.

Se eu tivesse que escolher o tópico mais importante no desenvolvimento de software, seriam estruturas de dados e algoritmos. Você pode considerá-lo a ferramenta fundamental disponível para qualquer programador de computador. Durante a programação, usamos estruturas de dados para armazenar e organizar dados, e algoritmos para manipular os dados nessas estruturas. Este artigo contém uma revisão detalhada de todas as estruturas de dados e algoritmos comuns em para permitir que os leitores se tornem bem equipados.

Listados abaixo estão os tópicos discutidos neste artigo:





Estruturas de dados em Java

Uma estrutura de dados é uma forma de armazenar e organizar dados em um computador para que possam ser usados ​​com eficiência. Ele fornece um meio de gerenciar grandes quantidades de dados com eficiência. E estruturas de dados eficientes são fundamentais para projetar algoritmos eficientes.

Dentroneste artigo ‘Estruturas de dados e algoritmos em Java’, vamos cobrir estruturas de dados básicas, como:



Vamos verificar cada um deles.

Estruturas de dados lineares em Java

Estruturas de dados lineares em são aqueles cujos elementos são sequenciais e ordenados de forma que: haja apenas um primeiro elemento e tem apenas um próximo elemento , há apenas um último elemento e tem apenas um elemento anterior , enquanto todos os outros elementos têm um Next e um anterior elemento.

Arrays

A matriz é uma estrutura de dados linearrepresentando um grupo de elementos semelhantes, acessados ​​por índice. O tamanho de uma matriz deve ser fornecido antes de armazenar os dados. Listadas abaixo estão as propriedades de uma matriz:



  • Cada elemento em uma matriz é do mesmo tipo de dados e tem o mesmo tamanho
  • Os elementos da matriz são armazenados em locais de memória contíguos com o primeiro elemento começando no menor local de memória
  • Os elementos da matriz podem ser acessados ​​aleatoriamente
  • A estrutura de dados do array não é completamente dinâmica

Arrays - Edureka

Por exemplo , podemos querer um videogame para controlar as dez melhores pontuações desse jogo. Em vez de usar dez diferentes variáveis para essa tarefa, poderíamos usar um único nome para todo o grupo e usar números de índice para se referir às pontuações mais altas desse grupo.

Lista Ligada

PARA é uma estrutura de dados linear com a coleção de vários nós, onde eCada elemento armazena seus próprios dados e um ponteiro para a localização do próximo elemento. O último link em uma lista vinculada aponta para nulo, indicando o fim da cadeia. Um elemento em uma lista vinculada é chamado de . O primeiro nó é chamado de cabeça .O último nó é chamadoa rabo .

Tipos de lista vinculada

Lista vinculada individualmente (unidirecional)

Lista duplamente vinculada (bidirecional)

Lista Circular Ligada

Aqui está um exemplo simples: Imagine uma lista vinculada como uma cadeia de clipes de papel vinculados. Você pode facilmente adicionar outro clipe de papel na parte superior ou inferior. É ainda rápido inserir um no meio. Tudo o que você precisa fazer é apenas desconectar a corrente no meio, adicionar o novo clipe de papel e reconectar a outra metade. Uma lista vinculada é semelhante.

Pilhas

Pilha, uma estrutura de dados abstrata, é uma coleção de objetos que são inseridos e removidos de acordo com o último a entrar, primeiro a sair (UEPS) princípio. Os objetos podem ser inseridos em uma pilha a qualquer momento, mas apenas o objeto inserido mais recentemente (ou seja, o “último”) pode ser removido a qualquer momento.Listadas abaixo estão as propriedades de uma pilha:

  • É uma lista ordenada na qualinserção e exclusão podem ser realizadas apenas em uma extremidade que é chamada de topo
  • Estrutura de dados recursiva com um ponteiro para seu elemento superior
  • Segue o último a entrar, primeiro a sair (UEPS) princípio
  • Suporta dois métodos mais fundamentais
    • empurrar (e): inserir o elemento e, no topo da pilha
    • pop (): remove e retorna o elemento superior da pilha

Exemplos práticos da pilha incluem ao inverter uma palavra,para verificar a exatidão de parêntesesseqüência,implementação da funcionalidade de volta em navegadores e muito mais.

Filas

também são outro tipo de estrutura de dados abstrata. Ao contrário de uma pilha, a fila é uma coleção de objetos que são inseridos e removidos de acordo com o first-in-first-out (FIFO) princípio. Ou seja, os elementos podem ser inseridos a qualquer momento, mas apenas o elemento que está na fila há mais tempo pode ser removido a qualquer momento.Abaixo estão listadas as propriedades de uma fila:

  • Frequentemente referido como primeiro a entrar, primeiro a sair Lista
  • Suporta dois métodos mais fundamentais
    • enfileirar (e): Insira o elemento e, no retaguarda da fila
    • dequeue (): Remover e retornar o elemento do frente da fila

Filas são usadas notransferência assíncrona de dados entre dois processos, agendamento de CPU, agendamento de disco e outras situações onde os recursos são compartilhados entre vários usuários e servidos por ordem de chegada no servidor. Em seguida, neste artigo 'Estruturas de dados e algoritmos em Java', temos estruturas de dados hierárquicas.

Estruturas de dados hierárquicas em Java

Árvore Binária

Árvore binária é umestruturas hierárquicas de dados em árvore nas quais cada nó tem no máximo dois filhos , que são chamados de criança esquerda e a criança certa . Cada árvore binária possui os seguintes grupos de nós:

  • Nó raiz: é o nó superior e muitas vezes referido como o nó principalporque todos os outros nós podem ser alcançados a partir da raiz
  • Subárvore esquerda, que também é uma árvore binária
  • Subárvore direita, que também é uma árvore binária

Listadas abaixo estão as propriedades de uma árvore binária:

  • Uma árvore binária pode ser percorrida de duas maneiras:
    • Profundidade Primeiro Traversal : Em ordem (esquerda-raiz-direita), pré-ordem (raiz-esquerda-direita) e pós-ordem (esquerda-direita-raiz)
    • Largura Primeiro Traversal : Nível de ordem transversal
  • Complexidade de tempo da travessia da árvore: O (n)
  • O número máximo de nós no nível ‘l’ = 2l-1.

As aplicações de árvores binárias incluem:

  • Usado em muitos aplicativos de pesquisa onde os dados estão constantemente entrando / saindo
  • Como um fluxo de trabalho para composição de imagens digitais para efeitos visuais
  • Usado em quase todos os roteadores de alta largura de banda para armazenar tabelas de roteadores
  • Também usado em rede sem fio e alocação de memória
  • Usado em algoritmos de compressão e muitos mais

Pilha Binária

Binary Heap é um completoárvore binária, que responde à propriedade heap. Em termos simples,é uma variação de uma árvore binária com as seguintes propriedades:

  • Heap é uma árvore binária completa: Uma árvore é considerada completa se todos os seus níveis, exceto possivelmente o mais profundo, estiverem completos. Tsua propriedade de Binary Heap o torna adequado para ser armazenado em um .
  • Segue a propriedade heap: Um heap binário é um Min-Heap ou um Max-Heap .
    • Pilha binária mínima: Fou cada nó em um heap, o valor do nó é menor ou igual a valores das crianças
    • Pilha binária máxima: Fou cada nó em um heap, o valor do nó é Melhor que ou igual a valores das crianças

Aplicações populares de heap binário incluemimplementar filas de prioridade eficientes, encontrar com eficiência os k menores (ou maiores) elementos em um array e muitos mais.

Hash Tables

Imagine que você tem um objeto e você deseja atribuir uma tecla a ele para tornar a pesquisa muito fácil. Para armazenar esse par chave / valor, você pode usar uma matriz simples como uma estrutura de dados onde as chaves (inteiros) podem ser usadas diretamente como um índice para armazenar valores de dados. No entanto, nos casos em que as chaves são muito grandes e não podem ser usadas diretamente como um índice, uma técnica chamada hashing é usada.

No hashing, as chaves grandes são convertidas em chaves pequenas usando funções hash . Os valores são então armazenados em uma estrutura de dados chamadapara tabela de hash. Uma tabela hash é uma estrutura de dados que implementa um ADT de dicionário, uma estrutura que pode mapear chaves exclusivas para valores.

Em geral, uma tabela hash tem dois componentes principais:

qual ide é melhor para java
  1. Bucket Array: Um array de balde para uma tabela hash é um array A de tamanho N, onde cada célula de A é considerada um “balde”, ou seja, uma coleção de pares de valores-chave. O inteiro N define a capacidade da matriz.
  2. Função Hash: É qualquer função que mapeia cada chave k em nosso mapa para um inteiro no intervalo [0, N & menos 1], onde N é a capacidade da matriz de balde para esta tabela.

Quando colocamos objetos em uma hashtable, é possível que diferentes objetos tenham o mesmo hashcode. Isso é chamado de colisão . Para lidar com a colisão, existem técnicas como encadeamento e endereçamento aberto.

Portanto, essas são algumas estruturas de dados básicas e mais frequentemente usadas em Java. Agora que você está ciente de cada um deles, pode começar a implementá-los em seu . Com isso, concluímos a primeira parte 'deste artigo' Estruturas de dados e algoritmos em Java '. Na próxima parte, vamos aprender sobrealgoritmos básicos e como usá-los em aplicações práticas, como classificação e pesquisa, dividir e conquistar, algoritmos gananciosos, programação dinâmica.

Algoritmos em Java

Historicamente usado como uma ferramenta para resolver cálculos matemáticos complexos, os algoritmos estão profundamente conectados com a ciência da computação e com estruturas de dados em particular. Um algoritmo é uma sequência de instruções que descreve uma maneira de resolver um problema específico em um período de tempo finito. Eles são representados de duas maneiras:

  • Fluxogramas - É umrepresentação visual do fluxo de controle de um algoritmo
  • Pseudo-código - Istoé uma representação textual de um algoritmo que se aproxima do código-fonte final

Nota: O desempenho do algoritmo é medido com base na complexidade do tempo e da complexidade do espaço. Principalmente, a complexidade de qualquer algoritmo depende do problema e do próprio algoritmo.

Vamos explorar as duas categorias principais de algoritmos em Java, que são:

Classificando Algoritmos em Java

Algoritmos de classificação são algoritmos que colocam os elementos de uma lista em uma determinada ordem. As ordens mais comumente usadas são a ordem numérica e a ordem lexicográfica. Neste artigo de ‘Estruturas de dados e algoritmos’, vamos explorar alguns algoritmos de classificação.

Bubble Sort em Java

O Bubble Sort, frequentemente referido como sinking sort, é o algoritmo de classificação mais simples. Ele percorre repetidamente a lista a ser classificada, compara cada par de elementos adjacentes e os troca se estiverem na ordem errada.A classificação por bolhas tem esse nome porque filtra os elementos para o topo da matriz, como bolhas que flutuam na água.

Aqui estápseudocódigo que representa o algoritmo de classificação de bolhas (contexto de classificação crescente).

a [] é uma matriz de tamanho N begin BubbleSort (a []) declara inteiro i, j para i = 0 a N - 1 para j = 0 a N - i - 1 se a [j]> a [j + 1 ] então troque a [j], a [j + 1] end if end por return a end BubbleSort

Este código ordena uma matriz unidimensional de N itens de dados em ordem crescente. Um loop externo faz N-1 passagens pela matriz. Cada passagem usa um loop interno para trocar itens de dados de forma que o próximo item de dados menor “borbulhe” no início do array. Mas o problema é que o algoritmo precisa de uma passagem inteira sem nenhuma troca para saber que a lista está classificada.

Pior caso e complexidade de tempo médio: O (n * n). O pior caso ocorre quando uma matriz é classificada reversamente.

Melhor caso de complexidade de tempo: Em). O melhor caso ocorre quando uma matriz já está classificada.

Classificação de seleção em Java

A classificação de seleção é uma combinação de pesquisa e classificação. O algoritmo classifica uma matriz encontrando repetidamente o elemento mínimo (considerando a ordem crescente) da parte não classificada e colocando-o em uma posição adequada na matriz.

Aqui está o pseudocódigo que representa o Algoritmo de Classificação por Seleção (contexto de classificação crescente).

a [] é uma matriz de tamanho N begin SelectionSort (a []) para i = 0 an - 1 / * definir o elemento atual como mínimo * / min = i / * encontrar o elemento mínimo * / para j = i + 1 para n se lista [j]

Como você pode entender pelo código, o número de vezes que a classificação passa pela matriz é um a menos do que o número de itens na matriz. O loop interno encontra o próximo menor valor e o loop externo coloca esse valor em seu local apropriado. A classificação de seleção nunca faz mais do que O (n) trocas e pode ser útil quando a gravação de memória é uma operação cara.

Complexidade de tempo: Em2), pois há dois loops aninhados.

Espaço Auxiliar: Ou (1).

Classificar por inserção em Java

A classificação por inserção é um algoritmo de classificação simples que itera pela lista consumindo um elemento de entrada por vez e constrói a matriz final classificada. É muito simples e mais eficaz em conjuntos de dados menores. É uma técnica de classificação estável e no local.

Aqui está o pseudocódigo que representa o Algoritmo de classificação por inserção (contexto de classificação ascendente).

a [] é uma matriz de tamanho N begin InsertionSort (a []) para i = 1 a N chave = a [i] j = i - 1 enquanto (j> = 0 e a [j]> chave0 a [j + 1] = x [j] j = j - 1 fim enquanto a [j + 1] = fim de chave para fim InsertionSort

Como você pode entender pelo código, o algoritmo de classificação de inserçãoremove um elemento dos dados de entrada, encontra o local ao qual pertence na lista classificada e o insere ali. Ele se repete até que nenhum elemento de entrada permaneça sem classificação.

Melhor caso: O melhor caso é quando a entrada é uma matriz que já está classificada. Nesse caso, a classificação por inserção tem um tempo de execução linear (ou seja, & Theta (n)).

Pior caso: A entrada de pior caso mais simples é uma matriz classificada em ordem reversa.

QuickSort em Java

O algoritmo Quicksort é um algoritmo de classificação rápido, recursivo e não estável que funciona pelo princípio de dividir e conquistar. Ele escolhe um elemento como pivô e particiona o array fornecido ao redor desse pivô selecionado.

Etapas para implementar a classificação rápida:

  1. Escolha um “ponto de pivô” adequado.
  2. Divida as listas em duas listascom base neste elemento pivô. Cada elemento menor do que o elemento pivô é colocado na lista da esquerda e cada elemento maior é colocado na lista da direita. Se um elemento for igual ao elemento pivô, ele pode entrar em qualquer lista. Isso é chamado de operação de partição.
  3. Classifique recursivamente cada uma das listas menores.

Aqui está o pseudocódigo que representa o Algoritmo Quicksort.

java convert string to date
QuickSort (A como array, baixo como int, alto como int) {if (baixo

No pseudocódigo acima, partição () função executa a operação de partição e Ordenação rápida() function chama repetidamente a função de partição para cada lista menor gerada. A complexidade do quicksort no caso médio é & Theta (n log (n)) e no pior caso é & Theta (n2).

Mesclar classificação em Java

Mergesort é um algoritmo de ordenação rápido, recursivo e estável que também funciona pelo princípio de dividir e conquistar. Semelhante ao quicksort, merge sort divide a lista de elementos em duas listas. Essas listas são classificadas independentemente e, em seguida, combinadas. Durante a combinação das listas, os elementos são inseridos (ou mesclados) no lugar certo da lista.

Aqui está o pseudocódigo que representa o algoritmo de classificação de mesclagem.

procedimento MergeSort (a as array) if (n == 1) retorna a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) retornar mesclar (l1, l2) procedimento final procedimento mesclar (a como matriz, b como matriz) var c como matriz enquanto (a e b têm elementos) if ( a [0]> b [0]) adicione b [0] ao final de c remova b [0] de b else adicione a [0] ao final de c remova a [0] de um final se final enquanto enquanto (a possui elementos) adicione a [0] ao final de c remova a [0] de um final enquanto (b possui elementos) adicione b [0] ao final de c remova b [0] do final de b enquanto retorna c procedimento final

mergesort () função divide a lista em duas, chamadas mergesort () nessas listas separadamente e, em seguida, combina-as enviando-as como parâmetros para a função merge ().O algoritmo tem uma complexidade de O (n log (n)) e tem uma ampla gama de aplicações.

Classificação de heap em Java

Heapsort é um algoritmo de classificação baseado em comparaçãoEstrutura de dados Binary Heap. Você pode pensar nisso como uma versão aprimorada da classificação de seleção, ondeele divide sua entrada em uma região classificada e uma não classificada e encolhe iterativamente a região não classificada, extraindo o maior elemento e movendo-o para a região classificada.

Etapas para implementar Quicksort (em ordem crescente):

  1. Construir um heap máximo com a matriz de classificação
  2. Neste pontot, o maior item é armazenado na raiz do heap. Substitua-o pelo último item do heap e reduza o tamanho do heap em 1. Finalmente, monte a raiz da árvore
  3. Repita as etapas acima até que o tamanho da pilha seja maior que 1

Aqui está o pseudocódigo que representa o algoritmo de classificação de heap.

Heapsort (a as array) para (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) fim para fim para heapify (a como matriz, n como int, i como int) maior = i // Inicializar maior como raiz int l eft = 2 * i + 1 // esquerda = 2 * i + 1 int right = 2 * i + 2 // right = 2 * i + 2 if (left a [maior]) maior = left if (right a [maior]) maior = right if (maior! = I) swap ( a [i], A [maior]) Heapify (a, n, maior) end heapify

Além desses, existem outros algoritmos de classificação que não são tão conhecidos, como Introsort, Classificação por contagem, etc. Passando para o próximo conjunto de algoritmos neste artigo de ‘Estruturas de dados e algoritmos’, vamos explorar algoritmos de busca.

Pesquisando Algoritmos em Java

Pesquisar é uma das ações mais comuns e realizadas com frequência em aplicativos comerciais regulares. Algoritmos de pesquisa são algoritmos para localizar um item com propriedades especificadas entre uma coleção de itens. Vamos explorar dois dos algoritmos de pesquisa mais comumente usados.

Algoritmo de pesquisa linear em Java

A pesquisa linear ou pesquisa sequencial é o algoritmo de pesquisa mais simples. Envolve a busca sequencial por um elemento na estrutura de dados fornecida até que o elemento seja encontrado ou o fim da estrutura seja alcançado. Se o elemento for encontrado, a localização do item é retornada, caso contrário, o algoritmo retorna NULL.

Este é o pseudocódigo que representa a pesquisa linear em Java:

procedimento linear_search (a [], valor) para i = 0 a n-1 se a [i] = valor então imprima 'Encontrado' retorne i final se imprima 'Não encontrado' fim para final linear_search

É umalgoritmo de força bruta.Embora certamente seja o mais simples, definitivamente não é o mais comum, devido à sua ineficiência. A complexidade de tempo da pesquisa linear é EM) .

Algoritmo de pesquisa binária em Java

A pesquisa binária, também conhecida como pesquisa logarítmica, é um algoritmo de pesquisa que encontra a posição de um valor de destino em uma matriz já classificada. Ele divide a coleção de entrada em metades iguais e o item é comparado com o elemento do meio da lista. Se o elemento for encontrado, a pesquisa termina aí. Caso contrário, continuamos procurando o elemento dividindo e selecionando a partição apropriada da matriz, com base no fato de o elemento de destino ser menor ou maior do que o elemento do meio.

Este é o pseudocódigo que representa a pesquisa binária em Java:

Procedimento binary_search uma matriz classificada n tamanho da matriz x valor a ser pesquisado lowerBound = 1 upperBound = n enquanto x não foi encontrado se upperBound

A pesquisa termina quando o upperBound (nosso ponteiro) vai além do lowerBound (último elemento), o que implica que pesquisamos em todo o array e o elemento não está presente.É o algoritmo de pesquisa mais comumente usado, principalmente devido ao seu tempo de pesquisa rápido. A complexidade de tempo da pesquisa binária é EM) o que é uma melhoria marcante no EM) complexidade de tempo da Pesquisa Linear.

Isso nos leva ao final deste artigo 'Estruturas de dados e algoritmos em Java'. Cobri um dos tópicos mais fundamentais e importantes de Java.Espero que você tenha esclarecido tudo o que foi compartilhado com você neste artigo.

Pratique o máximo possível e reverta sua experiência.

Confira o pela Edureka, uma empresa de aprendizagem online confiável com uma rede de mais de 250.000 alunos satisfeitos espalhados por todo o mundo. Estamos aqui para ajudá-lo em todas as etapas de sua jornada, para nos tornarmos uma pergunta além dessa entrevista java, nós criamos um currículo que é projetado para estudantes e profissionais que desejam ser um desenvolvedor Java.

Tem alguma questão para nós? Mencione isso na seção de comentários deste ‘Estruturas de dados e algoritmos em Java’ artigo e entraremos em contato com você o mais breve possível.