Le migliori strutture dati e algoritmi in Java che devi conoscere

Se dovessi scegliere l'argomento più importante nello sviluppo del software, sarebbero le strutture di dati e gli algoritmi. Puoi pensarlo come lo strumento fondamentale a disposizione di ogni programmatore di computer. Durante la programmazione, usiamo strutture dati per archiviare e organizzare i dati e algoritmi per manipolare i dati in quelle strutture. Questo articolo contiene una revisione dettagliata di tutte le strutture di dati e gli algoritmi comuni in per consentire ai lettori di diventare ben attrezzati.

Di seguito sono elencati gli argomenti discussi in questo articolo:

• Strutture dati in Java
  • Strutture dati lineari
  • Strutture dati gerarchiche
• Algoritmi in Java
  • Algoritmi di ordinamento
  • Ricerca di algoritmi

Strutture dati in Java

Una struttura dati è un modo per archiviare e organizzare i dati in un computer in modo che possano essere utilizzati in modo efficiente. Fornisce un mezzo per gestire in modo efficiente grandi quantità di dati. E strutture dati efficienti sono fondamentali per progettare algoritmi efficienti.

Nelin questo articolo 'Strutture dati e algoritmi in Java', tratteremo strutture di dati di base come:

• Strutture dati lineari
  • Lista collegata
  • Pile
  • Code

• Strutture dati gerarchiche
  • Alberi binari
  • Mucchi
  • Tabelle hash

Diamo un'occhiata a ciascuno di essi.

Strutture dati lineari in Java

Strutture dati lineari in sono quelli i cui elementi sono sequenziali e ordinati in modo tale che: ce ne sia uno solo primo elemento e ne ha solo uno elemento successivo , ce n'è solo uno ultimo elemento e ne ha solo uno elemento precedente , mentre tutti gli altri elementi hanno l'estensione Il prossimo e a precedente elemento.

Arrays

Un Vettore è una struttura dati lineareche rappresenta un gruppo di elementi simili, a cui si accede tramite indice. La dimensione di un array deve essere fornita prima di memorizzare i dati. Di seguito sono elencate le proprietà di un array:

• Ogni elemento in un array è dello stesso tipo di dati e ha la stessa dimensione
• Gli elementi della matrice vengono memorizzati in posizioni di memoria contigue con il primo elemento che inizia dalla posizione di memoria più piccola
• È possibile accedere in modo casuale agli elementi dell'array
• La struttura dei dati dell'array non è completamente dinamica

Per esempio , potremmo volere che un videogioco tenga traccia dei primi dieci punteggi di quel gioco. Piuttosto che usarne dieci diversi variabili per questa attività, potremmo utilizzare un unico nome per l'intero gruppo e utilizzare i numeri di indice per fare riferimento ai punteggi più alti in quel gruppo.

Lista collegata

PER è una struttura dati lineare con la raccolta di più nodi, dove eOgni elemento memorizza i propri dati e un puntatore alla posizione dell'elemento successivo. L'ultimo collegamento in un elenco collegato punta a null, indicando la fine della catena. Un elemento in un elenco collegato è chiamato a nodo . Il primo nodo è chiamato capo .Viene chiamato l'ultimo nodoil coda .

Tipi di elenchi collegati

Elenco collegato singolarmente (unidirezionale)

Elenco a doppio collegamento (bidirezionale)

Elenco collegato circolare

Ecco un semplice esempio: Immagina un elenco collegato come una catena di graffette collegate insieme. Puoi facilmente aggiungere un'altra graffetta in alto o in basso. È anche veloce inserirne uno nel mezzo. Tutto quello che devi fare è scollegare la catena al centro, aggiungere la nuova graffetta, quindi ricollegare l'altra metà. Un elenco collegato è simile.

Pile

Pila, una struttura dati astratta, è una raccolta di file oggetti che vengono inseriti e rimossi secondo il last-in-first-out (LIFO) principio. Gli oggetti possono essere inseriti in una pila in qualsiasi momento, ma solo l'oggetto inserito più di recente (ovvero, 'l'ultimo') può essere rimosso in qualsiasi momento.Di seguito sono elencate le proprietà di uno stack:

come generare una stringa casuale in java

• È un elenco ordinato in cuil'inserimento e la cancellazione possono essere eseguiti solo su un'estremità chiamata superiore
• Struttura dati ricorsiva con un puntatore al suo elemento superiore
• Segue il last-in-first-out (LIFO) principio
• Supporta due metodi fondamentali
  • push (e): inserisce l'elemento e in cima alla pila
  • pop (): rimuove e restituisce l'elemento in cima allo stack

Esempi pratici della pila includono quando si inverte una parola,per verificare la correttezza di parentesisequenza,implementando la funzionalità di ritorno nei browser e molti altri.

Code

sono anche un altro tipo di struttura dati astratta. A differenza di uno stack, la coda è una raccolta di oggetti che vengono inseriti e rimossi in base a first-in-first-out (FIFO) principio. Cioè, gli elementi possono essere inseriti in qualsiasi momento, ma solo l'elemento che è stato in coda più a lungo può essere rimosso in qualsiasi momento.Di seguito sono elencate le proprietà di una coda:

• Spesso indicato come il il primo che entra è il primo ad uscire elenco
• Supporta due metodi fondamentali
  • enqueue (e): inserisce l'elemento e, in posteriore della coda
  • dequeue (): rimuove e restituisce l'elemento dal file davanti della coda

Le code vengono utilizzate intrasferimento asincrono di dati tra due processi, pianificazione della CPU, pianificazione del disco e altre situazioni in cui le risorse sono condivise tra più utenti e servite in base al primo arrivato, primo server. Successivamente, in questo articolo 'Strutture dati e algoritmi in Java', abbiamo strutture dati gerarchiche.

Strutture di dati gerarchiche in Java

Albero binario

Binary Tree è un filestrutture di dati ad albero gerarchico in cui ogni nodo ha al massimo due figli , che sono indicati come il bambino sinistro e il figlio giusto . Ogni albero binario ha i seguenti gruppi di nodi:

• Nodo radice: è il nodo più in alto e spesso viene definito nodo principaleperché tutti gli altri nodi possono essere raggiunti dalla radice
• Left Sub-Tree, che è anche un albero binario
• Right Sub-Tree, che è anche un albero binario

Di seguito sono elencate le proprietà di un albero binario:

• Un albero binario può essere attraversato in due modi:
  • Profondità prima traversata : In ordine (sinistra-radice-destra), preordine (radice-sinistra-destra) e postordine (sinistra-destra-radice)
  • Larghezza prima traversata : Attraversamento dell'ordine di livello
• Complessità temporale dell'attraversamento dell'albero: O (n)
• Il numero massimo di nodi al livello 'l' = 2^l-1.

Le applicazioni degli alberi binari includono:

• Utilizzato in molte applicazioni di ricerca in cui i dati entrano / escono costantemente
• Come flusso di lavoro per la composizione di immagini digitali per effetti visivi
• Utilizzato in quasi tutti i router a larghezza di banda elevata per la memorizzazione delle tabelle dei router
• Utilizzato anche nelle reti wireless e nell'allocazione della memoria
• Utilizzato negli algoritmi di compressione e molti altri

Heap binario

Binary Heap è un completoalbero binario, che risponde alla proprietà heap. In termini semplici essoè una variazione di un albero binario con le seguenti proprietà:

• Heap è un albero binario completo: Si dice che un albero sia completo se tutti i suoi livelli, tranne forse il più profondo, sono completi. Tla sua proprietà di Binary Heap lo rende adatto per essere memorizzato in un file .
• Segue la proprietà dell'heap: Un heap binario è un file Min-Heap o a Max-Heap .
  • Heap binario minimo: Fo ogni nodo in un heap, il valore del nodo è minore o uguale a valori dei bambini
  • Heap binario massimo: Fo ogni nodo in un heap, il valore del nodo è maggiore o uguale a valori dei bambini

Le applicazioni popolari di heap binario includonoimplementando code di priorità efficienti, trovando in modo efficiente i k elementi più piccoli (o più grandi) in un array e molti altri.

Tabelle hash

Immagina di avere un file oggetto e si desidera assegnargli una chiave per semplificare la ricerca. Per memorizzare quella coppia chiave / valore, è possibile utilizzare un semplice array come una struttura dati in cui le chiavi (numeri interi) possono essere utilizzate direttamente come indice per memorizzare i valori dei dati. Tuttavia, nei casi in cui le chiavi sono troppo grandi e non possono essere utilizzate direttamente come indice, viene utilizzata una tecnica chiamata hashing.

Nell'hashing, le chiavi grandi vengono convertite in chiavi piccole utilizzando funzioni hash . I valori vengono quindi memorizzati in una struttura dati chiamataper tabella hash. Una tabella hash è una struttura dati che implementa un dizionario ADT, una struttura che può mappare chiavi univoche ai valori.

In generale, una tabella hash ha due componenti principali:

1. Matrice di secchi: Un array di bucket per una tabella hash è un array A di dimensione N, in cui ogni cella di A è pensata come un 'bucket', ovvero una raccolta di coppie chiave-valore. L'intero N definisce la capacità dell'array.
2. Funzione hash: È qualsiasi funzione che mappa ogni chiave k nella nostra mappa su un numero intero nell'intervallo [0, N & meno 1], dove N è la capacità dell'array di bucket per questa tabella.

Quando inseriamo oggetti in una tabella hash, è possibile che oggetti diversi abbiano lo stesso codice hash. Questo è chiamato a collisione . Per affrontare la collisione, esistono tecniche come il concatenamento e l'indirizzamento aperto.

Quindi, queste sono alcune strutture dati di base e utilizzate più di frequente in Java. Ora che sei consapevole di ciascuno di questi, puoi iniziare a implementarli nel tuo file . Con questo, abbiamo completato la prima parte di 'questo articolo' Strutture dati e algoritmi in Java '. Nella parte successiva, impareremoalgoritmi di base e come usarli in applicazioni pratiche come ordinamento e ricerca, divide et impera, algoritmi avidi, programmazione dinamica.

Algoritmi in Java

Storicamente utilizzati come strumento per la risoluzione di calcoli matematici complessi, gli algoritmi sono profondamente connessi con l'informatica e con le strutture dati in particolare. Un algoritmo è una sequenza di istruzioni che descrive un modo per risolvere un problema specifico in un periodo di tempo finito. Sono rappresentati in due modi:

• Diagrammi di flusso - È unrappresentazione visiva del flusso di controllo di un algoritmo
• Pseudocodice - Itè una rappresentazione testuale di un algoritmo che approssima il codice sorgente finale

Nota: Le prestazioni dell'algoritmo vengono misurate in base alla complessità temporale e spaziale. Per lo più, la complessità di qualsiasi algoritmo dipende dal problema e dall'algoritmo stesso.

Esploriamo le due principali categorie di algoritmi in Java, che sono:

• Ordinamento degli algoritmi in Java
• Ricerca di algoritmi in Java

Ordinamento degli algoritmi in Java

Gli algoritmi di ordinamento sono algoritmi che mettono gli elementi di un elenco in un certo ordine. Gli ordini più comunemente usati sono l'ordine numerico e l'ordine lessicografico. In questo articolo 'Strutture dati e algoritmi' esploriamo alcuni algoritmi di ordinamento.

Bubble Sort in Java

Bubble Sort, spesso definito come sinking sort, è l'algoritmo di ordinamento più semplice. Scorre ripetutamente l'elenco da ordinare, confronta ogni coppia di elementi adiacenti e li scambia se sono nell'ordine sbagliato.Bubble sort prende il nome perché filtra gli elementi nella parte superiore della matrice, come bolle che galleggiano sull'acqua.

Eccopseudocodice che rappresenta l'algoritmo di ordinamento a bolle (contesto di ordinamento crescente).

a [] è un array di dimensione N inizio BubbleSort (a []) dichiara intero i, j per i = 0 a N - 1 per j = 0 a N - i - 1 se a [j]> a [j + 1 ] quindi scambia una [j], una [j + 1] end if end per restituire una fine BubbleSort

Questo codice ordina una matrice unidimensionale di N elementi di dati in ordine crescente. Un loop esterno fa passare N-1 sull'array. Ogni passaggio utilizza un ciclo interno per scambiare elementi di dati in modo tale che l'elemento di dati più piccolo successivo 'bolle' verso l'inizio della matrice. Ma il problema è che l'algoritmo richiede un intero passaggio senza alcuno scambio per sapere che l'elenco è ordinato.

Complessità del tempo del caso peggiore e media: O (n * n). Il caso peggiore si verifica quando un array viene ordinato al contrario.

Migliore complessità del case time: Su). Il caso migliore si verifica quando un array è già ordinato.

Ordinamento selezione in Java

L'ordinamento della selezione è una combinazione di ricerca e ordinamento. L'algoritmo ordina un array trovando ripetutamente l'elemento minimo (considerando l'ordine crescente) dalla parte non ordinata e posizionandolo in una posizione corretta nell'array.

Ecco lo pseudocodice che rappresenta l'algoritmo di ordinamento della selezione (contesto di ordinamento crescente).

a [] è un array di dimensione N begin SelectionSort (a []) per i = 0 an - 1 / * imposta l'elemento corrente come minimo * / min = i / * trova l'elemento minimo * / per j = i + 1 to n if list [j]
Come puoi capire dal codice, il numero di volte in cui l'ordinamento passa attraverso l'array è uno in meno rispetto al numero di elementi nell'array. Il ciclo interno trova il valore successivo più piccolo e il ciclo esterno colloca quel valore nella sua posizione corretta. L'ordinamento della selezione non effettua mai più di O (n) scambi e può essere utile quando la scrittura in memoria è un'operazione costosa.
 Complessità temporale: Su2) in quanto vi sono due cicli annidati.
 Spazio ausiliario: Oppure (1).
 Ordinamento di inserzione in Java 
L'ordinamento di inserzione è un semplice algoritmo di ordinamento che itera nell'elenco consumando un elemento di input alla volta e costruisce l'array ordinato finale. È molto semplice e più efficace su set di dati più piccoli. È una tecnica di smistamento stabile e sul posto.
Ecco lo pseudocodice che rappresenta l'algoritmo di ordinamento di inserzione (contesto di ordinamento crescente).
a [] è un array di dimensione N begin InsertionSort (a []) per i = 1 to N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 fine mentre a [j + 1] = estremità chiave per fine InsertionSort
Come puoi capire dal codice, l'algoritmo di ordinamento per inserzionerimuove un elemento dai dati di input, trova la posizione a cui appartiene nell'elenco ordinato e lo inserisce lì. Si ripete finché nessun elemento di input rimane non ordinato.
 Caso migliore: Il caso migliore è quando l'input è un array già ordinato. In questo caso, l'ordinamento per inserzione ha un tempo di esecuzione lineare (cioè & Theta (n)).
 Caso peggiore:  L'input più semplice nel caso peggiore è un array ordinato in ordine inverso.
 QuickSort in Java 
L'algoritmo Quicksort è un algoritmo di ordinamento veloce, ricorsivo e non stabile che funziona secondo il principio divide et impera. Sceglie un elemento come pivot e partiziona l'array dato attorno a quel pivot selezionato.
 Passaggi per implementare l'ordinamento rapido:  
 
Scegli un 'punto di articolazione' adatto.
Dividi gli elenchi in due elenchibasato su questo elemento pivot. Ogni elemento più piccolo dell'elemento pivot viene posizionato nell'elenco di sinistra e ogni elemento più grande viene inserito nell'elenco di destra. Se un elemento è uguale all'elemento pivot, può essere inserito in qualsiasi elenco. Questa è chiamata operazione di partizione.
Ordina ricorsivamente ciascuno degli elenchi più piccoli. 
Ecco lo pseudocodice che rappresenta l'algoritmo Quicksort.
QuickSort (A come array, basso come int, alto come int) {if (low
Nello pseudocodice sopra, partizione() funzione esegue l'operazione di partizione e Quicksort () funzione chiama ripetutamente la funzione di partizione per ogni elenco più piccolo generato. La complessità del quicksort nel caso medio è & Theta (n log (n)) e nel caso peggiore è & Theta (n2).
 Unisci ordinamento in Java 
Mergesort è un algoritmo di ordinamento veloce, ricorsivo e stabile che funziona anche secondo il principio divide et impera. Simile a quicksort, merge sort divide l'elenco di elementi in due elenchi. Questi elenchi vengono ordinati in modo indipendente e quindi combinati. Durante la combinazione degli elenchi, gli elementi vengono inseriti (o uniti) al posto giusto nell'elenco.
Ecco lo pseudocodice che rappresenta l'algoritmo di ordinamento unione.
procedura MergeSort (a come array) if (n == 1) restituisce una var l1 come array = a [0] ... a [n / 2] var l2 come array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) fine procedura procedura merge (a come array, b come array) var c come array while (aeb hanno elementi) if ( a [0]> b [0]) aggiungi b [0] alla fine di c rimuovi b [0] da b altrimenti aggiungi a [0] alla fine di c rimuovi a [0] da una fine se finisce mentre mentre (a ha elementi) aggiungi a [0] alla fine di c rimuove a [0] da una fine mentre (b ha elementi) aggiungi b [0] alla fine di c rimuovi b [0] dalla fine b mentre ritorna c fine procedura
 mergesort () la funzione divide l'elenco in due, chiamate mergesort () su questi elenchi separatamente e quindi li combina inviandoli come parametri alla funzione merge ().L'algoritmo ha una complessità di O (n log (n)) e ha un'ampia gamma di applicazioni.
 Ordinamento heap in Java 
Heapsort è un algoritmo di ordinamento basato sul confrontoStruttura dati dell'heap binario. Puoi pensarlo come una versione migliorata di ordinamento di selezione, dovedivide il suo input in una regione ordinata e una non ordinata e riduce iterativamente la regione non ordinata estraendo l'elemento più grande e spostandolo nella regione ordinata.
 Passaggi per implementare Quicksort (in ordine crescente): 
Crea un heap massimo con l'array di ordinamento
A questo puntot, l'elemento più grande viene archiviato nella radice dell'heap. Sostituiscilo con l'ultimo elemento dell'heap e riduci la dimensione dell'heap di 1. Infine, heapify la radice dell'albero
Ripetere i passaggi precedenti finché la dimensione dell'heap non è maggiore di 1
Ecco lo pseudocodice che rappresenta l'algoritmo di ordinamento dell'heap.
Heapify (a come array) per (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) fine per fine per heapify (a come array, n come int, i come int) più grande = i // Inizializza più grande come radice int l eft = 2 * i + 1 // sinistra = 2 * i + 1 int a destra = 2 * i + 2 // a destra = 2 * i + 2 se (a sinistra a [il più grande]) il più grande = a sinistra se (a destra a [il più grande]) il più grande = a destra se (il più grande! = I) scambia ( a [i], A [più grande]) Heapify (a, n, più grande) end heapify
Oltre a questi, ci sono altri algoritmi di ordinamento che non sono così conosciuti come Introsort, Counting Sort, ecc. Passando alla prossima serie di algoritmi in questo articolo 'Strutture dati e algoritmi', esploriamo gli algoritmi di ricerca.
 Ricerca di algoritmi in Java 
La ricerca è una delle azioni più comuni e frequenti nelle normali applicazioni aziendali. Gli algoritmi di ricerca sono algoritmi per trovare un elemento con proprietà specificate in una raccolta di elementi. Esploriamo due degli algoritmi di ricerca più comunemente utilizzati.
 Algoritmo di ricerca lineare in Java 
La ricerca lineare o sequenziale è l'algoritmo di ricerca più semplice. Implica la ricerca sequenziale di un elemento nella struttura dati data fino a quando l'elemento viene trovato o viene raggiunta la fine della struttura. Se l'elemento viene trovato, viene restituita la posizione dell'elemento altrimenti l'algoritmo restituisce NULL.
Ecco lo pseudocodice che rappresenta la ricerca lineare in Java:
procedura linear_search (a [], value) for i = 0 an-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search
È unalgoritmo di forza bruta.Sebbene sia certamente il più semplice, sicuramente non è il più comune, a causa della sua inefficienza. La complessità temporale della ricerca lineare è SU) .
chef vs ansible vs burattino
 Algoritmo di ricerca binaria in Java 
La ricerca binaria, nota anche come ricerca logaritmica, è un algoritmo di ricerca che trova la posizione di un valore target all'interno di un array già ordinato. Divide la raccolta di input in metà uguali e l'elemento viene confrontato con l'elemento centrale dell'elenco. Se l'elemento viene trovato, la ricerca finisce qui. Altrimenti, continuiamo a cercare l'elemento dividendo e selezionando la partizione appropriata dell'array, in base al fatto che l'elemento di destinazione sia più piccolo o più grande dell'elemento centrale.
Ecco lo pseudocodice che rappresenta la ricerca binaria in Java:
Procedura binary_search un array ordinato n dimensione dell'array x valore da cercare lowerBound = 1 upperBound = n mentre x non trovato se upperBound
La ricerca termina quando upperBound (il nostro puntatore) supera lowerBound (ultimo elemento), il che implica che abbiamo cercato nell'intero array e che l'elemento non è presente.È l'algoritmo di ricerca più comunemente utilizzato principalmente a causa del suo tempo di ricerca rapido. La complessità temporale della ricerca binaria è SU) che è un netto miglioramento rispetto a SU) complessità temporale della ricerca lineare.
Questo ci porta alla fine di questo articolo 'Strutture dati e algoritmi in Java'. Ho trattato uno degli argomenti più fondamentali e importanti di Java.Spero che tu sia chiaro con tutto ciò che è stato condiviso con te in questo articolo.
  Assicurati di esercitarti il ​​più possibile e di ripristinare la tua esperienza.   
 Controlla il    da Edureka, una società di formazione online affidabile con una rete di oltre 250.000 studenti soddisfatti sparsi in tutto il mondo. Siamo qui per aiutarti in ogni fase del tuo viaggio, per diventare oltre a queste domande dell'intervista Java, abbiamo creato un curriculum progettato per studenti e professionisti che vogliono essere uno sviluppatore Java. 
 Hai domande per noi? Si prega di menzionarlo nella sezione commenti di questo 'Strutture dati e algoritmi in Java'  articolo e ti risponderemo il prima possibile.