Comprensione degli aspetti macro delle strutture dati

Li definirei come l'interfaccia che forniscono, inclusa la complessità delle operazioni.

Si potrebbe in seguito implementare un elenco collegato con un array e viceversa (e in modo ricorsivo), ma sarebbe impossibile mantenere la complessità.

Aggiornamento: per chiarire: uno stack è definito come una infrastruttura con aggiunta costante al massimo e rimozione costante in cima. Non dice come lo implementiamo. Si potrebbe implementarlo usando un array, o un elenco collegato, ma anche un doppio elenco collegato, ma questo è irrilevante.

L'atomico che abbiamo su un computer è memmory (binario) e la forma più elementare di memmory è un array, quindi è possibile creare ogni tipo di datastructure usando un array.

Si potrebbe immaginare di avere un altro atomico (forse un qubit). Quindi uno stack sarebbe ancora uno stack, ma forse non potremmo implementarlo con quell'atomico.

Le pile, le code, gli heap, la tabella hash sono quelle che sono considerate strutture dati astratte. L'implementazione spetta a te implementare. È possibile utilizzare un elenco collegato per farlo o potrebbe essere necessario utilizzare un altro tipo di dati astratto per crearlo. Ad esempio, una coda di priorità può essere creata usando un min-heap che può essere creato usando un albero binario. L'implementazione dipende da te se segui le "regole" (ad es. Min-heap con un tempo di esecuzione per findMin costante o la ricerca di un valore in un hash-table costante, ci sono alcuni modi per farlo )

Sì, le proprietà emergenti degli array e delle liste concesse consentono loro di essere trattati come una struttura di dati "primitive", tuttavia ciò non significa che la lista collegata sia esattamente quale altra struttura usi sotto.

La cosa importante da rimuovere dalle liste concatenate è quella di puntare a punti arbitrari nella memoria, piuttosto che mantenere un raggruppamento sequenziale di slot di memoria. Se l'accesso casuale migliora le prestazioni di una struttura più astratta, allora vale l'ottimizzazione fornita da un array. Considerando che, l'uso di puntatori arbitrari ti offre una maggiore libertà di utilizzo della memoria.

Ad esempio, in Clojure a map viene implementato come una matrice sottostante fino a quando diventa più vantaggioso utilizzare un alto livello di astrazione, per il quale si disattiva l'implementazione.

Direi che devi sempre passare da macro (livello di sistema) a micro viste (diciamo a livello di funzione) se vuoi capire qualcosa fuori dalla programmazione dei sistemi medi o grandi.

Per passare da una vista all'altra, libri come:

The Art of Computer Programming di Donald E. Knuth (algoritmo a livello micro)

Algorithms di Rober Sedgewick (versioni in Java, C ++, C) (sia da macro ad algoritmo che da algoritmo a micro livello)

Manuale di progettazione dell'algoritmo di Steven Skienna (livello da macro a livello di algoritmo)

The Pragmatic Programmer di Dave Thomas, Andy Hunt

Di gran lunga, l'ultima parte di Algorithms in Java 4th Edition di Robert Sedgewick è quella che aiuterà a cambiare spesso questi micro e macro occhiali, ma senza perdere di vista il grande premio.