La bufala delle liste linkate

[dobermann77]

Le liste linkate non servono a niente. Consideriamo una lista linkata semplice in C. Il nodo è di questo tipo

struct nodo_lista {
int valore1;
...
int valoren;
struct nodo* nodosuccessivo;
}

Le liste linkate sono fatte di nodi, e ogni nodo contiene un puntatore all'elemento successivo della lista.

**********

Quando si parla di pregi e difetti delle liste linkate, le si confronta coi vettori di tipo elemento_vettore.

struct elemento_vettore {
int valore1;
...
int valoren;
}

Le strutture potrebbero essere grandi, e questo complica effettivamente la rimozione e l'inserimento di nuovi elementi.

******

Quello che pero' non si fa mai è confrontare le strutture con vettori di puntatori a elemento_vettore.
In questo caso, la rimozione e l'inserimento comporta lo spostamento di puntatori, che sono oggetti piccoli.
Si mantiente il vantaggio del tempo di accesso O(1).

L'unico vantaggio delle linked list è che sono "totalmente splittate" nell'heap, i blocchi allocati contigui sono molto piccoli,
mentre il vettore di puntatori potrebbe essere grande (ma puo' essere grande un vettore di puntatori?)

BAH
Dove sbaglio?

[Oceans11]

Quello che pero' non si fa mai è confrontare le strutture con vettori di puntatori a elemento_vettore.
In questo caso, la rimozione e l'inserimento comporta lo spostamento di puntatori, che sono oggetti piccoli.
Si mantiente il vantaggio del tempo di accesso O(1).


Non è esattamente così.
Nell'inserimento ti puoi trovare in 2 casi:

1) il vettore non è pieno. Ma per inserire devi scandire l'intero vettore prima di trovare un elemento vuoto.
2) il vettore è pieno. Che fai in questo caso?

[dobermann77]

Non è esattamente così.
Nell'inserimento ti puoi trovare in 2 casi:

1) il vettore non è pieno. Ma per inserire devi scandire l'intero vettore prima di trovare un elemento vuoto.
2) il vettore è pieno. Che fai in questo caso?

1) Nel vettore non ci sono elementi vuoti, se non eventualmente in fondo. Per inserire un elemento devo creare un buco spostando quelli successivi. Operazione comunque ridicola se sono puntatori, sposto puntatori non le strutture dati.
2) Se il vettore è pieno, lo copio in un'altra area di memoria piu' grande.
(vedi CAPACITY della classe C++ vector)

[Oceans11]

1) Nel vettore non ci sono elementi vuoti, se non eventualmente in fondo. Per inserire un elemento devo creare un buco spostando quelli successivi. Operazione comunque ridicola se sono puntatori, sposto puntatori non le strutture dati.
2) Se il vettore è pieno, lo copio in un'altra area di memoria piu' grande.
(vedi CAPACITY della classe C++ vector)

e ti sembra di mantenere l'O(1)?
tanto per precisare, su architetture a 64bit succede spesso che un intero occupi 4byte, mentre un puntatore 8, il doppio. Quindi sti puntatori non sono così economici. Nelle liste non si spostano strutture dati, chiaro.

[nico159]

Si mantiente il vantaggio del tempo di accesso O(1).
Spiega meglio questo punto :)
Non tutti gli algoritmi permettono di mantenere l'accesso in O(1) se gli oggetti cambiano posizione all'interno di un vettore

Da che testo stai studiando?

[dobermann77]

Voglio inserire un nuovo nodo in posizione n.

Nel vettore di puntatori i dati sono contigui, basta un memcpy degli elementi successivi per creare lo spazio.
Per le liste si deve tenere conto dell'algoritmo che percorre la lista fino alla posizione giusta.

Mah... quale ci mette di meno?

Guardate su QUALUNQUE sito, fanno confronti tra liste e vettori di strutture, non vettori di puntatori a strutture.

Comunque ora scrivo un bench...

[vendettaaaaa]

Voglio inserire un nuovo nodo in posizione n.

Nel vettore di puntatori i dati sono contigui, basta un memcpy degli elementi successivi per creare lo spazio.
Per le liste si deve tenere conto dell'algoritmo che percorre la lista fino alla posizione giusta.

Mah... quale ci mette di meno?

Guardate su QUALUNQUE sito, fanno confronti tra liste e vettori di strutture, non vettori di puntatori a strutture.

Comunque ora scrivo un bench...
Come dice Andrei Alexandrescu (e il buon senso), finchè non misuri in modo preciso non puoi trarre delle conclusioni.

[Daniels118]

Se i vettori fossero migliori delle liste non si studierebbero le liste.
Se le liste fossero migliori dei vettori non si studierebbero i vettori.
Se i programmatori avessero buon senso non farebbero certe domande.

Scusate l'ironia, non è per offendere, ma quando si analizza un problema bisogna cercare di non essere di parte. Ogni soluzione ha i suoi pregi e i suoi difetti, come è stato giustamente osservato, i vettori hanno un tempo di accesso diretto o(1), ma il tempo per la modifica è variabile. Per esempio, per inserire un elemento in testa si ha una complessità o(n). Inoltre, se il vettore si riempe bisogna allocarlo da un'altra parte e copiare tutto il contenuto. Nelle applicazioni multithread questo determina anche l'obbligo di dover passare sempre per il puntatore al vettore, perché il puntatore agli elementi viene invalidato. Allocare un vettore più grande del necessario potrebbe essere uno spreco di memoria.
Le liste da parte loro, hanno sempre un tempo di accesso o(1) se si leggono gli elementi in sequenza, e la complessità rimane sempre o(1) per modificare/eliminare/aggiungere un elemento nella posizione del cursore. Inoltre consumano solo la memoria necessaria (se escludiamo i puntatori agli elementi stessi).

In linea di massima si può usare questa regola:
se (i dati cambiano poco) O ((si conosce a priori il numero massimo di elementi) E (le modifiche vengono fatte sempre in coda)), è preferibile usare un array;

se (i dati cambiano molto) E (se l'accesso agli elementi viene fatto sempre in sequenza) E ((il numero massimo di elementi non è noto a priori) O (le modifiche non avvengono solo in coda)), è preferibile usare una lista.

Per tutti i casi che non riescono a soddisfare contemporaneamente queste condizioni, la soluzione sta nel mezzo. Spesso chi progetta il programma non sa esattamente come avverrà l'accesso ai dati, perché questo potrebbe dipendere dall'input, quindi si fanno delle prove con dati che rispecchino una situazione reale.

Si potrebbe ad esempio realizzare una classe lista e un'altra vettore che implementino entrambe una stessa interfaccia d'accesso, e vedere quindi come cambiano le prestazioni utilizzando l'una o l'altra, senza cambiare una sola riga di codice del programma principale. Si potrebbe addirittura pensare un algoritmo euristico che sceglie quale classe istanziare in base ad un'analisi dei dati di input, il programma potrebbe poi trattare l'oggetto come istanza dell'interfaccia, senza dover implementare due gestioni separate per le due classi.