Quote:
Originariamente inviato da gehur
forse non è la sezione giusta, ma non sapevo dove postare..
la domanda è la seguente: perchè nelle tabelle hash con liste di collisione bidirezionali il tempo di cancellazione è O(1) mentre con liste si collisione unidirezionali il tempo è O(n)??
|
Sezione giusta direi.
Deriva dal fatto che nelle liste doppio linkate la cancellazione si fa in O(1), mentre nelle liste a single link la cancellazione si fa in O(N).
(In realta' per le hashtable non e' corretto dire O(1) e O(N), ma occorrerebbe dire O(1) e O(M), dove M e il ratio di collisione, ovvero quanti elementi hanno in media la stessa hash, ovvero quando e' appunto in media lunga la lista di collisione nelle hashtable gestite con liste di collisione)
Per cancellare un elemento da una lista linkata occorre aggiornare i puntatori degli elmenti che vi puntano.
Nella doppio likata, per sapere su quali elementi agire quindi e' sufficiente andare a leggere il nodo stesso, che contiene per definizione il successore e il precedente, che dovranno essere aggiornati come se l'elemento da cancellare non esistesse piu'. Quindi O(1), ovvero un numero fisso e costante di operazioni da fare indipendente dalla lunghezza della lista stessa.
Per quanto riguarda invece la lista single linkata (ad esempio in avanti), non sappiamo qual e' l'elemento precedente che deve essere aggiornato puntando al successivo, semplicemente leggendo il nodo da cancellare.
Occorrera' seguire la lista dall'inizio per trovare l'elemento precedente, per poi poterlo aggiornare. Seguire dall'inizio costa O(N).