Data Structures and Algorithms – Complete Notes for Engineering Students

Introduction to Data Structures and Algorithms

Data Structures and Algorithms (DSA) is the foundation of computer science and is essential for technical interviews, competitive programming, and building efficient software. This comprehensive guide covers all important topics for engineering students.

What is a Data Structure?

A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently. The choice of data structure affects the performance of algorithms.

Classification of Data Structures

Linear Data Structures

• Array: Fixed-size collection of elements
• Linked List: Elements connected through pointers
• Stack: LIFO (Last In First Out) structure
• Queue: FIFO (First In First Out) structure

Non-Linear Data Structures

• Trees: Hierarchical structure with nodes
• Graphs: Nodes connected by edges
• Heaps: Complete binary tree with heap property
• Hash Tables: Key-value pairs with hash function

Arrays

Characteristics

• Fixed size (in most languages)
• Contiguous memory allocation
• O(1) access time for any element
• O(n) insertion/deletion in middle

Common Operations

• Access: O(1)
• Search: O(n) for unsorted, O(log n) for sorted
• Insertion: O(n) at arbitrary position
• Deletion: O(n) at arbitrary position

Linked Lists

Types

• Singly Linked List: Each node points to next node
• Doubly Linked List: Nodes have prev and next pointers
• Circular Linked List: Last node points to first

Time Complexity

• Access: O(n)
• Search: O(n)
• Insertion at head: O(1)
• Deletion at head: O(1)
• Insertion/Deletion at tail: O(n) for singly, O(1) for doubly

Stacks

Operations

• Push: Add element to top – O(1)
• Pop: Remove element from top – O(1)
• Peek: View top element – O(1)
• isEmpty: Check if empty – O(1)

Applications

• Function call management (Call stack)
• Expression evaluation (Postfix, Prefix)
• Undo operations in text editors
• Backtracking algorithms
• Balanced parentheses checking

Queues

Types

• Simple Queue: Basic FIFO
• Circular Queue: Circular buffer implementation
• Priority Queue: Elements dequeued by priority
• Deque: Double-ended queue

Applications

• CPU scheduling
• Printer queue
• BFS traversal in graphs
• Message queues in systems

Trees

Binary Tree Properties

• Maximum nodes at level i: 2^i
• Maximum nodes in tree of height h: 2^(h+1) – 1
• Minimum height for n nodes: log2(n+1) – 1

Binary Search Tree (BST)

• Left subtree has smaller values
• Right subtree has larger values
• Search, Insert, Delete: O(log n) average, O(n) worst

Tree Traversals

• Inorder (LNR): Left, Node, Right – gives sorted order for BST
• Preorder (NLR): Node, Left, Right – used for copying tree
• Postorder (LRN): Left, Right, Node – used for deletion
• Level Order: BFS traversal using queue

AVL Trees

• Self-balancing BST
• Balance factor: height(left) – height(right)
• Balance factor must be -1, 0, or 1
• Rotations: LL, RR, LR, RL
• All operations: O(log n)

Graphs

Representations

• Adjacency Matrix: 2D array, O(V^2) space
• Adjacency List: Array of lists, O(V+E) space

Graph Traversals

• BFS (Breadth First Search): Uses queue, O(V+E)
• DFS (Depth First Search): Uses stack/recursion, O(V+E)

Important Graph Algorithms

• Dijkstras Algorithm: Single source shortest path, O(V^2) or O(E log V)
• Bellman-Ford: Handles negative weights, O(VE)
• Floyd-Warshall: All pairs shortest path, O(V^3)
• Prims/Kruskals: Minimum Spanning Tree
• Topological Sort: DAG ordering

Sorting Algorithms

Comparison-Based Sorting

Searching Algorithms

• Linear Search: O(n) – works on any array
• Binary Search: O(log n) – requires sorted array
• Interpolation Search: O(log log n) average for uniform distribution

Dynamic Programming

Key Concepts

• Optimal Substructure: Optimal solution contains optimal solutions to subproblems
• Overlapping Subproblems: Same subproblems solved multiple times

Common DP Problems

• Fibonacci Series
• 0/1 Knapsack
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS)
• Matrix Chain Multiplication
• Coin Change Problem
• Edit Distance

Time Complexity Cheat Sheet

• O(1) – Constant: Array access, Hash table operations
• O(log n) – Logarithmic: Binary search, BST operations
• O(n) – Linear: Linear search, Single loop
• O(n log n) – Log-linear: Merge sort, Heap sort
• O(n^2) – Quadratic: Bubble sort, Nested loops
• O(2^n) – Exponential: Recursive fibonacci, Subsets
• O(n!) – Factorial: Permutations

Tips for Coding Interviews

1. Practice at least 200-300 problems on LeetCode/HackerRank
2. Focus on patterns rather than memorizing solutions
3. Always analyze time and space complexity
4. Start with brute force, then optimize
5. Communicate your thought process clearly