Structures and Algorithms Together

We set out to build one data structure, the dynamic array. Along the way we wrote add, grow, get, set, contains, indexOf, remove, selectionSort, swap, and indexOfMin.

Every one of those is an algorithm.

Data structures and algorithms are closely related, and the connection runs in both directions.

Data structures are built from algorithms

A data structure is more than a way to lay out data. Each operation it offers is a procedure that has to be designed and made correct. That is an algorithm.

We saw several of them in this chapter, and they take different amounts of work to design. get is a single array access, so there is not much to it. remove has to find an element and then shift every later element one slot left to close the gap. add is usually a single write, but when the backing array is full, grow allocates a larger array and copies the elements across. The client calling add cannot tell whether it got the single write or the copy.

So building a data structure involves designing algorithms.

Algorithms are built on data structures

The connection runs the other way too. An algorithm operates on data, and that data has to be organized somehow. We saw this with selectionSort. It operates on DynamicArray through its public interface: size, get, and set. Give it a different structure with the same operations and it will sort it. Many algorithms are designed around the operations a particular data structure provides, and those operations determine what the algorithm can do and how efficiently it can do it.

So designing algorithms involves building and using data structures.

Data structures and algorithms

This is why the two are usually taught together. The acronym DSA stands for Data Structures and Algorithms, and it is often used to name a course or a book that covers both. Our course is called “Data Structures”, but we will treat it as a DSA course.