What is the relationship between data structures and algorithms? [closed]

Question

I have been searching for a good online course in data structures but have found that Google also returns results for algorithms courses, which say stuff like:

In this course you will learn several fundamental principles of algorithm design: divide-and-conquer methods, graph algorithms, practical data structures (heaps, hash tables, search trees), randomized algorithms, and more. [source]

and

By the end of this class you will understand key concepts needed to devise new algorithms for graphs and other important data structures and to evaluate the efficiency of these algorithms. [source]

and

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. [source]

My question is: are algorithms and data structures intimately linked, meaning that they must be understood together or is one topic more foundational than the other?

EDIT: For those voting to close this question, can you please tell me why and maybe how to improve this one? Learning to ask the right questions is part of the educational process.

Answer 1

All sorts of mixtures do exist. You have data structures, which are not associated with algorithms, algorithms, which require no (real) data structures, but most often the two come in one package.

Edit: as @Doval correctly pointed out, data structures per se do not have any operations associated with them. The act of combining data structure and algorithm forms an abstract data type.

Data structures without algorithms

Consider for example a data structure for storing 2-dimensional coordinates, appropriately called Point. There is nothing much in terms of algorithms to be done for a point and it really is just a container for an x and y value. Of course, giving this data structure, you can now add all sorts of algorithms on top of it (distance calculation, convex hulls, what-have-you).

You can think of a lot of data structures, which are simply an accumulation of individual data. While these do occur frequently in practice, they do not make for good teaching material, because there is nothing to be learned from it, once you have understood, that single data items can be accumulated into a new data structure (like what do you learn after the above Point example, if I provide you with that awesome data structure called Point3D, which can do the same thing for 3-dimensional space?)

Algorithms without (real) data structures

"Real", because obviously every interesting algorithm needs primitive data types like integers or booleans, and we do not want to consider those as data structures in this context. Similarly to above, these algorithms are typically rather simple ones. In particular, they do not come with a complicated state of any sort, because that usually goes into a data structure (see next section).

An example for such an algorithm would be calculating the greatest common divisor of two numbers. Euklid's algorithms for the gcd really only needs to hold two integers and manipulates them.

Once things start to get more interesting, you very soon enter the world of abstract data types though. For example, the sieve of Eratosthenes is based on an array. We could have a discussion now, whether an array is still primitive, or in fact, you could discuss if an integer isn't already a data structure. Either way, algorithms that exist completely without data structures are rather boring, even if you accept their isolated existence.

Algorithms combined with data structures, aka abstract data types

Now these are the interesting ones, but for two very different reasons. Typically, you can approach these from two directions: data structure first, or algorithm first.

While an abstract data type is defined by the combination of data structure + algorithms/operations, we often view them with a focus on either one of those and consider the other one as enablers.

Data structure, then algorithm

You will encounter abstract data types, which are rather simple to use, but involve more or less complicated algorithms to make them work internally. For example, a HashMap is trivial to use, but involves a nifty hash function and dealing with the hash collisions on the inside. Yet, from your point of view as a user you care about it as something that holds data for you, not something that does something for you.

In contrast to the last group below, these data structures do not expose their users to these algorithms. You do not need to know, nor care, about a HashMaps internal hash function in order to be able to use it. (To use it effectively though, you may want to know these things ;)

Algorithm, then data structure

The other direction means you have an algorithm, which you want to be able to simply use, but which needs data structures internally to make it work as intended. An example would be a binary space partitioning (BSP) algorithm, that you can simply ask for the 2-dimensional Point from a large set of points that is closest to a given query point. However, you need a tree structure (and even additional algorithms like distance calculations) on the inside to actually write the algorithm.

In general, one can say that algorithms in this group use involved data structures for their internal state representation. I would argue, that this group of algorithms is the most diverse and you will find many many different ones that fit this general scheme. Regarding the point of view, we see these as interesting, because they do something (f.ex. sorting) for us, and do not care as much about the data holding part.

Closely related data structures and algorithms

Finally, you have data structures, which are very close related to algorithms that directly correspond with them. A typical example is a binary tree, which, when you want to do anything meaningful with it, forces the topic of tree-walking algorithms on you (depth-first, breadth-first, whatever).

For these cases, we change the focus of our view of the resulting abstract data types every so often. Sometimes you care about the structure of your tree, a few minutes later you care about being able to run a find operation on it, then you wonder about deleting a node, and right-away about how the structure looks afterwards. While all of this holds true for the other sections above as well, it is not something that is the primary focus in your mind, for example, when you store/retrieve data to/from a Map, or when you sort a linked list.

Answer 2

Data structures often influence the details of an algorithm. Because of this the two often go hand in hand.

Consider for example an algorithm for cutting your lawn. How you go about cutting your lawn is likely to be influenced by the actual structure of your lawn. If you live in a small house in a densely packed suburb and your lawn is just a small rectangle a few meters squared in area, you would probably prefer to cut your lawn with a push-mower instead of a tractor/riding mower. If your lawn involves many acres of flat meadow land, your preference may be for the riding mower as opposed to the push-mower (though either mower may eventually get the job done). If your lawn involves acres of land with large flat areas, but a few small hills and a number of trees, you may develop a more interesting algorithm for cutting the lawn that involves both a riding mower and a push-mower, or some other grass cutting techniques.

Ultimately though, the structure of your data may have a significant impact on your decisions for how to develop your algorithm (or which algorithms to use). For this reason, the two topics often go hand in hand.

And vice versa: sometimes the algorithm we want to use influences (at least at the onset of computing) the data structures you develop to support the algorithm. For example going from an array list to the idea of a linked list and eventually to a BST for storing an ordered list that will allow for quick find.