[softfalcon]

You're not wrong, data structures and an algorithm for data retrieval are often connected and developed together. You often see someone come up with a novel way of traversing data, then they model an elegant data structure to match it and enable said traversal.

What isn't covered in this flow is how composition of multiple data-structure/algorithm pairings work together amidst many others. It's often not an algorithm on its own that defines an overall solution. It's the connecting of many of them together, to build a whole software stack, domain language, etc.

When you understand the algorithms, the corresponding data structures, when to use them, similarities in various frameworks in your chosen domain, how that analogues to your current problem set, etc you really start getting somewhere.

[eska]

* data structures and an algorithm for data retrieval are often connected and developed together*

Often? Always! An algorithm always only works on a certain data data structure.

[nonrandomstring]

Or as Fred Brooks put it:

   " Show me your tables, and I won't usually need your flowcharts;
   they'll be obvious."

But to be fair, you need to be a pretty damn good comp sci person (and actively thinking in algs and DS) to quickly look at DS and see the "obvious" processing implied.

[sfn42]

A problem I see a lot is when the flowcharts should be obvious, but aren't because whoever wrote the code didn't write the obvious solution.

Instead they wrote a horrible buggy mess that tries (and usually fails at least a little) to do the same thing as the obvious solution but with much more, and more convoluted, code.

[softfalcon]

I appreciate your particularness in this regard, and you'll have to forgive me as I've spent a lot of time with folks who are very wary of the word "data structures".

I tend to use softer words like "often" as it makes folks feel less defensive towards the discussion. If someone came up to you and told you that your outlook on something is 100% definitively wrong, you might balk at the statement merely because I said "100%". Just as you have stated "Always!" and corrected me so emphatically.

Since I've found this to be a difficult topic for some, and given this is a public forum, I chose to be cautious in my wording.

[a1369209993]

Also they're just straightforwardly wrong. For example, binary search works on a array, or on a predicate like \x->(x*x <= 2.0), or on a hash table with contiguous integer indexes, or even on a linked list. Of course it works very badly on a linked list (worse than linear scanning unless the comparison is ruinously expensive), but they didn't say "An algorithm always only works properly on a certain data data structure.".

[eska]

A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t have random access for example. So binary search on a linked list is actually not possible.

[a1369209993]

> linked lists don't have random access

`list.get_nth(n)` has O(N) runtime, as does `list.length()`, so binary search is actually completely possible, with runtime O(N^2) (aka "works very badly").

(Fair point that all four data structures need to be sorted, though, although ideally that would go without saying, since it's kind of inherent in what binary search is.)

[eska]

Having random access means that it‘s O(1).