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 HashMap
s 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.
if less than recurse to the left; if greater than, recurse to the right; if equal, return
search or the slightly more sophisticatedif 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 '14 at 12:41