-
Notifications
You must be signed in to change notification settings - Fork 0
3.03 Linked List
La linked list salva i dati attraverso dei nodi che puntano ad altri nodi.
- Indexing: O(n)
- Ricerca: O(n)
- Inserimento: O(n)
Il motivo principale per usare una Linked List invece di un array è il fatto che gli elementi possono essere rimossi, aggiunti o spostati senza riallocare o riorganizzare l'intera struttura. Infatti "ristrutturare" un array a tempo di esecuzione è un'operazione molto più costosa.
D'altra parte, siccome le linked list semplici di per se non consentono l'accesso randomico ai dati, o qualsiasi altro tipo di indexing efficiente, molte operazioni basilari, come ottenere l'ultimo nodo della lista, trovare un nodo che contiene una data key, oppure trovare una posizione dove un nuovo nodo deve essere inserito, potrebbe richiedere l'iterazione sulla maggior parte degli elementi.