Apr 302018One of the most important and overlooked parts of designing algorithms is choosing the right data types.
We often assume that the types of data an algorithm will use are determined by the inputs and the output — but it might help to use a temporary collection of some data, if that collection has useful operations.
Those operations are determined by the collection’s type.
In this post we’ll look at a couple of examples where using the right data types makes the problem simpler.
Feb 192018When 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.
Feb 192018In 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.
Feb 192018Computers 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.
Feb 122018Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.
Feb 122018Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.
Feb 122018A list can do everything an array can do, and more; the array data type is strictly “less useful” than the list data type.
However, the array data structure is both faster and uses less memory than any list data structure.(1)
This is common: if a data type supports fewer operations, then programmers who use that type have less freedom, but programmers who implement it (or choose an implementation) have more freedom.
A data structure supporting fewer operations can often be more efficient in speed, memory use, or both; or, if you want more operations supported, expect a lower efficiency.
Feb 122018We have the idea of an abstract data type (ADT) — a data type which is defined by its set of possible values and set of supported operations, but which does not specify how those values should be represented in memory, nor how the operations should be implemented.
We also have a memory model for thinking about data structures, which fill in these details.(1)
Feb 122018A type defines not just the possible values that some data can take, but also the operations which can be performed on that data.
For example, the int type represents integers, and supports arithmetic operations, bitwise operations and comparison operations.
