Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
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:
No size limits. No matter how much you think you know at first, you'll always hit a size limit.
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.
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.
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.
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.
Listin C#,ArrayListin 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).