B2.2 Data structures

A <strong>data structure</strong> is a way of organising and storing data in a computer so that it can be accessed and modified efficiently. Choosing the right data structure for a problem is one of the most important decisions in programming , it affects memory usage, speed, and the complexity of your code.

In IB Computer Science, you need to understand two broad categories:

• Static data structures , fixed in size, allocated at compile time
• Dynamic data structures , flexible in size, can grow or shrink at runtime

You also need to understand specific structures like queues, which follow particular rules about how data is added and removed.

Static Data Structure: A data structure whose size is fixed at compile time and cannot be changed during program execution. Memory is allocated in a single contiguous block.

Key characteristics of static data structures:

• Fixed size: You must declare the size before the program runs , it cannot grow or shrink.
• Contiguous memory: All elements are stored next to each other in memory, which allows fast, direct access to any element.
• Compile-time allocation: The operating system reserves the exact amount of memory needed before the program even starts.

Examples:

• Arrays in Java (e.g., int[] scores = new int[30];)
• Tuples in Python (e.g., seats = (1, 2, 3, 4, 5))

Advantages:

• Faster element access due to contiguous memory layout
• Simpler to implement and manage
• Predictable memory usage

Disadvantages:

• Cannot resize during runtime , inflexible
• If you over-allocate (reserve more space than needed), unused memory is still occupied , this is called memory waste
• If you under-allocate, you risk an overflow error