In the Python course chapter on data structures, it is stated that linked list insertions have a space complexity of 0(1).
Why is that the case?
I understand that the insertion itself should have a space complexity of 0(1). However, because you’re inserting at a “random index” of a singly linked list, shouldn’t the space complexity of iterating over each node before insertion be taken into account?
In other words how should the concepts of space/time complexities be isolated from processes/concepts/steps leading up to (in this case) the “insertions”?
Iterating over each node is taken into consideration when talking about time complexity of inserting. For space complexity there’s no difference - each insert will need0(1) space.
I think I kind of understand your reasoning - after all, with each insertion list is getting bigger. That’s true, however when referring solely to the single operation - ie. insertion - that value is constant, as far as the space complexity goes.
