Big O Notation Arrays vs. Linked List insertions

Question

O(1) accurately describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you'd have to resize an array if it's full.

For linked list, you have to traverse the list to do middle insertions, so that's O(n). You don't have to shift elements down though.

There's a nice chart on wikipedia with this: http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays

                          Linked list   Array   Dynamic array   Balanced tree

Indexing                          Θ(n)   Θ(1)       Θ(1)             Θ(log n)
Insert/delete at beginning        Θ(1)   N/A        Θ(n)             Θ(log n)
Insert/delete at end              Θ(1)   N/A        Θ(1) amortized   Θ(log n)
Insert/delete in middle     search time 
                                + Θ(1)   N/A        Θ(n)             Θ(log n)
Wasted space (average)            Θ(n)    0         Θ(n)[2]          Θ(n)

Assuming you are talking about an insertion where you already know the insertion point, i.e. this does not take into account the traversal of the list to find the correct position:

Insertions in an array depend on where you are inserting, as you will need to shift the existing values. Worst case (inserting at array[0]) is O(x).

Insertion in a list is O(1) because you only need to modify next/previous pointers of adjacent items.