CODEWITHSUNDEEP
c
Atul
Atul

Reputation: 1177

Choosing a data structure

Different Data structures are used according to requirement but how would I know which data structure should I use? I just want to know how to choose an appropriate data structure ? Thanks

Upvotes: 3

Views: 4005

Answers (6)

Billy ONeal
Billy ONeal

Reputation: 106530

This flowchart is for the STL in C++, but you could implement any of the data structures supported by the STL containers in C.

  • List is a linked list
  • Vector is a dynamic array
  • Deque is something like a list of dynamic arrays -- sort of splits the difference.
  • Queue and Priority queue are like they say (usually queue is implemented in terms of deque, priority queue is usually implemented in terms of a heap inside a vector or deque)
  • Set/Map/Multiset/Multimap are all implemented using some form of balanced binary tree.

Update 2016: Apparently the image I used to link to here has been link-rotted, but you can see several equivalent images over at this question: In which scenario do I use a particular STL container?

Upvotes: 8

Andrew Hill
Andrew Hill

Reputation: 2020

Each data structure has different costs for different types of actions: you should ask yourself:

  1. do i need to be able to find a specific element (give me the person called "bob") ?
  2. do i care about the order (ie, regularly find the first or last)?
  3. do i need to be able efficiently delete records other than the last?
  4. do i need random access (give me the 20th) ?
  5. do i need to be able to have efficient multithread read and write?

note: a question not on the list is "do i need to be able to iterate through everything in the store" as all practical data stores are able to access all N elments in O(n) time

also, all these comments are generalizations:

if the answer to 1. is "yes" then that rules out various un-ordered array type structures (vectors, unsorted arrays, linked lists)

if the answer to 2. is "yes" then that rules out hash based stores (hashmap, etc ...) as they give up a predictable order in order to aid search efficiency. you probably need a treeset or ordered list.

if the answer to 3. is "yes" then that rules out list based (unsorted arrays, linked-lists) and you probably need a treeset, ordered list, or hash map.

if the answer to 4 is "yes" then that rules out hashmaps and linked lists (note, this is a different question to 1, as hashmaps store everything based on an index, they don't store them in any specific order)

if the answer to 5 is "yes" then asking a question with your specific requirements is probably the way to go, as this complicates every answer given on the previous points (linked lists, hashmaps and slowly growing arrays allow efficent parallel implementations, sorted anything is hard to do in parralel).

if you're wondering why tree-set is on all those options but is not generally recommended; it's because if the answer to 2 is "no", then hashmap is typically better (time to add and remove elements increases much slower than treeset as the collection grows). similarly if the answer to any of the other questions is 'no' then there are better recommendations.

in general: if you need random access, hashmap. if you need sorted treeset, otherwise a linked list. (these all come with a memory overhead compared to a straight array, so i've assumed memory isn't highly restrictive)

Upvotes: 1

user3280137
user3280137

Reputation: 1

If your concern is fast and efficient searching then which data structure you will choose to store the data? Give reasons to justify your selected data structure.

Upvotes: 0

user147373
user147373

Reputation:

Not what you are looking for, but it depends.

It depends on the data that you are storing, any constraints on accessing that data, do you need to be able to look things up really fast? Does it need to maintain any kind of sort on the data? Will you be sorting it later?

Even when you choose a data structure (Linked List, Map, Set) there a numerous variants among them that might further drive your decision.

My rule of thumb is this:

Go with the simplest that you can until you know otherwise that you need something more complicated.

Upvotes: 0

Jonathan Wood
Jonathan Wood

Reputation: 67195

It's hard to answer without knowing what parts of the decision are giving you trouble.

For the most part, you want the smallest and simplest data structure that will hold the data you need to store.

Was there one particular case that was giving you trouble?

Upvotes: 0

Justin Niessner
Justin Niessner

Reputation: 245399

You need to research which data structures are used to meet which requirements (there's nobody here that is going to go through the time to spell out every option for you and tell you exactly when to use it).

Once you know the details, you should be able to (with a decent amount of certainty) pick the appropriate Data Structure for your needs.

Upvotes: 2

Related Questions