Komplexität des Algorithmus, das ein Element in einer kreisförmigen verknüpften Liste am vorderen Ende einfügt

Question

Wenn in einer kreisförmigen verknüpften Liste ein Element vorne eingefügt werden muss [kurz bevor der von Kopf gezeigte Knoten], kann er in O (1) durchgeführt werden (siehe Antwort hier)

Aber in einem Buch, das derzeit ich derzeit habe, wird erwähnt, dass es in O (n) (der üblichen Methode) erfolgt. Ich habe auch nur wenige Vorlesungs -PPTs gesehen, sie alle erwähnen die übliche Methode, um die Liste zu durchqueren und ein Element hinzuzufügen.

Meine Frage ist :

1. Welche Methode wird in praktischen Szenarien verwendet?

2. Ich bin kurz davor, an einer Prüfung teilzunehmen, die aus MCQs besteht, wenn oben gestellt wird, soll ich o (n) markieren, da dies die Standardantwort ist?

Answer 1

Die in praktischen Szenarien verwendete Methode hängt vom Szenario (und vom Programmierer) ab. Es gibt mehrere mögliche Probleme, die die Auswahl der Implementierung beeinflussen:

1. Ob der Algorithmus dem Programmierer bekannt ist.
2. Einfache Codierung (es ist am einfachsten, wenn es bereits in einer Bibliothek implementiert ist, die Sie verwenden können).
3. Geschwindigkeit - Das hängt davon ab, wie die Datenstruktur verwendet wird.
4. Space Overhead von der Datenstruktur.

Ein intelligenter Programmierer sollte all dies berücksichtigen und versuchen, sich über verschiedene Algorithmen und Datenstrukturen zu informieren.