time complexity of insertion in different linked lists

In a homework problem, I have to find the average amount of elements that have to be moved when inserting a value into a sequential list. It asks, if there is a sequential list data structure of 127 elements, what is the average number of values that have to be moved when we add an element, or remove an element.

I supposes the average would be 127/2, or 63.

This got me wondering, how does the time complexity of insertion in a sequential list compare to that of a linked list?

https://stackoverflow.com/questions/66575888/time-complexity-of-insertion-in-different-linked-lists March 11, 2021 at 11:06AM