Data Structures Algorithms Tutorial

Introduction to Data Structures & Algorithms

Data structures are ways of organizing and storing data to enable efficient access and modification. Algorithms are step-by-step procedures for solving problems.

Why Learn Data Structures & Algorithms?

Problem Solving: Essential for solving complex programming problems
Efficiency: Write more efficient and optimized code
Interviews: Core topic in technical interviews
Foundation: Building blocks for advanced computer science concepts

Prerequisites

Basic programming knowledge in any language (Python, Java, C++)
Understanding of variables, loops, and functions
Basic mathematical concepts

Arrays

Arrays are collections of elements stored in contiguous memory locations. They provide O(1) access time to elements using indices.

Array Operations

# Python Array Examples
# Creating an array
arr = [1, 2, 3, 4, 5]

# Accessing elements
first_element = arr[0]  # O(1)
last_element = arr[-1]  # O(1)

# Insertion
arr.append(6)           # O(1) at end
arr.insert(0, 0)        # O(n) at beginning

# Deletion
arr.pop()               # O(1) from end
arr.pop(0)              # O(n) from beginning

# Searching
index = arr.index(3)    # O(n) linear search

Common Array Problems

Problem: Two Sum

Given an array of integers and a target sum, find two numbers that add up to the target.

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)  # Returns [0, 1]

Linked Lists

Linked lists are linear data structures where elements are stored in nodes, and each node contains data and a reference to the next node.

Types of Linked Lists

Singly Linked List: Each node points to the next node
Doubly Linked List: Each node has pointers to both next and previous nodes
Circular Linked List: Last node points back to the first node

Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_beginning(self, val):
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
    
    def delete_node(self, val):
        if not self.head:
            return
        
        if self.head.val == val:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next

Stacks & Queues

Stack (LIFO - Last In, First Out)

Elements are added and removed from the same end (top).

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None
    
    def is_empty(self):
        return len(self.items) == 0

Queue (FIFO - First In, First Out)

Elements are added at rear and removed from front.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        return None
    
    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None
    
    def is_empty(self):
        return len(self.items) == 0

Trees

Trees are hierarchical data structures with a root node and child nodes. Each node can have multiple children but only one parent.

Binary Tree Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def inorder_traversal(self, node):
        """Left -> Root -> Right"""
        if node:
            self.inorder_traversal(node.left)
            print(node.val, end=" ")
            self.inorder_traversal(node.right)
    
    def preorder_traversal(self, node):
        """Root -> Left -> Right"""
        if node:
            print(node.val, end=" ")
            self.preorder_traversal(node.left)
            self.preorder_traversal(node.right)
    
    def postorder_traversal(self, node):
        """Left -> Right -> Root"""
        if node:
            self.postorder_traversal(node.left)
            self.postorder_traversal(node.right)
            print(node.val, end=" ")

Binary Search Tree (BST)

A special type of binary tree where left subtree contains values less than root, and right subtree contains values greater than root.

Sorting Algorithms

Bubble Sort - O(n²)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Quick Sort - O(n log n)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

Time & Space Complexity

Big O notation describes the upper bound of algorithm performance in terms of time and space.

Common Time Complexities

Complexity	Name	Example	Description
O(1)	Constant	Array access	Same time regardless of input size
O(log n)	Logarithmic	Binary search	Time increases logarithmically
O(n)	Linear	Linear search	Time increases linearly
O(n log n)	Linearithmic	Merge sort	Efficient sorting algorithms
O(n²)	Quadratic	Bubble sort	Time increases quadratically

Data Structures & Algorithms Tutorial

Table of Contents