Comments on: Array vs. Linked List

By: Fatih

Fatih — Thu, 26 Oct 2023 16:02:23 +0000

Thank you for your informative article.

Much love

By: Sven Woltmann

Sven Woltmann — Mon, 26 Dec 2022 14:10:00 +0000

The answer is: it depends :-)

If you want to insert an element at a certain index and you only have the reference to the first node, then you are right. Then the complexity is O(n), because you have to find the node first. (That is unless you use a "skip list" where the complexity to find an element by its index is O(log n).)

But if you already have a pointer to that node, the complexity is O(1).

If you are implementing an algorithm where you frequently insert/remove items from the middle of a list, implementing with a linked list makes sense if you can somehow keep track of those pointers.

I have added this constraint to the corresponding sentence in the article. Thank you for pointing out this ambiguity!

By: Pushkar

Pushkar — Sun, 25 Dec 2022 14:31:16 +0000

Regarding your point on "the time complexity for inserting into and removing from a linked list is: O(1)". Per my understanding it should be O(n) as we need to traverse to particular position to insert the node.

Please let me know if there is any correction.