Skip to content

Data structures and algorithms

~12 min

In short

A data structure is a way of storing data so that certain operations are fast. An algorithm is a step-by-step method for solving a problem. This page explains the core ideas, the order to learn them in, and how to practise without memorising solutions.

What the subject is about

Most programs spend their time looking things up, sorting things, and moving through collections. The shape you choose for the data decides how fast those operations are. A list is good for ordered items you read in sequence. A dictionary (hash table) is good for finding a value by key. A heap gives you the smallest item quickly. A graph models roads, friendships, or dependencies.

The second half of the subject is analysis. Big-O notation describes how the running time or memory grows as the input grows. You do not need exact formulas at the start. You need to see that a loop nested inside another loop over the same input is usually quadratic, and that halving the search space at each step gives logarithmic time.

What to learn first

  1. Big-O notation: what it measures and what it ignores.
  2. Arrays and lists: indexing, appending, and the cost of inserting in the middle.
  3. Linear search and binary search on sorted data.
  4. Stacks and queues, and where they appear in real programs.
  5. Hash tables: average-case lookup and why collisions matter.
  6. Sorting: at least one simple method (insertion or selection) and one fast method (merge sort).
  7. Linked lists and the trade-off against arrays.
  8. Binary trees and binary search trees.
  9. Heaps and priority queues.
  10. Graphs: adjacency lists, breadth-first search, depth-first search.

The site's Python course has a section that goes through several of these in practice. Start with ../../python/05-cp-data-structures/index.md, especially ../../python/05-cp-data-structures/04-deque-and-heap.md. For complexity and search patterns, see ../../python/06-codeforces-patterns/02-complexity-and-pypy.md and ../../python/06-codeforces-patterns/05-binary-search.md.

What you can skip at first

  • Red-black trees, B-trees, and other balanced trees. Learn their purpose first. The implementation details can wait.
  • Advanced graph algorithms such as shortest paths with negative weights or network flow.
  • Dynamic programming. It is hard for most first-year students. Come back after you are comfortable with recursion and arrays.
  • Writing every sort from memory before an exam. Understand what each one does and how fast it is. Memorising code is less useful.

How it connects to the other subjects

Hash tables appear inside databases (indexes and joins) and inside operating systems (page tables and caches). Trees underlie database indexes; B-trees are the usual choice for disk-based storage. Graphs describe network routing and dependency resolution. Complexity analysis is the same tool you will use when you reason about how a database query scales.

Algorithms also depend on the computer's actual behaviour. Two algorithms with the same Big-O can run at different speeds because of memory access patterns. That link is covered in computer architecture.

Free resources

  • MIT 6.006, Introduction to Algorithms (https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/). Full lecture notes and problem sets from MIT OpenCourseWare. It suits a student who wants a rigorous course with proofs.
  • VisuAlgo (https://visualgo.net/). Animated step-by-step views of sorting, trees, heaps, and graph algorithms. It suits someone who understands things better by watching them run.
  • Big-O Cheat Sheet (https://www.bigocheatsheet.com/). A one-page reference for the running times of common operations. It suits quick lookup while you practise, not as a substitute for learning the reasons.
  • Algorithms, 4th edition, Sedgewick and Wayne (https://algs4.cs.princeton.edu/home/). The book's companion site with code and slides. It suits someone who likes to read the code alongside the explanation.

Practice

  1. Write a function that finds the largest element in a list and state its running time in Big-O. Then explain why it cannot be faster in the worst case.
  2. Implement binary search on a sorted list. Test it on an empty list, a list with one item, and a value that is not present.
  3. Use a dictionary to count how often each word appears in a paragraph. Compare the time it takes with a version that uses a list of pairs and linear search.
  4. Implement a stack with push and pop, then use it to check whether brackets in a string are balanced.
  5. Represent a small graph of five cities as an adjacency list, then write a breadth-first search that prints the cities in the order they are visited.

Sources

  • MIT OpenCourseWare, 6.006 Introduction to Algorithms, https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
  • VisuAlgo, https://visualgo.net/
  • Big-O Cheat Sheet, https://www.bigocheatsheet.com/
  • Sedgewick and Wayne, Algorithms, 4th edition, companion site, https://algs4.cs.princeton.edu/home/