Care este complexitatea temporală a operațiunilor de inserare, ștergere și căutare a elementelor într-o listă simplu înlănțuită?

Într-o listă simplu înlănțuită, operațiile au următoarele complexități temporale:

• Inserare:

  • La începutul listei — O(1), deoarece este suficient să schimbăm pointerul capului.
  • La sfârșitul sau într-un loc arbitrar — O(n), deoarece trebuie să parcurgem lista până la poziția dorită.

• Ștergere:

  • Ștergerea primului element — O(1).
  • Ștergerea unui element după valoare sau poziție — O(n), deoarece trebuie să găsim elementul și nodul anterior.

• Căutare:

  • Căutarea unui element după valoare — O(n), deoarece trebuie să parcurgem lista secvențial.

Prin urmare, operațiile de inserare și ștergere la începutul listei sunt foarte rapide, în timp ce celelalte necesită timp liniar din cauza necesității de a parcurge lista.