Skip to content
loading...

re: Data Structures & Algorithms in JavaScript(Single Linked List) Part 1 VIEW POST

FULL DISCUSSION
 

Your complexity for insert at any position is incorrect as it does not take into account the additional getElementAt. That being said you can get rid of that func call by simply using a trailing "pointer".

 

Yes, you can get rid of the function and simply use a trailing pointer, But loop until the desired index is common in linked list methods, so instead of rewriting the same code, again and again, I have extract into a function. And the complexity of the find the desired position in the linked list is O(n) once you know it required constant time to insert.
So to insert at any position, first you have the position, I.e 0(n) and insert the element I.e O(1),
To compute O-notation we will ignore the lower order terms since the lower order terms are relatively insignificant for large input. That's why the complexity is O(n).

 

Your insert calls this.getElementAt to get the previous, that is not O(1).

That trailing pointer can make the difference between serving a response and not serving anything in a production setting ;) Every cycle counts, even on 32 cores and 128GB of RAM...

code of conduct - report abuse