Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Array dinamico di puntatori o lista collegata?
Forum - C/C++ - Array dinamico di puntatori o lista collegata?

Avatar
AldoBaldo (Member)
Expert


Messaggi: 345
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 0:22
Domenica, 18/06/2017
Oggi mi annoiavo a vario titolo e, non avendo di meglio da fare, ho dato sfogo al mio squilibrio mentale mettendomi a sragionare astrattamente sui vantaggi e sugli svantaggi di due costrutti di immagazzinamento dei dati: gli array dinamici di puntatori e le liste collegate. Da tanto rimuginare non è emersa una gran chiarezza... a prima vista direi che un array dinamico di puntatori è più lineare da implementare e offre un accesso più "diretto" (non serve necessariamente scorrere gli elementi per trovare quel che serve), però non è che ne sia del tutto certo. Qualcuno ha voglia di dire quattro parole in merito?


Ma cosa vuoi che ne sappia? Io ci gioco, col codice, mica ci lavoro!
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6109
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 4:00
Domenica, 18/06/2017
Le liste collegate sono quasi sempre una brutta idea.

Bjarne Stroustrup (creatore del C++) spiega piuttosto bene il perche' qui (inglese): https://www.youtube.com/watch?v=YQs6IC-vgmo

Il problema principale e' che le liste collegate non permettono di sfruttare le cache della CPU (che hanno impatti enormi sulla performance).

C'e' poi il solito argomento di alcuni scolari che "le liste collegate permettono un inserimento efficente in mezzo alla lista, mentre gli array no", che cade quando si capisce che prima di inserire un elemento nel mezzo di una lista, praticamente sempre bisogna scorrere la lista per raggiungere il mezzo, che in termini di prestazioni, spesso e' piu' lento che copiare un intero blocco di memoria.

Le liste collegate offrono degli ottimi esercizi per imparare ad usare i puntatori.

Ultima modifica effettuata da pierotofy il 18/06/2017 alle 4:01


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
AldoBaldo (Member)
Expert


Messaggi: 345
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 22:12
Domenica, 18/06/2017
La questione dello sfruttamento o meno della cache credo passi un po' alto sopra alla mia testa. :(
Rimane il fatto che parlavo di array di puntatori, non di strutture dati, per cui anche inserire nel mezzo di una lista non dovrebbe essere tanto oneroso, considerando che un puntatore è solo 4 o al limite 8 bytes. Certo, a meno che si tratti di un array con milioni di elementi, ma a quel punto ogni procedimento sarebbe oneroso, no?
Per me che sono uno pseudoprogrammatore amatoriale, inoltre, risultano più semplici da trattare gli array di puntatori rispetto alle liste collegate, il che porta a chiedersi quanto possa valere la pena affrontare lo sforzo dell'apprendimento di un metodo poco famigliare (ovvero: vale la pena se porta vantaggi, se no, no). Per questo mi ponevo il quesito -- conviene restare su un terreno familiare o la differenza in termini di efficienza è tale da giustificare lo "sbattimento" per familiarizzare con un costrutto "alieno"?

P.S. il filmato lo guarderò domani, questa sera sono un po' bollito.


Ma cosa vuoi che ne sappia? Io ci gioco, col codice, mica ci lavoro!
PM Quote