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