Dynamic array | Sololearn: Learn to code for FREE!


Dynamic array

I was thinking about a data structure which would guarantee constant indexing and constant addition. It would differ from normal dynamic arrays as addition of a new item wouldn't be amortized. The idea is to provide an array with fixed sized in which the last item would point to a new array if the data structure needs to grow. That way I would avoid copying the array when capacity is reached. Also, there would be a pointer which points to the current last item so that I can know where to add a new item. Finally, of course, I would keep track of the amount of inner arrays that have been created. What do you think of this idea? Would it be efficient?

2/12/2019 3:13:29 PM


2 Answers

New Answer


Okay. The idea you are suggesting is already present, not exactly, buy similar. There is a data structure called linked list. In linked list, you can expand the array on the go just like you said. Please do look up linked list on Google once. It's really great if you thought about that on your own though. Noice


I am aware of linked lists. However, they do not provide constant indexing, as a matter of fact, indexing is O(n) which is not that good compared to dynamic arrays. With my idea, I was thinking about providing constant indexing as in dynamic arrays and constant addition as in linked lists. Just like a mix of this two data structures