trekhleb / javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
MIT License
185.07k stars 29.85k forks source link

confusing insertion and deletion time complexity on linked list #1001

Closed happyuniv closed 1 year ago

happyuniv commented 1 year ago

on linked-list page and doubly-linked-list page time complexity on insertion is O(1) but on deletion is O(n) Why is it different? shouldn't deletion be O(1) or insertion be O(n) ?

lazarljubenovic commented 1 year ago

Insertion assumes appending to head/tail, so no traversal happens. Deletion means deleting a specific node, so you need to find it firstly.

vikash18o19 commented 1 year ago

@lazarljubenovic Exactly, In case of Insertion: I guess we have both the pointers, the head and the tail, had it been just the head, We would need to traverse the whole list to insert at the end and complexity would have been O(n). In case of deletion: as @lazarljubenovic mentioned we need to find the node first. thus, O(n). Issue: #1001 must have been resolved now.