Choosing a data structure

Question

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

It depends what problem would you solve... give us more details... — IProblemFactory, Dec 20 '10 at 19:14
you answered it, 'different Data structures are used according to **requirement** '. — Lazer, Dec 20 '10 at 19:14
I'm not aware of simple answers to this problem. It's part of the learning process in the never-ending path to becoming a programmer. And it's also one of the things that makes it fun. There are often different data structures, patterns, algorithms, etc. that can be used in a problem. But it takes time, design, experience, teamwork, and many other factors to find the "best" one. — Mark Wilkins, Dec 20 '10 at 19:15

score 9 · Accepted Answer · edited May 23 '17 at 12:15

9

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?

edited May 23 '17 at 12:15

Community

1
1

answered Dec 20 '10 at 19:15

Billy ONeal

104,103
58
317
552

+1 LOL. That has been very handy. Wish I would have thougt of to post it. – Casey Dec 20 '10 at 19:19
@SoapBox: When the unordered containers are actually standard it probably will be (though I am not the author so I cannot say). – Billy ONeal Dec 20 '10 at 19:21
pretty neat! - it will help accelerate discussions (with naysayers) on data structures. Can you please identify the source? And perhaps the vector image of this illustration will be helpful - to make changes / additions. – abRao Dec 20 '10 at 19:37
@Abhi: I don't know the original source. I'd just seen this before and googled for "STL Flow Chart". This particular link is from http://www.jamesonwilliams.com/stl-container-choice , but I highly doubt that's the original author. I'm unaware of any SVG version unfortunately. – Billy ONeal Dec 20 '10 at 19:40
Thanks to all of you ....actually now I understand it's all about practice and experience. Actually I was trying to know the solution before arising the problem which is quite impossible. Anyway thanks again now I'll have to work a lot on it. – Atul Dec 25 '10 at 13:30
The image doesn't load anymore – Will Sheppard Jan 21 '16 at 13:42
1

@Will: Looks like it's gone. Fixed up to link to another question I found with good substitutes. – Billy ONeal Jan 21 '16 at 21:03

score 2 · Answer 2 · answered Dec 20 '10 at 19:14

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.

score 1 · Answer 3 · answered Oct 03 '14 at 06:24

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

do i need to be able to find a specific element (give me the person called "bob") ?
do i care about the order (ie, regularly find the first or last)?
do i need to be able efficiently delete records other than the last?
do i need random access (give me the 20th) ?
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)

score 0 · Answer 4 · answered Feb 06 '14 at 15:11

0

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.

answered Feb 06 '14 at 15:11

user3280137

1

score 0 · Answer 5 · answered Dec 20 '10 at 19:14

0

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?

answered Dec 20 '10 at 19:14

Jonathan Wood

65,341
71
269
466

Well, something like a binary tree is rarely the smallest and simplest way to store something, but it's often the most performant way to do so. – Billy ONeal Dec 20 '10 at 19:16
Well, I was thinking more about the data structure itself more than the algorithm. But that's definitely part of the problem when the question asked is not entirely clear. – Jonathan Wood Dec 20 '10 at 19:24

score 0 · Answer 6 · answered Dec 20 '10 at 19:17

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.

Thanks to all of you ....actually now I understand it's all about practice and experience. Actually I was trying to know the solution before arising the problem which is quite impossible. Anyway thanks again now I'll have to work a lot on it. — Atul, Dec 25 '10 at 13:30

Choosing a data structure

6 Answers6

Linked