Wat is de tijdsmaat voor de operatie van het invoegen van een element in het centrale deel van een dubbel gekoppelde lijst?

Het invoegen van een element in het centrale deel van een dubbel gekoppelde lijst vereist meestal eerst het vinden van de invoegpositie, wat O(n) tijd kost, omdat je door de lijst moet lopen tot het gewenste knooppunt.

Het daadwerkelijke invoegproces (het aanpassen van de pointers van de aangrenzende knooppunten) wordt uitgevoerd in O(1).

Samengevat:

• Zoeken naar positie — O(n)
• Invoegen — O(1)

Als de positie al bekend is (bijvoorbeeld, als je een pointer naar een knooppunt hebt), is het invoegen O(1). Zo niet, dan moet je eerst door de lijst lopen, wat O(n) geeft.