Supponete di dover memorizzare N numeri interi (con N <= 100), e di poterlo fare o usando un array di 100 int, oppure utilizzando una lista, in cui ogni nodo contiene un intero e un puntatore al prossimo nodo.
Assumendo che sia un int che un puntatore occupino ciascuno 4 byte, qual è il massimo valore di N per cui l’uso della lista risulta conveniente in termini di memoria occupata (cioè, il massimo valore di N per cui la lista occupa strettamente meno byte dell’array)?
Soluzione: 49.
Osserva
- 100 int occupano 4*100 byte = 400 byte
- un nodo della lista occupa 2*4 byte = 8 byte
mentre la lista
- 1*8 byte = 8 byte
- 2*8 byte = 16 byte
- …
- 49*8 byte = 392 byte
- 50*8 byte = 400 byte
- 51*8 byte = 408 byte
- …