2
$\begingroup$

Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations.

Is this because insertion operations are not defined on the array ADT?

$\endgroup$
  • 1
    $\begingroup$ Please ask only one question per post. I removed the second one (note that it's still available here); please repost on its own -- if it's not already been answered here, here or here. $\endgroup$ – Raphael May 25 '16 at 9:20
  • $\begingroup$ @Raphael - sorry, but your revisions to my question were too heavy-handed IMO. $\endgroup$ – Ben May 25 '16 at 9:34
  • $\begingroup$ The linked article contains specific values for insertion/deletion complexity in both dynamic and fixed-size arrays. $\endgroup$ – Rick Decker May 25 '16 at 14:58
1
$\begingroup$

The array is a fixed-size data structure, and insertions would change its size. Thus they are impossible, which is why Wikipedia says "N/A" for the insertion complexity.

A dynamic array can have its size changed, which is why complexities are given in that column.

$\endgroup$
  • $\begingroup$ "The array is a fixed-size data structure" - should this be ADT? $\endgroup$ – Ben May 25 '16 at 16:47

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.