I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new array, then copy elements from the previous one which is a linear operation itself (invoked log(n) times, where n is the number of insertion operations). Are there better implementations of such data structure while preserving constant item access time? For example, how about implementing a concept known from disk file systems - an allocation table; whenever we need to extend our array, an allocation table entry is created for newly reserved memory, without touching previously inserted items. Indexing time could still be constant, if only the allocation table would be implemented wisely (for example with using constant "page" size) What I've written could be complete nonsense; it's just an idea.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time amortized.
Your idea is no different from a linked list of arrays of fixed size (correct if I'm wrong). If the list gets really large, looking for an element will take a lot of time.
