You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson introduces the fundamental distinction between static and dynamic data structures — a key concept in A-Level Computer Science. Understanding how data structures allocate and manage memory is essential for choosing the right structure for a given problem.
A data structure is a way of organising, storing, and managing data so that it can be accessed and modified efficiently. Choosing the right data structure affects both the performance and correctness of a program.
Data structures can be classified as either static or dynamic, depending on how they allocate memory.
A static data structure has a fixed size that is determined at compile time (before the program runs). Once created, the amount of memory it uses cannot change.
| Feature | Description |
|---|---|
| Size | Fixed — must be declared when the structure is created. |
| Memory allocation | Allocated at compile time. |
| Memory usage | May waste memory if not fully used; cannot grow if more space is needed. |
| Access | Typically allows direct access (random access) to any element using an index. |
| Examples | Arrays (in most languages), fixed-size strings. |
// Pseudocode
DECLARE scores: ARRAY[0..9] OF INTEGER // Fixed size of 10
# Python lists are dynamic, but fixed-size arrays can be simulated:
import array
scores = array.array('i', [0] * 10) # Fixed-size integer array of 10
A dynamic data structure can grow and shrink during program execution. Memory is allocated and deallocated at runtime as needed.
| Feature | Description |
|---|---|
| Size | Variable — can grow or shrink at runtime. |
| Memory allocation | Allocated at runtime (on the heap). |
| Memory usage | Uses only as much memory as needed, but each element may require extra memory for pointers/references. |
| Access | May require sequential access (traversal) to find an element. |
| Examples | Linked lists, binary trees, stacks (linked), queues (linked). |
| Feature | Static | Dynamic |
|---|---|---|
| Size | Fixed at creation | Can change during execution |
| Memory allocation | Compile time | Runtime |
| Memory efficiency | May waste space | Uses only what is needed |
| Access speed | O(1) random access | O(n) sequential access (for linked structures) |
| Overflow risk | Yes — cannot grow | No — grows as needed |
| Pointer overhead | None | Yes — each node stores pointers |
| Example | Array | Linked list |
Exam Tip: A very common exam question asks you to compare static and dynamic data structures, explaining the advantages and disadvantages of each. Always give specific examples (e.g., arrays for static, linked lists for dynamic) and relate your answer to the scenario given in the question.
| Memory Area | Used For | Characteristics |
|---|---|---|
| Stack | Local variables, function call data | Fast, fixed size, LIFO, automatically managed |
| Heap | Dynamically allocated data (objects, nodes) | Slower, flexible size, manually or garbage-collected |
Static data structures are typically allocated on the stack (for local arrays) or in a fixed memory block. Dynamic data structures allocate nodes on the heap.
| Scenario | Recommended | Reason |
|---|---|---|
| The number of elements is known in advance | Static (array) | No overhead, fast access |
| The number of elements is unknown or changes frequently | Dynamic (linked list) | Can grow and shrink as needed |
| Fast random access to elements is required | Static (array) | O(1) index access |
| Frequent insertions and deletions are required | Dynamic (linked list) | No shifting of elements needed |
An Abstract Data Type (ADT) is a logical description of how data is viewed and the operations that can be performed on it, without specifying the implementation. A data structure is the concrete implementation of an ADT.
| ADT | Possible Implementations |
|---|---|
| Stack | Array-based stack, linked-list-based stack |
| Queue | Array-based queue, linked-list-based queue |
| List | Array, linked list |
| Map/Dictionary | Hash table, binary search tree |
Exam Tip: If asked "What is an abstract data type?", explain that it defines the operations (e.g., push, pop for a stack) without specifying how they are implemented. The implementation is the data structure.
Exam Tip: Be prepared to recommend either a static or dynamic data structure for a given scenario. Always justify your choice by explaining the trade-offs involved.