Ho sentito lati contrastanti da questo argomento. Avevo l'impressione che una lista collegata fosse un modo per implementare una struttura dati (stack, coda), non in realtà una struttura dati.
Ho sentito lati contrastanti da questo argomento. Avevo l'impressione che una lista collegata fosse un modo per implementare una struttura dati (stack, coda), non in realtà una struttura dati.
Ahimè! java.util.LinkedList non è una struttura dati di per sé.
Questo significa che anche una matrice non è una struttura dati? o albero binario (perché è usato per implementare una SortedMap o un Heap)?
Chiediti: "Sono dati? è strutturato?" se la risposta a entrambi è "sì", allora, hai una struttura dati di qualche tipo. Dare una lettura alla struttura dei dati di Wikipedia
Il fatto che una data struttura sia utilizzata per implementare altre cose non significa che non sia una struttura stessa.
Gli array vengono utilizzati per implementare array flessibili. Gli array flessibili vengono utilizzati per implementare la parte della tabella hash di una mappa (o dizionario se invece la tua lingua usa quel gergo). Le liste collegate possono essere pensate come (tipo di sbagliato, ma sopportato da me) come forma specializzata di un albero (un solo ramo). Gli alberi vengono utilizzati per implementare ... bene, heap s, mappe ordinate , b alberi (che si trovano spesso negli indici nei database e nei file system). L'elenco può andare avanti e avanti e avanti (e non è un elenco completo).
Alcune di queste cose che ho citato sono confuse nella loro implementazione. Si può implementare una mappa con una tabella hash (supportata da un array) - una HashMap , un albero rosso-nero (una particolare implementazione di un albero binario bilanciato - sii contento che non sia un albero avl) come SortedMap , o anche liste collegate come ConcurrentSkipListMap . La cosa fondamentale è come si comportano - tutte queste implementazioni implementano un insieme degli stessi metodi garantendo che abbiano tutti un get(K) e put(K, V) (insieme ad altre cose).
L'elenco collegato (implementazione concreta) è un modo particolare di implementare un elenco (un tipo di dati astratto). Potresti farlo anche con un array flessibile (un'altra implementazione concreta).
L'utilizzo di una struttura come fondamento per un'altra struttura non lo rende meno di una struttura. Il punto chiave nella struttura dei dati è che ci sono dati, ed è strutturato in qualche modo in modo da sapere dove cercare i suoi componenti.
Leggi altre domande sui tag data-structures data linked-list