0
$\begingroup$

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)

Can anyone please explain why:

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

Thanks

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 24 '17 at 9:18
  • $\begingroup$ @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. $\endgroup$ – Maxim Koretskyi Apr 24 '17 at 9:22
1
$\begingroup$
  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)$.

$\endgroup$
  • $\begingroup$ great, thanks. re 2 - I'm always forgetting that n/2 is "shortened" to n. re 1 - can you please provide an example? $\endgroup$ – Maxim Koretskyi Apr 24 '17 at 9:14
  • $\begingroup$ @Maximus It depends on the actual policy, but usually when a dynamic array becomes less full than a given % threshold, you reallocate it to reclaim memory. A simple policy could be: on insertion, if there's no space, double the length of the array. On removal, if less than 25% is full, half the length of the array. The actual % may vary. $\endgroup$ – chi Apr 24 '17 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.