Data Structures | Knowledge Base by Andrii Sonsiadlo

📄️Overview

A data structure is a decision about which operations you want to be cheap. There is no structure

An array is a block of contiguous memory holding equally-sized elements. That one property gives it

A linked list stores each element in its own node, together with a pointer to the next one. Nothing

Stacks and queues are not new storage — they are restrictions on storage. Both hold a sequence,

A hash table turns a key into an array index by running it through a hash function, then reads or

A tree is a set of nodes where each node has one parent (except the root) and no cycles. That single

A binary search tree is $O(\log n)$ only while it stays short, and nothing in the plain

A priority queue answers one question: what is the most important item right now? A binary

A graph is a set of vertices and a set of edges connecting them. That is nearly no structure

Some problems never ask what is in a group. They ask only whether two things have ended up in the

A hash set answers "is this exact string in the set?" and nothing else. It cannot answer "what strings

Prefix sums answer range-sum

A stack grows and shrinks at one end; a queue adds

Every structure so far in this section answers its question exactly, at the cost of storing enough

A cache with unlimited capacity is just a hash table. The interesting problem

This page is a reference, not a tutorial — each page in this section explains the reasoning behind the