Why does linked list delete and insert operation have complexity of O(1) ? shouldn't it be of O(n)
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).
The complexity of removing is considered that you already have the pointer to the right position of the element you want to remove...
Is not considered the cost you took for finding it
Information on this topic is now available on Wikipedia at: Search data structure
+----------------------+----------+------------+----------+--------------+
| | Insert | Delete | Search | Space Usage |
+----------------------+----------+------------+----------+--------------+
| Unsorted array | O(1) | O(1) | O(n) | O(n) |
| Value-indexed array | O(1) | O(1) | O(1) | O(n) |
| Sorted array | O(n) | O(n) | O(log n) | O(n) |
| Unsorted linked list | O(1)* | O(1)* | O(n) | O(n) |
| Sorted linked list | O(n)* | O(1)* | O(n) | O(n) |
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n)** | O(n) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) |
+----------------------+----------+------------+----------+--------------+
* The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time.
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.