Sì, è la sezione giusta.
E' la sola operazione di rimozione che è O(1), c'è sempre il costo relativo alla ricerca dell'elemento da eliminare che è proporzionale alla lunghezza.
Con una lista uniderezionale per rimuovere un elemento bisogna invece fare sempre la ricerca, ma bisogna anche ricercare l'elemento precedente in modo da linkare questo elemento a quello successivo a quello da eliminare.
Questo costo aggiuntivo è però facilmente eliminabile, diciamo che se la ricerca dell'elemento viene fatta con cognizione di causa allora verrà mantenuto anche il puntatore all'elemento precedente così che sarà possibile fare l'eliminazione dell'elemento dalla lista in O(1)
Ad esempio:
Codice:
struct list
{
int info;
struct list *next;
} *l;
void elimina(int i, struct list **l)
{
struct list *current = *l, *prev = *l;
while(current->info != i && current != NULL)
{
prev = current;
current = current -> next;
}
if(current == NULL)
return;
if(current == prev)
*l = current->next;
prev->next = current->next;
free(current);
}
Qui la lista è unidirezionale eppure l'eliminazione è O(n)