Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

It seems to me that, for everyday use, more primitive data structures like arrays get the job done just as well as a binary tree would. My question is how common is to use these structures when writing code for projects at work or projects that you pursue in your free time?

I understand the better insertion time/deletion time/sorting time for certain structures but would that really matter that much if you were working with a relatively small amount of data?

share|improve this question

closed as not constructive by maple_shaft Apr 5 '12 at 12:23

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

5  
Associative data structures, such as hash tables or binary trees, are extremely commonly; perhaps even more common than arrays. –  Charles Salvia Apr 5 '12 at 2:56
1  
might be better if people reply with the respective languages they are using –  prusswan Apr 5 '12 at 3:17
1  
I assume you also mean ignoring each language's array-like types (List in C#, ArrayList in Java, [] in Python, etc.). I do use associative structures (maps, dictionaries) extremely frequently, as I work a lot in Python, but also in C# and C++. Many of those structures are implemented with trees behind the covers. Sets are pretty common for me too. There are tasks that more naturally fit data types (like finding the difference between two data sets). –  birryree Apr 5 '12 at 4:00
    
I guess to the beginner, arrays are the least intimidating. Now I am starting to see how inflexible they are compared to other data structures –  ironcyclone Apr 5 '12 at 10:44
1  
@Chris2021 This question does not meet the acceptable criteria for a constructive question per the FAQ. Asking what peoples experiences are doesn't fit well in the Q&A format. You can consider editing the question to instead ask why it is not so common in the workplace instead and we can consider it for reopening. –  maple_shaft Apr 5 '12 at 12:26
add comment

7 Answers 7

I use trees/maps and lists literally every day. Actually I rarely use arrays at all, for their inflexibility: arrays are harder to work with!

Which specific implementation of a list (ArrayList, LinkedList,..) or map (HashMap, TreeMap,..) I use depends solely on the task on hand, and takes some common sense and educated guessing.

share|improve this answer
add comment

Each language has its own set of 'built in' data structures that developers make use of more than others. In C its arrays, but in C#, Python and Ruby its probably Lists and Dictionaries. It depends on what you get 'for free' with a language and its base library.

I'm developing mainly in C# and use the generic (strongly typed) List all the time along with the generic Dictionary. It frees you from having to worry about the data structure implementation and you can just concentrate on your algorithm. In C I think you'd spend a lot more time implementing these types of things and so you may be happy sticking to lower level structures like arrays.

But implementing your own custom data structures does have a role too - I recently needed to setup a QuadTree type in C# for partitioning 2D space - that was the best solution for what was needed.

share|improve this answer
add comment

Effective C++ says that std::vector (a resizeable array) should be the default choice for a container. Bjarne Stroustrup presented an "invisible graph" [vanished from the slides] on the Going Native conference where he compared theoretically better data structure (linked list) with a vector. Vector won for his tested size range as cache misses caused by following list elements killed performance totally.

At work we develop various data-transformation algorithms where performance is important, and ~75% of all data structures are vectors. Next in line come sorted vectors, which are efficiently searchable with binary search (std::lower_bound and std::upper_bound). Next come hashes and trees (when the algorithm needs efficient online insert/update/delete [i.e., when a sorted vector can't be constructed from scratch]), after them comes std::dequeue (a combination of list and sequential allocation) meagerly used less than a dozen times. Singly/doubly linked list? < 5 (I'd even dare say zero) occurrences in a large C++ project.

share|improve this answer
add comment

Very honestly, I have to disagree. I spend a lot of my free time writing C. I've done a number of interpreters lately. Although I do use arrays in some circumstances, I almost always use linked lists, binary trees, hash tables or other structures.

I have two reasons:

  1. No size limits. No matter how much you think you know at first, you'll always hit a size limit.

  2. More natural algorithms fall out of things like linked lists and binary trees. You can recurse on them, or you can iterate, but they just work better.

share|improve this answer
    
A valid point. I'm not an experienced programmer by any means but wouldn't the size of either an array or a linked list be limited only by the memory? –  ironcyclone Apr 5 '12 at 2:14
    
@Chris2021 The amount of memory is a factor, but the way a linked list works is far more flexible. You can have each "index" at random locations in memory, but an array is one index after the other. Arrays are limited by the amount of consecutive memory available. Of course you have to assign how many indices you want, which means when you hit that limit, you have to create a new array and copy the old one over, which is a PITA (not to mention pretty inefficient.) –  Glenn Nelson Apr 5 '12 at 2:59
    
Modern CPUs love sequential accesses. Anything else, unless you're careful about placing data in memory, kills performance. –  zvrba Apr 5 '12 at 5:44
add comment

So many useful data structures are in convenient-to-use libraries these days that I use the best data structure for the job regardless, which very often is trees, linked lists, tries, or whatever. Of course, this is expected at work. But why would I want to make my life harder just because it's a hobby project? I don't do hobby programming so that I can have fun typing out a[x+1] = a[x] + a[x-1] a bunch of times; I do it to solve problems. Appropriate use of data structures is a big part of how to make this happen.

If you're asking how often do I write a custom data structure...well..not very often in any context, since so many powerful ones are available in libraries. But the rule is the same: if a novel data structure is "best" (taking into account how long it will take me to write and debug the code for it), then I use it.

share|improve this answer
add comment

If I'm using Python, I use mainly: dictionaries (no surprise), lists, tuples. I admit that I regard lists as arrays so long as they can be indexed as one.

share|improve this answer
add comment

I used to work with both C++ and C#. I use Lists, Maps, Vectors almost everyday. Most of the people are not really bothered about taking it in a perspective of data structure but just as a way to meet their target.

I use arrays very rarely, mostly when working with Windows APIs etc. where we need to give fixed length array. But on the other hand, I am not used to replace arrays with the dynamically growing data structures like vector. I feel it's tricky and on top of complexity it spoils the readability.

It also depends what kind of platform you're working on. When I have worked in embedded Linux project, I was mostly stuck with fixed size arrays where none of these C++ data structures or implementations can be used.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.