In an earlier post we saw the importance of choosing the right data types when designing an algorithm. But we don’t just choose a type — whether we’re aware of it or not, we are also choosing a data structure which implements that type.
Both choices can have a big impact on how efficient an algorithm is; let’s consider some examples.
A polygon is any shape made of straight-line segments. Polygons are especially important in computer graphics and games, since they’re used in vector image formats and 3D models.
The most primitive geometric objects are points and vectors. But real geometric problems involve shapes like rectangles, triangles, circles, and polygons — or more complex collections of shapes, such as 3D models made of many polygons. In this post we’ll consider how computers can represent some simple kinds of shapes, and solve problems using these representations.
Many computing applications deal with geometric or spatial data. Here are some of the more obvious examples:
Before attempting these exercises, you should read the posts about graphs, graph problems, and graph data structures.
A graph is an abstract model of a relation between pairs of things. In the previous post we identified many relations which can be modelled as graphs; however, we don’t yet have any data structures to represent graphs in computer programs.
Before attempting these exercises, you should read the posts about trees, ways to think about trees, and tree data structures.
Abstract data types define what data can be represented and what operations can be performed on it, but not how the data should be stored or structured in a program. Data structures are concrete implementations of ADTs which fill in these details — they define how the data should be stored in memory, and what instructions should be followed to perform the operations.
Trees are both; we have an abstract idea of what a tree is, but there are also data structures for them, which we’ll look at in this post. In fact, we can even use tree data structures to implement other ADTs, such as sets or dictionaries.(1)
Before attempting these exercises, you should read the posts about array-lists and linked lists.
When designing a data structure, there are always choices to make. In the previous post we described the array-list data structure implementing the list data type; in that post, we made the choice to store the list values in an “underlying array” so the list values would all be together in memory. In this post we’ll show that this really was a choice, by developing a list data structure which stores the list values in separate objects, rather than a single array object.
In earlier posts we described lists and arrays. We described lists as an abstract data type, meaning we said what a list is and what we should be able to do with one. However, we didn’t say how a list is implemented — we didn’t describe a data structure for a list — so we don’t yet have a scheme for representing lists in memory.(1) On the other hand, when we described arrays, we did also describe how to represent them in memory.
Computers read data from memory by its address — and memory addresses are numbers — so arrays are a natural data structure for sequence types which support ‘getting’ values by their numeric index. When we ‘get’ from an array, the computer can use the index to calculate the memory address of the value we want.
To implement a dictionary, we need a way to ‘get’ values by their keys.
An array is an efficient data structure because its indices are a compact range of numbers; but the keys in a dictionary generally aren’t numbers, so it’s not obvious how a key like "foo" can be used to find where in memory the value associated with it is.
If we can’t directly calculate where the value is, we’d have to search for it, and this could be quite slow if there is a lot of data to search through.
Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.