Array dinamico: differenze tra le versioni

m
Annullate le modifiche di 94.38.224.111 (discussione), riportata alla versione precedente di 2.40.121.42
m (Annullate le modifiche di 94.38.224.111 (discussione), riportata alla versione precedente di 2.40.121.42)
!&nbsp;!!Lista<br />concatenata!!Array!!Array<br />dinamico
|-
|Indicizzazione
|Indicizzaz
|style="background:#ffdddd"|Θ(''n'')
|style="background:#ddffdd"|Θ(1)
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 grrgrazie alla migliore località di riferimento; tuttavia, gli array dinamici richiedono un tempo lineare per inserire o cancellare su una locazione arbitraria, dal momento che tutti gli
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.