# Insertion and deletion complexities for a linked list and array

I have the following table that compares different operation complexities for a linked list and array:

                        Linked List |   Array   |   Dynamic Array
Deletion at ending      O(n)        |   O(1)    |   O(n)
Insertion in middle     O(n)        |   O(n)    |   O(n)
Deletion in middle      O(n)        |   O(n)    |   O(n)


1. Deletion for Dynamic Array is O(n)?
2. Insertion and deletion in middle for all data structures is O(n)?

Thanks

• OK, that's a couple of rather basic questions you've asked in rapid succession. I suggest you try a bit harder to work these things out for yourself before asking. To see the answers for arrays and linked lists, you shouldn't need to do much more than think about how you would insert or delete an entry from the data structure. Dynamic arrays are a little more complicated but any description of them will surely include the analysis. – David Richerby Apr 24 '17 at 9:18
• @DavidRicherby, the table I'm getting the values from are quite big, but I've asked only a few things I don't understand from it. I've done my homework, so I find your comment inappropriate. – Maxim Koretskyi Apr 24 '17 at 9:22

1. The array may need to be reallocated if there are too many free cells, and this costs $O(n)$ (non-amortized)
2. For arrays, the array portion which comes after the affected element must be moved one position left or right, so that's $O(n)$. For lists, it depends. If you have the pointer to the previous cell w.r.t. the inserted/deleted one, this can be done in $O(1)$. If you don't, and you only have the pointer to the list head, then you have to scan the list -- half the list, on average, will be scanned, costing $O(n)$.
• great, thanks. re 2 - I'm always forgetting that n/2 is "shortened" to n. re 1 - can you please provide an example? – Maxim Koretskyi Apr 24 '17 at 9:14