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

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 24, 2017 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$
    – Max Koretskyi
    Commented Apr 24, 2017 at 9:22

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
2
  • $\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$
    – Max Koretskyi
    Commented Apr 24, 2017 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
    Commented Apr 24, 2017 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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