I am trying to understand why insertion and deletion in LinkList is O(1) rather than O(N) like in ArrayLists. The common explanation is that because LL is a formed from a doubly linked list you simply have to changes the references. But don't you still need to find the place where you are inserting or deleting to? Do you not traverse the LL to reach the address in question before you can even change the next and previous references making it a O(N) time?
Asked
Active
Viewed 170 times
2
-
How you conclude that the complexity of ArrayList insertion in O(n). it is not true. it is also O(1) – Sahan Dissanayaka Jul 11 '20 at 17:41
-
https://stackoverflow.com/q/2182597/10243797 is this your answer – Sahan Dissanayaka Jul 11 '20 at 17:43
-
1The arraylist would have to still update the rest of the elements of the array. So it would shift the n elements thus being O(n) – Arif Howlader Jul 12 '20 at 15:21
1 Answers
1
But don't you still need to find the place where you are inserting or deleting to? Do you not traverse the LL to reach the address in question before you can even change the next and previous references making it a O(N) time?
Not always. In many cases, a data structure can hold a reference (or pointer/iterator) directly to a node of a list. This reference help algorithms to quickly delete the node later (in O(1), without any traversal). For example, this can be the case on a network server handling a list of clients: a data structure containing contextual information about a client can reference a node in order to delete quickly a client from the list once the client is disconnected (so to scale well with the number of active client). In this case, no full traversal is needed.
Jérôme Richard
- 41,678
- 6
- 29
- 59