CODEWITHSUNDEEP
c++data-structures
user2502162
user2502162

Reputation:

Fastest data structure for inserting data, not for searching

Can anyone please tell me which is the fastest data structure for inserting data. My requirements are to load names of people, and then retrieve them at super fast speed. There is no question of sorting, searching a specific name etc, not even memory, because total people may not be more than 20. The single requirement is load people and retrieve the names at a later stage. Does anyone have any idea?

Upvotes: 3

Views: 657

Answers (3)

Tarun Sharma
Tarun Sharma

Reputation: 115

If you are sure that total objects / nodes will always be less than 20 than array is the best. Retreival happens using index in array and is the fastest. If you are not sure of the size of datastructure, then I will suggest a list because insertion in a list is the fastest provided you are not looking for an order of insertion. If order of insertion is needed then go for linked list. Hashtable might not be an option because it has an extra overhead of synchronozation which is not needed here. A Set interface could be used if you want to avoid duplicates and you have no worries about the order of retrieval.

Upvotes: 0

Ed Heal
Ed Heal

Reputation: 60037

Apart from the tongue in check answer (it was my first thought) and you have at most 20 people, just use an array.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373482

Tongue-in-cheek answer: if you are only doing insertions and nothing else, the easiest data structure is nothing at all - just don't store anything. That makes insertions instantaneous, since you do absolutely nothing to do an insertion.

More realistic answer: if you are just trying to store a bunch of data as quickly as possible and you have an upper bound on the number of total elements, just use an array and keep track of the next free index. If the array stores pointers to elements, then each insertion is a pointer assignment plus an increment of the next free index. If you're storing copies, then each insertion makes a copy (which you'd have to do anyway) and an increment. Since any structure that stores elements has to either store a pointer or copy to it, the overhead is a single increment, which I'm fairly confident is about as cheap as it gets.

Hope this helps!

Upvotes: 10

Related Questions