📚 Introduction to Data Structures & Algorithms

🟢 Beginner Foundation 30 min read
📑 In This Lesson
1 What is DSA?
2 Types of Data Structures
3 Types of Algorithms
4 Real World Applications
5 Why Learn DSA?
6 Memory & Performance
7 PHP & DSA
8 Interview Questions
9 Quiz
10 Practice Problems

🤔 What is Data Structures & Algorithms?

Data Structure is a way of organizing and storing data so that it can be accessed and modified efficiently.
Algorithm is a step-by-step procedure or formula for solving a problem.

Think of it this way:

Data Structure = Container

Like different types of containers in your kitchen - you use a glass for liquids, a plate for solids, and a bowl for soup. Similarly, you use an Array for indexed data, a Hash Map for key-value pairs, and a Tree for hierarchical data.

Algorithm = Recipe

Like following a recipe - you have ingredients (data) and step-by-step instructions (algorithm) to cook a dish (solve a problem). Binary Search, Merge Sort, and BFS are all algorithms.

🏗️ Types of Data Structures

📏 Linear Data Structures

Elements are arranged in a sequential order, one after another.

Structure Description Real Example
Array Fixed-size, contiguous memory List of students in a class
Linked List Nodes connected by pointers Train coaches linked together
Stack LIFO (Last In First Out) Undo button in editors
Queue FIFO (First In First Out) Waiting line at a ticket counter

🌳 Non-Linear Data Structures

Elements are arranged in a hierarchical or interconnected manner.

Structure Description Real Example
Tree Hierarchical, parent-child File system on your computer
Graph Nodes connected by edges Social network (friends)
Heap Priority-based tree Emergency room triage
Hash Table Key-value mapping Dictionary / phone book

⚙️ Types of Algorithms

Searching

Linear Search, Binary Search, BFS, DFS

Sorting

Bubble, Merge, Quick, Heap, Counting Sort

Recursion

A function calling itself to solve subproblems

Dynamic Programming

Breaking problems into overlapping subproblems

Greedy

Making locally optimal choices at each step

Backtracking

Exploring all possibilities, undoing wrong paths

🌍 Real World Applications

DSA Concept Real-World Use Example
Arrays Storing collections Image pixels, sensor data, contact lists
Stack Undo/Redo, Backtracking Browser history, text editor undo
Queue Task scheduling Printer queue, message processing, BFS
Hash Table Fast lookups Database indexing, caching, DNS resolution
Graph Networks & connections Google Maps routing, social networks, web crawling
Tree Hierarchical data File systems, HTML DOM, organizational charts
Heap Priority management Task schedulers, Dijkstra's algorithm, median finding
Trie String searching Autocomplete, spell checkers, IP routing

🎯 Why Should You Learn DSA?

✅ Get Hired

Google, Amazon, Microsoft, Facebook, and virtually every tech company tests DSA in interviews. It's the #1 factor in technical hiring decisions.

✅ Write Better Code

Choosing the right data structure can mean the difference between an app that handles 100 users vs 100 million users.

✅ Problem Solving Mindset

DSA teaches you to think systematically. You learn to break complex problems into manageable pieces - a skill valuable beyond programming.

✅ Foundation for Everything

System Design, Machine Learning, Database internals, Compiler design - all built on DSA fundamentals.

💾 Memory & Performance Basics

Understanding how data structures use memory is crucial:

🧱 Contiguous Memory (Arrays)
Memory: [10][20][30][40][50][--][--][--]
Address: 100 104 108 112 116 120 124 128
                     ↑
           Fast access: arr[2] = *(base + 2*size)

Arrays store elements in consecutive memory locations. Access is O(1) but insertion/deletion is O(n).

🔗 Linked Memory (Linked Lists)
[10|*]-->[20|*]-->[30|*]-->[40|X]
 100        250        500        700
↑ Each node stores data + pointer to next

Linked lists store elements anywhere in memory. Insertion/deletion is O(1) but access is O(n).

🐘 PHP and DSA

PHP provides excellent built-in data structures. Here's a quick overview:

<?php
// PHP's Array is actually an ordered hash map - very versatile!
$arr = [10, 20, 30, 40, 50];

// Access - O(1)
echo $arr[2]; // 30

// PHP also provides:
// - SplStack (Stack)
// - SplQueue (Queue)
// - SplHeap (Heap)
// - SplFixedArray (Fixed-size array)
// - SplObjectStorage (Set of objects)

// But for learning, we'll implement our own
// to understand how they work internally!

$stack = new SplStack();
$stack->push('A');
$stack->push('B');
echo $stack->pop(); // B (LIFO)

// DSA concept: Find maximum in array
function findMax(array $arr): int {
    $max = PHP_INT_MIN;
    foreach ($arr as $val) {
        if ($val > $max) $max = $val;
    }
    return $max;
}

echo findMax([3, 7, 2, 9, 1]); // 9 - O(n) time, O(1) space

💼 Interview Questions

A data structure is how we organize and store data (e.g., Array, Tree, Hash Table). An algorithm is a step-by-step procedure to solve a problem using those data structures (e.g., Binary Search, Merge Sort). Data structures are the "what"; algorithms are the "how."

Choose Linked List when you need frequent insertions/deletions at the beginning or middle and don't need random access. Choose Array when you need fast random access (O(1)) and the size is relatively fixed. Linked Lists use more memory per element (pointer overhead).

An ADT defines what operations are supported (interface), not how they're implemented. A Data Structure is the concrete implementation. For example, a Stack ADT defines push/pop/peek operations. You can implement it using an Array or a Linked List. The ADT is the contract; the data structure is the implementation.

📝 Quick Quiz

Q1: Which of these is a linear data structure?

Q2: What does LIFO stand for?

Q3: Which data structure is best for implementing an "Undo" feature?

Q4: Which of the following is NOT a characteristic of a good algorithm?

Q5: PHP's built-in array is actually implemented as a(n):

✏️ Practice Problems

Reverse an Array
Easy

Write a function that reverses an array in-place without using built-in functions.

Try It
Find Duplicate
Easy

Given an array of n+1 integers where each is between 1 and n, find the duplicate.

Try It
Valid Parentheses
Medium

Check if a string of brackets/parentheses is valid using a stack.

Try It

📋 Cheat Sheet

Data Structure Way to organize and store data
Algorithm Step-by-step procedure to solve a problem
Linear DS Array, Linked List, Stack, Queue
Non-Linear DS Tree, Graph, Heap, Hash Table, Trie
ADT Abstract Data Type - defines operations, not implementation
Time Complexity How runtime grows with input size
Space Complexity How memory usage grows with input size
Next: Time & Space Complexity