Care este măsura de complexitate a algoritmului pentru adăugarea unui element la începutul unei liste dublu înlănțuite?

Adăugarea unui element la începutul unei liste dublu înlănțuite se face în timp constant, adică are o complexitate O(1).

Acest lucru se datorează faptului că lista dublu înlănțuită are un pointer către primul element (cap), iar pentru a insera un nou element, este suficient:

1. Să creezi un nou nod.
2. Să-i setezi pointerul next la elementul curent de început.
3. Să setezi pointerul prev al elementului curent de început la noul nod.
4. Să actualizezi pointerul cap al listei la noul nod.

Toate aceste operații nu depind de dimensiunea listei, așa că complexitatea — O(1).