Why does inserting elements take so long?

Question

Algorithms

Hello!
I'm reading the book "Groaming Algorithms", in the section with arrays and lists there was a misunderstanding. Why does inserting elements into an array take O(n) time, but into a list O(1)?
Don't we need to first reach the last element in the list, and then create a link to a new element in it? Why constant time?
And in arrays I can’t even imagine why O (n).

Answer 1

About the list It's just that the author is cunning and believes that the task of obtaining a pointer to the desired element in the list is a separate search task, which is just done in O (n). Well, with the insert, everything is simple - it is really done in O (1). The fact that in practice the insertion often consists of a search and the insertion itself was swept under the carpet by the cunning author. Beware of cunning authors!
About the array It's easy to guess™ that when inserting into the array in the very first place, you need to shift the entire tail of the array by one element (so that there is a place where to insert). This shift, according to the most pessimistic (when we insert it at the very beginning) estimate, takes O (n).

Answer 2

Because in a list, we can insert an element anywhere