Data Structures & Algorithms I

Most college-level computer science programs include some version of a data structures and algorithms course in the first or second year. The two concepts get lumped together due to their close conceptual link and how fundamental they both are to writing non-trivial programs. In 1976, Niklaus Wirth, the designer of the Pascal programming language, published the famous text Algorithms + Data Structures = Programs, which captured the relationship so well that the concept has become almost cliche.

Data structures are concrete implementations that define both how data is organized and how it can be operated on. Algorithms are procedures or instructions that define operations. Data structures provide application programming interfaces (APIs) that expose operations, each of which may employ one or more algorithms internally. The operations defined in a data structure’s interface can, in turn, be composed to build higher-level algorithms. For example, imagine a grocery list. At the very least, a simple list data structure requires an operation to insert an entry into the list, which is provided by its interface. The same interface might also contain operations for manipulating the data in the list which can be used to design even higher-level algorithms for processing a collection of elements in the list. It’s not hard to see how intricately linked these concepts are, and to get a complete operational or practical picture of one you must understand the other. That being said, there are many ways to accomplish similar tasks, and it’s not practical nor necessary to master every possible data structure or algorithm. Instead, it can be helpful to view them as tools in an ever-growing toolbox that you will curate according to the needs of your programming domain. This module covers a limited set of classical data structures which help illustrate foundational concepts that can be used to develop even more specialized tools.

Neither data structures nor algorithms are beholden to a single language or implementation. Instead they’re best understood by what kinds of problems each data structure or algorithm is intended to address. You can solve programming problems in any number of ways, and many designs include necessary tradeoffs. For example, there are several differet, equally as appropriate ways to realize a sorted list, each with benefits and drawbacks. The best programs combine the most appropriate data structures with the most efficient algorithms to produce results that best address the program design criteria.

Most programming languages provide implementations for many common ADTs within their standard libraries. Whatever language you choose to learn this material in, it’s valuable to review your chosen language’s default implementations. This review can help you make informed decisions about which data structure to use based on your specific use case and design criteria.

Reference Documentation

One of the best ways to understand a topic is by hands-on learning. This project includes a companion library of concrete implementations to illustrate the concepts covered in this module. You can also visit the project repo for more direct code examples, including experiments that were culled from the library.

Abstract Data Types

The concept of an abstract data type (ADT) is to provide a way to organize or classify data structures based on their behaviors or problems they’re intended to solve rather than their specific implementations or designs. ADTs define a theoretical group of operations that collectively describe the behavior of a data structure in an abstract or general way. These operations provide something like a blueprint for how the data structure should behave.

An ADT may include any number of variants or sub-types that differ depending on their intended use or design criteria. For example, the map ADT has a sorted sub-type which adds the ability to operate on ranges of map entries that might not be useful in an unsorted map structure. The sorted sub-type is still a map, but the map ADT is not necessarily sorted. Each of the map variants contain the same basic set of operations, but each sub-type may contain additional operations specific to that sub-type.

ADTs do not dictate implementation details. That is to say that you can achieve the same set of collective behaviors that make up an ADT in any number of concrete ways. Indeed, implementations can vary significantly across programming languages due to differences in language design, yet they are considered representations of the same ADT if they support the same set of general operations. This language-agnostic property allows ADTs to be universally understood and applied, regardless of language specifics or implementation details.

Because of the flexibility in classifying or defining ADTs, the boundaries between different data structures can sometimes be vague, leading to a vast number of possible variations and potentially even overlap. Still, it is generally more useful to group concepts into broader, high-level categorizations rather than endlessly splicing categories based on nuanced and often pedantic differences. This approach helps in understanding the fundamental concepts behind data structures without getting bogged down by the specifics of every possible variation.

The good news is that you don’t need to know every single data structure implementation to be a successful programmer. One of the key themes in studying data structures is understanding enough about abstract data types (ADTs) to recognize their differences and relationships, enabling you to make informed decisions when constructing your programs.

Content Organization

Unfortunately, there is no single way to classify or organize data structures. As a result you might encounter wildly different approaches across equally as valid texts. As an introductory text, this project attempts to provide a loosely linear pedagogical sequence of topics by ADT family. Each covered ADT also includes a basic analysis to provide reference in choosing the most appropriate tools for your more advanced implementations.

The following tables group common ADTs and their data structure implementations into broader data model categories. These include sequential, hierarchical, associative, and graph-based families of ADTs and their concrete realizations. Each table summarizes key properties, such as whether the structure is sorted, common in-memory structuring, and whether standard library implementations exist for each listed language. Not all ADTs have standard or concrete implementations, so I hope you’re ready to get crafty.

To save space and visual noise the tables in this section use a symbol-based short-hand to convey properties.

Symbol	Description
S	Sorted
U	Unsorted
I	Indexed (typically within contiguous memory arenas)
L	Linked (traditional pointer-based structures)
/	Either/or, listed in order of commonality or preference
+	Composite structures that use more than one type of memory structure

Sequential Structures

The sequential structures in this table are all unsorted by default. The stack and queue variants use a specific kind of ordering by default. Though not exactly a sorting scheme, the The First In First Out (FIFO) and Last In First Out (LIFO) orderings provide the primary behavioral characteristics of each structure type in this group.

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
List	Static array	U	I	T[]	[n]T	[T; N]
List	Dynamic array	U	I	ArrayList<E>	[]T	Vec<T>
List	Linked list	U	L	LinkedList<E>	container/list	LinkedList<T>
Stack	Any list	LIFO	I/L	Deque<E>	[]T	Vec<T> / LinkedList<T>
Queue	Any list	FIFO	I/L	Queue<E>*	container/list	VecDeque<T>
Deque	Any list	FIFO/LIFO	I/L	ArrayDeque<E>	container/list	VecDeque<T>

* via LinkedList<E>

Hierarchical Structures

General Trees

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
N-ary tree	Custom recursive tree node	U	I/L	Custom	Custom	Custom
Trie	Custom n-ary tree	S	I + L	Custom (TreeNode)	Custom	Custom

Search Trees

The most common search trees are binary search trees (BSTs)

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
BST	AVL tree	S	I/L	Custom	Custom	Custom
BST	Spaly tree	S				Custom
BST	(2, 4) tree	S				Custom
BST	Red-Black tree	S	I/L	TreeMap<K, V>	Custom	Custom
N-ary search tree	B-tree	S	I/L	Custom	Custom	Custom

Heaps

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
Heap	Binary heap	S	I/L	Custom	Custom	BinaryHeap<T>

Associative Structures

ADT	Data Structure	Sorted	Mem.	Java	Go	Rust
Map	Chaining hash table	U	I		Custom	Custom
Map	Probing hash table	U	I	HashMap<K, V>	Custom	Custom
Sorted map	Tree map or skip list	S	L + I			BTreeMap<K, V>
Multimap	Any hash table	S	I
Set	Any hash table or skip list	U	I	HashSet<E>	map[K]struct	HashSet<T>
Sorted set	Tree map or skip list	S	L + I

Graph Structures

ADT	Sorted/unsorted	Backing Structure	Java	Go	Rust
Directed graphs	U*	L/I	Custom (Graph<V, E>)	Custom	Custom
Undirected graphs	U	L/I	Custom	Custom	Custom
Weighted graphs	U**	L/I	Custom	Custom	Custom
Directed acyclic graphs	S***	L/I	Custom	Custom	Custom

* Sorted in topological applications

** Sorted for shortest paths

*** For topological ordering

Basic Algorithms

This section covers some common algorithmic themes. See the sub-sections for deeper dives into these algorithms.

Type	Sub-Type	Complexity	Std. Lib. Implementation
Sorting	Insertion sort	O(n^2)	Java/Rust:
	Merge sort		Java: Rust:
	Quick sort		Java/Rust:
Searching	Linear/sequential search	O(n)
	Binary search	O(log(n))
Hashing
Graph Algs.