Algorithms and data structures

Introduction

We have reached a state of piercing theoretical insight. In this chapter, we will apply our newfound analytical skills to commonly used algorithm and data structures. We’ll also briefly cover some abstract data types that will pop up in other chapters.

My approach here is going to be a bit different to what you’ll see in most textbooks on algorithms and data structures. They put a lot of emphasis on showing how to implement a wide variety of data structures and algorithms, usually in C. I don’t think that’s a particularly useful way for a self-taught person to start off. Learning how to implement a new data structure or algorithm in isolation is a sure way to immediately forget it. You need the reinforcement of regularly applying what you’ve learned to solve problems that you encounter daily. Computer science students have the luxury of being set problems and projects that test this new knowledge.

As a web developer, you’ll probably spend the majority of your time using the built-in data structures and algorithms provided by your language’s standard library or the browser environment. We’ll therefore focus on the data structures and core algorithms that are included in the languages and browsers you’re likely using every day. You’ll learn how they’re implemented and what their performance characteristics are.

I won’t spend any time on the fancy stuff behind the algorithmic brainteasers that some companies like to use for interviews. There are already many excellent interview preparation resources and there is no need for me to reinvent the wheel. As ever, the further reading section will have plenty of suggestions if you want to continue study.

Data structures

Look at any computer program and you’ll see two things: data and operations on that data. From the computer’s perspective, everything is just a huge sequence of ones and zeroes (i.e. bits, see the computer architecture chapter for more information). It is the programmer who creates meaning by telling the computer how to interpret these ones and zeroes.

Data types are a way of categorising the different forms of data a computer can utilise. A data type determines the (possibly infinite) set of possible values, the operations that can be performed on a value and maybe how a value can be physically implemented as a sequence of bits. Usually a programming language contains a few built-in, primitive types and allows you to make new types that build on the primitives. Common primitive types include integers, booleans, characters, floating point (i.e. decimal) numbers and strings.

Some data types are bound to a particular implementation. These are known as concrete data types. For example, the range of numbers that can be held by an int type depends on how many bits the underlying system uses to represent the number. A 64-bit int holds bigger numbers than a 32-bit int. Primitive types are nearly always concrete.

When a data type doesn’t specify an implementation, it is called an abstract data type (ADT). ADTs are merely descriptions of the set of possible values and the permitted operations on those values. Without an implementation you can’t create a value of the type. All you’ve done is specify how you’d like the value to behave and the computer doesn’t know how to create a value that behaves that way. I can want the moon on a stick but without a way of getting the moon on to a stick I’m not going to have it.

To actually use an ADT you need to create a data structure that implements the interface. A data structure defines a way of organising data that allows some operations to be performed efficiently. Data structures implement data types. Whether a particular data structure is a good implementation for a data type depends on whether the data structure efficiently implements the operations specified by the data type. The operations a data structure provides can be thought of as algorithms bound to the data held in the structure. We can therefore use the techniques we’ve seen above to measure the performance of a data structure’s operations and determine which tasks it is best suited to.

There exists a veritable zoo of data structures out there. In this section we’ll stick to the most fundamental ones: arrays, linked lists and hash maps. They’re incredibly useful and built-in to most programming languages.

Arrays

An array is the simplest possible data structure. It is a contiguous block of memory. That’s it. The array holds a sequence of identically sized elements. They have to be the same size so that the computer can know where the bits making up one element end and the bits making up another element begin. An array is therefore associated with the particular data type that it contains. The length, or size, of an array is determined by the size of the memory block divided by the element size. It indicates how many elements can fit into the array.

You can iterate through an array, by examining each element in sequence, or you can index, by jumping directly to any position in the array. We’re able to do this because the structure of the array allows us to work out the location of any element, provided we know the address of where the array starts and the element’s position within the array. Imagine that we have encoded the characters of the Latin alphabet into binary numbers that are two bytes long (a byte is eight bits). A array of size ten therefore requires a memory block twenty bytes long. We can immediately index any element in the array by calculating its memory address. We take the array’s base address (the address of the first element) and calculate an offset by multiplying the element size by the element’s index. If we assume our array of ten characters starts at memory address 1000, the addresses of the first four characters are as follows:

1 array[0] = 1000 + (0 * 2) = 1000
2 array[1] = 1000 + (1 * 2) = 1002
3 array[2] = 1000 + (2 * 2) = 1004
4 array[3] = 1000 + (3 * 2) = 1006

The strength of the array is its speed. Indexing an element in an array is a constant time operation. No matter how far away the indexed element is, we can always jump directly to it via a single calculation.

The simplicity of the array is also its main limitation. There is nothing in the structure of an array that marks the end of the array and so there is no way for the computer to know when it’s reached the end. In C a variable holding an array actually just holds the array’s base address. This means that the size of the array has to be stored in a separate variable and passed around with the array. The programmer is responsible for correctly updating the size variable when necessary. If you mistakenly tell the computer an incorrect size value, it will blithely iterate past the final element, possibly overwriting any values stored in those locations. This is known as a buffer overflow and is a major source of often very serious bugs. A second limitation of C-style arrays is that increasing the size of the array requires increasing the size of the allocated memory block. It’s often not possible to simply increase the size of the existing one because the adjacent memory addresses might already be in use. We frequently have to find a new, unused block of sufficient size and copy over all of the existing elements. Handling this manually is a bit of a pain.

More modern programming languages provide a slightly different data structure known as the dynamic array. They are so called because they have no fixed size, in contrast to static, C-style arrays. A dynamic array holds a raw array in a data structure that also keeps track of the number of elements in the array and its total capacity, thus preventing invalid indexing operations and removing the need to store the size in a separate variable. Dynamic arrays can resize automatically when they get filled up. If you don’t have to worry about the size of an array – as in Ruby, Python or JavaScript – you are actually using a dynamic array.

In many languages it’s hard to find out how a dynamic array actually works under the hood. In JavaScript, for example, there’s no simple way to get the current address of an array or any of its elements. This is by design: the whole point of dynamic arrays is to take this responsibility away from the programmer. Instead, let’s turn to Go. It offers an interesting intermediate point between the static arrays in C and the dynamic arrays in Ruby, Python and JavaScript. Go has C-style static arrays but builds on top of them another data structure, known as the slice, that works like a dynamic array. Go doesn’t hide any details of the underlying array. A slice is defined in the Go source code (runtime/slice.go) as a wrapper around an array:

1 type slice struct {
2         array unsafe.Pointer
3         len   int
4         cap   int
5 }

A pointer is a value that is the address of another value. It points to the value’s real location. A pointer can be dereferenced by accessing the value stored at the address held by the pointer. The slice doesn’t actually contain the array; it just holds the address where the array is. As well as the address of its underlying array, a slice tracks the len, the number of elements in the array, and the cap, the total capacity of the array. Let’s see them in action:

 1 package main
 2 
 3 import "fmt"
 4 
 5 func main() {
 6         slice := []byte{1, 2, 3}
 7         array := [3]byte{47}
 8 
 9         fmt.Printf("Slice %#v has length: %d and capacity: %d\n",
10                    slice, len(slice), cap(slice))
11         fmt.Printf("Slice element addresses: [%#p, %#p, %#p]\n\n",
12                    &slice[0], &slice[1], &slice[2])
13 
14         fmt.Printf("Array %#v has length: %d\n", array, len(array))
15         fmt.Printf("Array address: %#p\n\n", &array)
16 
17         fmt.Println("Appending another element...\n")
18         slice = append(slice, 4)
19 
20         fmt.Printf("Slice %#v has length: %d and capacity: %d\n",
21                    slice, len(slice), cap(slice))
22         fmt.Printf("Slice element addresses: [%#p, %#p, %#p, %#p]\n",
23                    &slice[0], &slice[1], &slice[2], &slice[3])
24 }

This program defines a slice and initialises it with three values. Immediately afterwards, we define a static array of size 3 but with only one initial value. Here is the output:

1 Slice []byte{0x1, 0x2, 0x3} has length: 3 and capacity: 3
2 Slice element addresses: [c000086000, c000086001, c000086002]
3 
4 Array [3]byte{0x2f, 0x0, 0x0} has length: 3
5 Array address: c000086003

The addresses are written in hexadecimal. Even though array only contains one actual value, space for two more has already been allocated. Notice that the elements held by slice are all adjacent to each other in memory and the address of array comes directly after. That means there is no empty space between the two variables. What do we expect to happen when we append another element to the slice? We know that the slice is a wrapper around a static array with a capacity of three. There won’t be room for a fourth element. We can’t just expand the underlying array because the memory address it would use is already occupied by array. We therefore expect that Go will have to find a new, bigger memory block for slice and move all the existing elements. Sure enough: