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?
1 Answers
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.
Related