Introduction to Dynamic
Data Structures
Welcome to Day 1. This lesson provides a foundational overview of how
modern computing systems manage and manipulate data, focusing on
the distinction between static and dynamic structures.
Overview and Learning Outcomes
Differentiate Data Compare Core Explain Real-World
Structures Structures Necessity
Distinguish clearly between static Compare and contrast arrays and Understand why dynamic data
and dynamic data structures and linked lists concerning memory management is essential for
their core characteristics. usage, access speed, and flexibility. modern, evolving systems like e-
commerce and logistics databases.
Concepts: Static vs. Dynamic Data Structures
The fundamental difference lies in how memory is managed and allocated during the program's lifecycle.
Static Data Structures Fixed-size structures Memory allocated once, easier to Arrays
determined at compile manage, limited flexibility.
time.
Dynamic Data Structures Size can change flexibly at Memory allocated/deallocated as Linked Lists,
runtime. needed, more complex, highly flexible. Trees
Memory Management in Data Structures
Static Memory Allocation Dynamic Memory Allocation
Memory is allocated contiguously in a block (usually on the Memory is non-contiguous; elements are linked using
stack or in the data segment). pointers or references (stored on the heap).
Leads to faster access due to locality of reference. Highly adaptable: size can grow or shrink easily.
Less adaptable: resizing means creating a new structure Requires overhead for managing pointers and depends
and copying all elements. on mechanisms like Garbage Collection (GC) in some
languages.
When to Use Static vs.
Dynamic Structures
Static Structures: Known and Stable Data
Use when the maximum size of the data is known and
unchanging. Example: The 12 months in a year, or a fixed-size
buffer for a specific task.
Dynamic Structures: Unpredictable Growth
Essential when data grows, shrinks, or changes unpredictably.
Example: Online inventory systems, active user lists, or
transaction queues.
Comparison: Arrays vs. Linked Lists
Arrays (static) and Linked Lists (dynamic) are fundamental contrasting data structures.
Memory Allocation Contiguous (Static) Non-contiguous (Dynamic)
Size Flexibility Fixed Can grow/shrink at runtime
Access Time O(1) (Fast Random Access) O(n) (Sequential Access)
Insertion/Deletion Expensive (Requires shifting Efficient (Adjust pointers, O(1) in the
elements) middle)
Memory Overhead Minimal Requires extra memory for pointers
Cache Performance Better (Data is close together) Poorer (Data is scattered across
memory)
Code Example: The Structural Difference
Array (Fixed Size) Linked List (Node-Based)
Simple, direct access to elements via index. Each element (Node) holds data and a pointer to the next element.
// C++ Example // C++ Example Node Structure
int arr[5] = {1, 2, 3, 4, 5}; struct Node {
int data;
// Accessing the third element: Node* next;
int value = arr[2]; // O(1) access };
// Requires traversal to find elements:
// Find 4: start from head, follow 'next' 3 times.
Real-World Context: The Importance of
Dynamic Data
Dynamic data structures are crucial for systems that must handle growth and frequent changes without interruption.
E-commerce & Logistics Social Media Platforms Dynamic Routing & Tracking
Supply chain inventory, order User connections, message threads, Systems determining the most efficient
processing queues, and real-time and constantly generated feeds path for a delivery fleet must
shipment tracking all rely on structures demand structures that support dynamically update routes based on
that can scale instantly. continuous additions and removals of traffic and new orders, often using
nodes. graph structures (which are dynamic).
Case Study: Dynamic Data in Supply Chain
Management
Linked lists and other dynamic structures directly support sustainable resource management (SDG 12) by ensuring systems are
accurate and responsive.
Real-time Inventory Tracking Supplier Data Updates
Dynamically add or remove items from Efficiently update supplier information
the stock list as they are received or sold, without needing to restructure the
preventing overstocking or stockouts. entire database.
Scalable Processing Efficient Disposal
Handle peak demand periods (e.g., Quickly identify and remove obsolete or
holidays) by scaling up transaction expired stock items, reducing waste and
processing queues dynamically. supporting responsible consumption.
Discussion and Activity: Putting Theory into
Practice
Class Discussion Points Mini-Activity: Inventory Structures
What happens if we try to use a fixed-size array to handle Task: On paper, model a simple "warehouse inventory" for 5
an ever-changing online product catalog? items using both an array and a linked list structure.
Why might dynamic structures reduce wasted memory
Add a 6th item (Overflow for the array).
but simultaneously increase overall system complexity?
Remove the 3rd item (Shifting for the array).
Can you think of a scenario where an array is strictly
better than a linked list? Goal: Visualize which structure handles these modifications
more efficiently and why.