It is said that the complexity of the LinkedList remove and the add operation is of O(1)
. and in case of ArrayList
it is of O(n)
.
Calculation for ArrayList of size "M" : if i want to remove the element at Nth position then i can directly go to the Nth position using index in one go (i don't have to traverse till Nth index) and then i can remove the element, till this point the complexity is O(1) then i will have to shift the rest of the elements(M-N shifts) so my complexity will be linear i.e. O(M-N+1). and hence deletion or insertion at the last will give me the best performence( as N ~ M) and deletion or insertion at the start will be worst (as N ~ 1).
Now the LisnkedList of size "M" : as we can not directly reach the Nth element in the LinkedList, to access the Nth element we have to traverse N elements, so the search in the LinkedList is costlier then the ArrayList...but Remove and the add operations are said to be of O(1) in case of LinkedList as, in LinkedList the Shift is not involved, but there is traverse operation involved rigth ? so the complexity should be of order O(n) where Worst performence will be at the tail node and best performence will be at the head node.
Could anyone please explain me why don't we consider the traverse cost while calculating the complexity of LinkedList remove operation ?
So i wants to understand how it works in java.util package. and if i want to implemet the same in C or C++ how would i achieve the O(1) for random deletion and insertion in LinkedList ?
The Space Complexity of the above Linked List operations is O(1). This is because we do not need extra space beyond a fixed number of variables. For some operations, you may need extra space of the order of O(N). For example, sorting a Linked List using a sorting algorithm that is not in-place.
Worst time complexity for inserting into list is O(n-i) , where n is the length of the list and i is the index at which you are inserting. So in case if you are inserting at the last index, that makes it O(1) .
The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before.
In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).
Remove and the add operations are said to be of O(1) in case of
LinkedList
as, inLinkedList
the shift is not involved, but there is traverse operation involved right?
Adding to either end of a linked list does not require a traversal, as long as you keep a reference to both ends of the list. This is what Java does for its add
and addFirst
/addLast
methods.
Same goes for parameterless remove
and removeFirst
/removeLast
methods - they operate on list ends.
remove(int)
and remove(Object)
operations, on the other hand, are not O(1). They requires traversal, so you correctly identified their costs as O(n).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With