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.

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.

share|improve this question

closed as primarily opinion-based by ratchet freak, user61852, gnat, MichaelT, david.pfx May 15 at 5:37

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

14  
A data structure is static, and can do nothing. An algorithm is just a set of instructions to perform on some data. Without one, the other is useless. Together, they make computer programs. They're both fundamental. –  Phoshi May 14 at 12:30
2  
@Phoshi Wrong. Data structure are closely tied to algorithms that manipulate the data. So closely tied those algorithms are considered part of the data structure. For example Lined List data structure tells you how the data is saved and also how the data is read and manipulated. –  Euphoric May 14 at 12:32
5  
@Euphoric I'd argue it's wrong to say that algorithms are part of the data structure. There's more than one way to implement a binary search: you can, for example, do the naive if less than recurse to the left; if greater than, recurse to the right; if equal, return search or the slightly more sophisticated if less than recurse to the left; otherwise keep track of this value as a potential candidate and recurse to the right; check for equality once we reach the leaves. They have slightly different numbers of comparisons. Both are one of the many things you could choose to do with a tree. –  Doval May 14 at 12:41
4  
@Euphoric You're confusing the data structure with the abstract data type that the combination of data structure and algorithms implement. –  Doval May 14 at 12:47
6  
@Euphoric, I have to disagree. merge sort is an algorithm. An array is a data structure. A linked list is a different data structure. I can write an implementation of MergeSort to operate on either. Some data structures may be more natural or more efficient for a particular algorithm, but it is rarely an absolute requirement (you do pretty much have to have a heap to implement heap sort). Nicholas Wirth wrote a popular text book in the 1980s titled: "Algorithms + Data Structures = Programs" –  Charles E. Grant May 14 at 15:28

2 Answers 2

up vote 17 down vote accepted

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.

share|improve this answer
    
You're conflating data structures and abstract data types. A data structure doesn't do anything. It makes no sense to say "you will encounter data structures, which are rather simple to use" because a data structure is just a structure. A Map is an abstract data type that may be implemented using a particular data structure and a set of algorithms that produce the desired results by traversing and manipulating the structure. The data structure doesn't hide the algorithms, because it has none; the abstract data type hides the data structure (that's what makes it abstract.) –  Doval May 14 at 12:54
    
Note that in a sense algorithms are always hidden because there's no way to inspect functions. That's probably why they're called abstractions in lambda calculus (whose only data type is functions). –  Doval May 14 at 12:59
1  
You are correct. Nevertheless, I see a distinction between how we view the different ADTs. I have edited my answer and hope it is clearer now and no longer conflates the structure with ADTs, while still emphasizing, that you can focus on structure and/or operations for any ADT. –  Frank May 14 at 13:35
    
Is it really too simple to say that data structures are nouns and algorithms are verbs? I suppose you might say that the algorithm is the implementation of the verb, but you still search a tree, even if that search is a binary search. You'd miss out on all the technical detail by saying so, but it does have a certain elegance. –  Magus May 14 at 23:02
    
@Doval: Even if a data structure which simply consists of a bunch of numbers in an array which are required to have and maintain some relationship to each other, such a thing may be "easy to use" if it's easy to maintain the required invariants while doing what one wants, or "hard to use" if it is difficult. –  supercat May 14 at 23:39

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.

share|improve this answer

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