Wat is de schatting van de tijdcomplexiteit van de operatie om een element uit een enkelvoudig gekoppelde lijst te verwijderen?

De tijdscomplexiteit van het verwijderen van een element uit een enkelvoudig gekoppelde lijst hangt af van of we een pointer naar het te verwijderen element hebben of alleen naar de kop van de lijst.

• Als we een element moeten verwijderen, wetende alleen de kop van de lijst, moeten we eerst door de lijst lopen om het element en zijn vorige knooppunt te vinden. Dit kost O(n) tijd, waarbij n het aantal elementen in de lijst is.
• Als we een pointer naar het vorige element (of naar het te verwijderen element zelf, als het het eerste element is) hebben, gebeurt de verwijdering in O(1), omdat het voldoende is om de koppelingen opnieuw in te stellen.

Dus, over het algemeen, is het verwijderen van een element uit een enkelvoudig gekoppelde lijst een operatie met een tijdcomplexiteit van O(n).