Originariamente inviato da Marco1995
Diamo per assurdo che ho un array che in memoria pesa 100megabyte...e io ho in ram 2Gb disponibili...solo che non riesco ad ottenere 100Mb contigui perchè sono tutti frammentati...in questo caso dovrei utilizzare una lista..l'esigenza delle liste non nasce anche per quel motivo?(Ovviamente non è il mio caso . .)
Questo è vero, ma, se il tuo programma non fa altro, 100 MB di memoria contigui si trovano eccome ti direi che normalmente sotto il giga non si hanno mai problemi se non ci sono altre allocazioni grosse in ballo, visto che gli allocatori decenti evitano di sparpagliare le "piccole allocazioni" in giro per lo spazio di indirizzi. Poi ora con spazi di indirizzi a 64 bit il problema sostanzialmente non si pone più.

Da un punto di vista di memoria occupata "in assoluto", poi, una lista concatenata prende più spazio - per ogni elemento, oltre allo spazio per il payload, hai bisogno anche dello spazio per i due puntatori, più lo spazio usato dall'allocator per tenere traccia di tutte le allocazioni per i singoli nodi. Con un vettore invece ti limiti ad allocare un blocco di memoria e finita lì (e se non basta, riallochi raddoppiando le dimensioni, arrivando alle dimensioni definitive in tempo logaritmico nel numero degli elementi).