Array dinamico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Supporto linguaggio: In inglese l'ordine sintattico è diverso dall'italiano: "language support" non può tradursi "supporto linguaggio" (che, inoltre, è pure una frase non ben formata in italiano) |
|||
Riga 35:
! !!Lista<br />concatenata!!Array!!Array<br />dinamico
|-
|Indicizzaz
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ddffdd"|Θ(1)
Riga 65:
Gli array dinamici beneficiano di molti vantaggi degli array, inclusa una buona [[località di riferimento]] e l'utilizzo di [[CPU cache|cache dati]], compattezza (basso utilizzo di memoria), e [[accesso casuale]]. In genere hanno solo un piccolo [[overhead|socraccarico addizionale]] ([[overhead]]) per memorizzare le informazioni su dimensione e capacità. Questo rende gli array dinamici uno strumento attraente per la costruzione di strutture dati ''cache-fliendly''.
Paragonati alle [[lista concatenata|liste concatenate]], gli array dinamici hanno un'indicizzazione più rapida (tempo costante contro tempo lineare) e tipicamente anche una più rapida iterazione
elementi seguenti devono essere spostati, mentre le liste concatenato possono farlo in tempo costante. Questo svantaggio è mitigato dal [[buffer gap]] e dalla variante ''vettore graduato'' discusso nel paragrafo ''Varianti'' più
sotto. Inoltre, per una regione di memoria altamente [[Frammentazione (informatica)|frammentata]], può essere dispendiosa o impossibile trovare uno spazio contiguo per un grosso array dinamico, mentre le liste concatenate non richiedono che l'intera struttura dati sia memorizzata in maniera contigua.
| |||