Войти в систему
Войти с помощью соц. сетей:
After our analysis, it emerges that the comparison of linked lists and arrays breaks down as follows:
Operation | Array | Linked list |
|---|---|---|
Reading | O(1) | O(N) |
Search | O(N) | O(N) |
Insertion | O(N) (O(1) at end) | O(N) (O(1) at beginning) |
Deletion | O(N) (O(1) at end) | O(N) (O(1) at beginning) |
In the grand scheme of things, linked lists seem to be lackluster when it comes to time complexity. They perform similarly to arrays for search, insertion, and deletion, and are much slower when it comes to reading. If so, why would one ever want to use a linked list?
The key to unlocking the linked list’s power is in the fact that the actual insertion and deletion steps are just O(1).
But isn’t that only relevant when inserting or deleting at the beginning of the list? We saw that to insert or delete elsewhere, it takes up to N steps just to access the node we want to delete or insert after!
Well, it just so happens that there are scenarios in which we may already have accessed the right node for some other purpose. The next example is a case in point.
Войти с помощью соц. сетей: