Complessità dell'algoritmo inserire un elemento in un elenco collegato circolare all'estremità anteriore

Question

In un elenco collegato circolare, se un elements esigenze da inserire anteriore [poco prima del nodo puntato da testa], può essere realizzata in O (1) (si veda la risposta qui )

Ma in un libro attualmente, ho, si dice che si è fatto in O (n) (il solito metodo). Ho visto anche alcuni punti percentuali di lezione, tutti menzionano il solito metodo di attraversare la lista e l'aggiunta di un elemento.

La mia domanda è:

1. In scenari pratici quale metodo viene utilizzato?

2. Sono in procinto di partecipare ad un esame, che consiste di MCQs, se sopra domanda viene posta devo marchio O (n), dal momento che è la risposta standard?

Answer 1

Il metodo utilizzato in scenari pratici dipende dallo scenario (e sul programmatore). Ci sono diversi problemi possibili che influenzano la scelta di implementazione:

1. Se l'algoritmo è noto per il programmatore.
2. Facilità di codifica (è più facile se è già implementato in qualche biblioteca è possibile utilizzare).
3. Velocità -. Che dipende da come viene utilizzata la struttura di dati
4. Spazio in testa presa dalla struttura di dati.

Un programmatore intelligente dovrebbe prendere tutti questi in considerazione, e cercare di rendersi più consapevole dei vari algoritmi e strutture dati.