Guide · Algorithms · Data structures

Data Structures – Learning Guide

A data structure is the way data is stored in memory. The choice of structure determines how quickly an element is added, removed or found – which is why the same task can take a second or an hour.

The guide goes from the array, the string and the matrix, through the stack, the queue and sets, to the structures used in the national competition and SIO: the Fenwick tree and the segment tree.

  • Grades 6–8 and secondary school
  • C++
  • Competition preparation
How to choose a structure: ask yourself which operations the task does most often – access by index (array), adding/removing at the end (stack) or at the beginning (queue), searching and removing duplicates (set), counting (map), the smallest element that keeps changing (priority_queue), a sum over an interval with updates (Fenwick).

Some lessons linked below are available only in Serbian for now. They are marked (SR).

1 Basic structures

The array, the string, the matrix, structures and vectors – the foundation of all the others.

2 Linear structures

Elements arranged one after another, with different rules for adding and removing.

3 Sets, maps and the priority queue

Ready-made structures from the C++ library that work in O(log n).

4 Advanced structures

Structures for the national competition and SIO.

Suggested order

  1. Array, string and matrix – tasks
  2. Structures and unions
  3. Vectors
  4. Linked lists
  5. Stack (SR)
  6. Queue (SR)
  7. Sets and maps (SR)
  8. Priority queue (SR)
  9. Disjoint Set Union
  10. Fenwick tree (SR)
  11. Segment tree (SR)

Useful external resources