10 Strutture di dati comuni spiegate con video + esercizi

“I cattivi programmatori si preoccupano del codice. I bravi programmatori si preoccupano delle strutture di dati e delle loro relazioni. ”- Linus Torvalds, creatore di Linux
** Aggiornamento ** Il mio video corso sugli algoritmi è ora in diretta! Scopri Algorithms in Motion dalle pubblicazioni Manning. Ottieni il 39% di sconto sul mio corso utilizzando il codice "39carnes"! Oppure puoi ottenere il 50% di sconto sul mio corso Deep Learning in Motion con il codice "vlcarnes2".

Le strutture di dati sono una parte fondamentale dello sviluppo del software e uno degli argomenti più comuni per le domande sui colloqui di lavoro con gli sviluppatori.

La buona notizia è che sono fondamentalmente solo formati specializzati per l'organizzazione e l'archiviazione dei dati.

Ti insegnerò 10 delle strutture di dati più comuni, proprio qui in questo breve articolo.

Ho incorporato video che ho creato per ognuna di queste strutture di dati. Ho anche collegato esempi di codice per ciascuno di essi, che mostrano come implementarli in JavaScript.

E per darti un po 'di pratica, mi sono collegato alle sfide del curriculum di FreeCodeCamp.

Si noti che alcune di queste strutture di dati includono la complessità temporale nella notazione Big O. Questo non è incluso per tutti loro poiché la complessità temporale a volte si basa su come è stata implementata. Se vuoi saperne di più su Big O Notation, consulta il mio articolo a riguardo o questo video di Briana Marie.

Inoltre, anche se mostro come implementare queste strutture di dati in JavaScript, per la maggior parte di esse non avresti mai bisogno di implementarle tu stesso, a meno che tu non stia usando un linguaggio di basso livello come C.

JavaScript (come la maggior parte dei linguaggi di alto livello) ha implementazioni integrate di molte di queste strutture di dati.

Tuttavia, sapere come implementare queste strutture di dati ti darà un enorme vantaggio nella ricerca di lavoro per gli sviluppatori e potrebbe tornare utile quando stai cercando di scrivere codice ad alte prestazioni.

Elenchi collegati

Un elenco collegato è una delle strutture di dati più basilari. Viene spesso confrontato con un array poiché molte altre strutture di dati possono essere implementate con un array o un elenco collegato. Ognuno di essi presenta vantaggi e svantaggi.

Rappresentazione dell'elenco collegato

Un elenco collegato è costituito da un gruppo di nodi che insieme rappresentano una sequenza. Ogni nodo contiene due cose: i dati effettivi che vengono archiviati (che possono essere praticamente qualsiasi tipo di dati) e un puntatore (o collegamento) al nodo successivo nella sequenza. Esistono anche elenchi doppiamente collegati in cui ciascun nodo ha un puntatore sia all'elemento successivo che a quello precedente nell'elenco.

Le operazioni di base in un elenco collegato sono l'aggiunta di un elemento all'elenco, l'eliminazione di un elemento dall'elenco e la ricerca nell'elenco di un elemento.

Vedi il codice per un elenco collegato in JavaScript qui.

Complessità temporale dell'elenco collegato
╔═══════════╦═════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬═════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (n) ║ O (n) ║
║ Inserire ║ O (1) ║ O (1) ║
║ Elimina ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

sfide di FreeCodeCamp

  • Lavora con i nodi in un elenco collegato
  • Creare una classe elenco collegato
  • Rimuovi elementi da un elenco collegato
  • Cerca in un elenco collegato
  • Rimuovi elementi da un elenco collegato per indice
  • Aggiungi elementi a un indice specifico in un elenco collegato
  • Crea un elenco doppiamente collegato
  • Invertire un elenco doppiamente collegato

Stacks

Uno stack è una struttura di dati di base in cui è possibile inserire o eliminare solo elementi nella parte superiore dello stack. È un po 'simile a una pila di libri. Se vuoi guardare un libro nel mezzo della pila, devi prima togliere tutti i libri sopra di esso.

Lo stack è considerato LIFO (Last In First Out) - il che significa che l'ultimo oggetto inserito nello stack è il primo oggetto che esce dallo stack

Rappresentazione dello stack

Esistono tre operazioni principali che possono essere eseguite su stack: inserire un oggetto in uno stack (chiamato 'push'), eliminare un oggetto dallo stack (chiamato 'pop') e visualizzare il contenuto dello stack (a volte chiamato 'pip ').

Vedi il codice per uno stack in JavaScript qui.

Complessità temporale dello stack
╔═══════════╦═════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬═════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (n) ║ O (n) ║
║ Inserire ║ O (1) ║ O (1) ║
║ Elimina ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

sfide di FreeCodeCamp

  • Scopri come funziona uno stack
  • Crea una classe di stack

code

Puoi pensare a una coda come a una fila di persone in un negozio di alimentari. Il primo della linea è il primo ad essere servito. Proprio come una coda.

Rappresentazione della coda

Una coda è considerata FIFO (First In First Out) per dimostrare il modo in cui accede ai dati. Ciò significa che una volta aggiunto un nuovo elemento, tutti gli elementi che sono stati aggiunti in precedenza devono essere rimossi prima che il nuovo elemento possa essere rimosso.

Una coda ha solo due operazioni principali: accodamento e dequeue. Accodare significa inserire un oggetto nella parte posteriore della coda e accodare significa rimuovere l'elemento anteriore.

Vedi il codice per una coda in JavaScript qui.

Complessità temporale della coda
╔═══════════╦═════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬═════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (n) ║ O (n) ║
║ Inserire ║ O (1) ║ O (1) ║
║ Elimina ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

sfide di FreeCodeCamp

  • Creare una classe di coda
  • Creare una classe di coda prioritaria
  • Crea una coda circolare

Imposta

Imposta rappresentazione

La struttura dati impostata memorizza i valori senza alcun ordine particolare e senza valori ripetuti. Oltre a poter aggiungere e rimuovere elementi a un set, ci sono alcune altre importanti funzioni di set che funzionano con due set contemporaneamente.

  • Unione: combina tutti gli elementi di due set diversi e li restituisce come nuovo set (senza duplicati).
  • Intersezione: dati due set, questa funzione restituisce un altro set che ha tutti gli elementi che fanno parte di entrambi i set.
  • Differenza: restituisce un elenco di elementi che si trovano in un set ma NON in un set diverso.
  • Sottoinsieme: restituisce un valore booleano che mostra se tutti gli elementi in un set sono inclusi in un set diverso.

Visualizza il codice per implementare un set in JavaScript qui.

sfide di FreeCodeCamp

  • Crea una classe impostata
  • Rimuovi da un set
  • Dimensioni del set
  • Esegui un'unione su due set
  • Eseguire un'intersezione su due set di dati
  • Esegui una differenza su due set di dati
  • Eseguire un controllo del sottoinsieme su due set di dati
  • Crea e aggiungi ai set in ES6
  • Rimuovi elementi da un set in ES6
  • Utilizzare .has e .size su un set ES6
  • Utilizzare Spread e Note per l'integrazione Set () ES5

Mappe

Una mappa è una struttura di dati che archivia i dati in coppie chiave / valore in cui ogni chiave è unica. Una mappa viene talvolta chiamata matrice o dizionario associativo. Viene spesso utilizzato per ricerche rapide di dati. Le mappe consentono le seguenti cose:

Rappresentazione della mappa
  • l'aggiunta di una coppia alla collezione
  • la rimozione di una coppia dalla collezione
  • la modifica di una coppia esistente
  • la ricerca di un valore associato a una chiave particolare

Visualizza il codice per implementare una mappa in JavaScript qui.

sfide di FreeCodeCamp

  • Crea una struttura dati mappa
  • Crea una mappa JavaScript ES6

Tabelle hash

Tabella hash e rappresentazione della funzione hash

Una tabella hash è una struttura di dati della mappa che contiene coppie chiave / valore. Utilizza una funzione hash per calcolare un indice in una matrice di bucket o slot, da cui è possibile trovare il valore desiderato.

La funzione hash di solito accetta una stringa come input e genera un valore numerico. La funzione hash dovrebbe sempre fornire lo stesso numero di output per lo stesso input. Quando due input hanno l'hash sullo stesso output numerico, questo si chiama collisione. L'obiettivo è avere poche collisioni.

Pertanto, quando si inserisce una coppia chiave / valore in una tabella hash, la chiave viene eseguita attraverso la funzione hash e trasformata in un numero. Questo valore numerico viene quindi utilizzato come chiave effettiva in cui è memorizzato il valore. Quando si tenta di accedere nuovamente allo stesso tasto, la funzione di hashing elaborerà il tasto e restituirà lo stesso risultato numerico. Il numero verrà quindi utilizzato per cercare il valore associato. Ciò fornisce in media un tempo di ricerca O (1) molto efficiente.

Visualizza il codice per una tabella hash qui.

Hash complessità del tempo di tabella
╔═══════════╦═════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬═════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (1) ║ O (n) ║
║ Inserire ║ O (1) ║ O (n) ║
║ Elimina ║ O (1) ║ O (n) ║
╚═══════════╩═════════╩════════════╝

sfide di FreeCodeCamp

  • Crea una tabella hash

Albero di ricerca binario

Albero di ricerca binario

Un albero è una struttura di dati composta da nodi Ha le seguenti caratteristiche:

  1. Ogni albero ha un nodo radice (in alto).
  2. Il nodo radice ha zero o più nodi figlio.
  3. Ogni nodo figlio ha zero o più nodi figlio e così via.

Un albero di ricerca binario aggiunge queste due caratteristiche:

  1. Ogni nodo ha fino a due figli.
  2. Per ciascun nodo, i suoi discendenti a sinistra sono inferiori al nodo corrente, che è inferiore ai discendenti a destra.

Gli alberi di ricerca binari consentono una rapida ricerca, aggiunta e rimozione di elementi. Il modo in cui sono impostati significa che, in media, ogni confronto consente alle operazioni di saltare circa la metà dell'albero, in modo che ogni ricerca, inserimento o cancellazione richieda un tempo proporzionale al logaritmo del numero di elementi memorizzati nell'albero.

Visualizza il codice per un albero di ricerca binario in JavaScript qui.

Complessità dei tempi di ricerca binaria
╔═══════════╦══════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬══════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (log n) ║ O (n) ║
║ Inserire ║ O (registro n) ║ O (n) ║
║ Elimina ║ O (registro n) ║ O (n) ║
╚═══════════╩══════════╩════════════╝

sfide di FreeCodeCamp

  • Trova il valore minimo e massimo in un albero di ricerca binario
  • Aggiungi un nuovo elemento a un albero di ricerca binario
  • Controlla se un elemento è presente in un albero di ricerca binario
  • Trova l'altezza minima e massima di un albero di ricerca binario
  • Usa la prima ricerca della profondità in un albero di ricerca binario
  • Usa Breadth First Search in un albero di ricerca binario
  • Elimina un nodo foglia in un albero di ricerca binario
  • Elimina un nodo con un figlio in un albero di ricerca binario
  • Elimina un nodo con due figli in un albero di ricerca binario
  • Invertire un albero binario

prova

Il trie (pronunciato "prova"), o albero del prefisso, è una specie di albero di ricerca. Un trie memorizza i dati in passaggi in cui ogni passaggio è un nodo nel trie. I tentativi vengono spesso utilizzati per memorizzare parole per una rapida ricerca, ad esempio una funzione di completamento automatico delle parole.

Rappresentazione trie

Ogni nodo in un trie di lingua contiene una lettera di una parola. Segui i rami di un trie per scrivere una parola, una lettera alla volta. I passaggi iniziano a ramificarsi quando l'ordine delle lettere diverge dalle altre parole nel trie o quando termina una parola. Ogni nodo contiene una lettera (dati) e un valore booleano che indica se il nodo è l'ultimo nodo di una parola.

Guarda l'immagine e puoi formare parole. Inizia sempre dal nodo principale in alto e procedi verso il basso. Il trie mostrato qui contiene la parola ball, bat, doll, do, dork, dorm, send, sense.

Visualizza il codice per un trie in JavaScript qui.

sfide di FreeCodeCamp

  • Crea un albero di ricerca Trie

Heap binario

Un heap binario è un altro tipo di struttura dati dell'albero. Ogni nodo ha al massimo due figli. Inoltre, è un albero completo. Ciò significa che tutti i livelli sono completamente riempiti fino all'ultimo livello e l'ultimo livello è riempito da sinistra a destra.

Rappresentazioni heap min e max

Un heap binario può essere un heap minimo o un heap massimo. In un heap massimo, le chiavi dei nodi principali sono sempre maggiori o uguali a quelle dei figli. In un heap minimo, le chiavi dei nodi principali sono inferiori o uguali a quelle dei bambini.

L'ordine tra i livelli è importante ma l'ordine dei nodi sullo stesso livello non è importante. Nell'immagine, puoi vedere che il terzo livello dell'heap minimo ha valori 10, 6 e 12. Quei numeri non sono in ordine.

Visualizza il codice per un heap in JavaScript qui.

Complessità temporale dell'heap binario
╔═══════════╦══════════╦════════════╗
║ Algoritmo ║ Medio ║ Caso peggiore ║
╠═══════════╬══════════╬════════════╣
║ Spazio ║ O (n) ║ O (n) ║
║ Cerca ║ O (n) ║ O (n) ║
║ Inserire ║ O (1) ║ O (registro n) ║
║ Elimina ║ O (registro n) ║ O (registro n) ║
║ Peek ║ O (1) ║ O (1) ║
╚═══════════╩══════════╩════════════╝

sfide di FreeCodeCamp

  • Inserisci un elemento in un heap massimo
  • Rimuovi un elemento da un heap massimo
  • Implementa l'ordinamento heap con un heap minimo

Grafico

I grafici sono raccolte di nodi (detti anche vertici) e le connessioni (chiamate bordi) tra loro. I grafici sono anche noti come reti.

Un esempio di grafici è un social network. I nodi sono persone e i bordi sono amicizia.

Esistono due tipi principali di grafici: diretto e non indirizzato. I grafici non indirizzati sono grafici senza alcuna direzione sui bordi tra i nodi. I grafici diretti, al contrario, sono grafici con una direzione nei bordi.

Due modi comuni per rappresentare un grafico sono un elenco di adiacenza e una matrice di adiacenza.

Grafico a matrice di adiacenza

Un elenco di adiacenza può essere rappresentato come un elenco in cui il lato sinistro è il nodo e il lato destro elenca tutti gli altri nodi a cui è collegato.

Una matrice di adiacenza è una griglia di numeri, in cui ogni riga o colonna rappresenta un nodo diverso nel grafico. All'intersezione di una riga e una colonna è presente un numero che indica la relazione. Gli zeri indicano che non vi è alcun vantaggio o relazione. Uno significa che c'è una relazione. Numeri più alti di uno possono essere usati per mostrare pesi diversi.

Gli algoritmi di attraversamento sono algoritmi per attraversare o visitare nodi in un grafico. I principali tipi di algoritmi di attraversamento sono la ricerca in ampiezza e la ricerca in profondità. Uno degli usi è determinare la vicinanza dei nodi a un nodo principale. Guarda come implementare la prima ricerca in JavaScript nel video qui sotto.

Vedi il codice per la prima ricerca su un grafico a matrice di adiacenza in JavaScript.

Elenco di adiacenza (grafico) complessità temporale
╔═══════════════╦════════════╗
║ Algoritmo ║ Tempo ║
╠═══════════════╬════════════╣
║ Memoria ║ O (| V | + | E |) ║
║ Aggiungi vertice ║ O (1) ║
║ Aggiungi bordo ║ O (1) ║
║ Rimuovi Vertex ║ O (| V | + | E |) ║
║ Rimuovi bordo ║ O (| E |) ║
║ Query ║ O (| V |) ║
╚═══════════════╩════════════╝

sfide di FreeCodeCamp

  • Elenco di adiacenza
  • Matrice di adiacenza
  • Matrice dell'incidenza
  • Ampia ricerca
  • Ricerca approfondita

Di Più

Il libro Grokking Algorithms è il miglior libro sull'argomento se sei nuovo nelle strutture di dati / algoritmi e non hai una preparazione informatica. Utilizza spiegazioni di facile comprensione e illustrazioni divertenti e disegnate a mano (dell'autore che è uno sviluppatore principale di Etsy) per spiegare alcune delle strutture di dati presenti in questo articolo.

Oppure puoi dare un'occhiata al mio video corso basato su quel libro: Algorithms in Motion from Manning Publications. Ottieni il 39% di sconto sul mio corso utilizzando il codice "39carnes"!