Trees in computing are an abstract idea with many diverse applications. Visual representations are especially important here, because a lot of ideas about trees are easiest to convey visually. Having more ways to think about trees also makes us more likely to recognise where they’re applicable.
There are two kinds of ‘tree’ that everyone knows about: actual trees made of wood, and family trees. Family trees are closer to how we think about trees in computing; a family tree is an abstract diagram of the parent/child relationships within a family. There are many kinds of hierarchical relationships which need to be modelled in computer programs.
Before attempting these exercises, you should read the posts about array-lists and linked lists.
Before attempting these exercises, you should view the box-and-pointer diagrams video lecture.
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.
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.
This video lecture explains box-and-pointer diagrams, which are a visual model for objects, variables and references. Box-and-pointer diagrams are also important for understanding and explaining data structures. We’ll develop the ideas behind box-and-pointer diagrams by thinking about how programs use memory.
Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.
Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.