The marked Circle in red . Shouldn’t that be O(1) for Middle and End Deletion (Linked List)
Deleting from the middle is always an O(n) operation. Deleting the last element is O(n) for a singly linked list since you have to traverse the whole list to find the element before the last element while it’s O(1) for a doubly linked list.
2 Likes
ya i meant O(n) for both middle and end for singly linked list
I also disagree with the slide stating that an insert at the Beginning and End are both O(1) operations.
Inserting at the beginning is O(1), but inserting at the end is an O(n).
2 Likes
Inserting at the end of a single linked list is constant time if you keep a pointer to the end of the list (which is precisely the implementation Mosh shows).
1 Like