Static and Dynamic Data Structures

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.

---

What is a Data Structure?

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.

---

Static Data Structures

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.

Characteristics

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.

Example: Array Declaration

// 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

Advantages of Static Data Structures

• Predictable memory usage — the compiler knows exactly how much memory is needed.
• Fast access — elements can be accessed directly by index in O(1) time.
• Simple implementation — no overhead for managing dynamic memory.
• No memory fragmentation — memory is allocated as a single contiguous block.

Disadvantages of Static Data Structures

• Wasted memory — if fewer elements are stored than the allocated size, memory is wasted.
• Overflow — if more elements are needed than the allocated size, the structure cannot grow.
• Fixed capacity — the maximum number of elements must be known in advance.

---

Dynamic Data Structures

A dynamic data structure can grow and shrink during program execution. Memory is allocated and deallocated at runtime as needed.

Characteristics

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).

Advantages of Dynamic Data Structures

• Flexible size — can grow and shrink as data is added or removed.
• Efficient memory usage — no wasted space for unused elements.
• No predefined capacity — limited only by available system memory.

Disadvantages of Dynamic Data Structures

• Overhead — each element stores additional data (e.g., pointers to the next element).
• Slower access — finding an element may require traversing the structure (O(n) time).
• Memory fragmentation — elements may be scattered across memory.
• More complex implementation — requires careful memory management.

---

Comparison Table

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: Stack vs Heap

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.

---

Choosing Between Static and Dynamic

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

---

Abstract Data Types vs Data Structures

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.

---

Summary

• Static data structures have a fixed size, are allocated at compile time, and offer fast random access (e.g., arrays).
• Dynamic data structures can grow and shrink at runtime, but may have slower access and require pointer overhead (e.g., linked lists).
• The choice depends on whether the data size is known, whether fast access or flexible size is more important, and how frequently insertions/deletions occur.
• Abstract Data Types describe operations; data structures implement them.

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.