DATA STRUCTURES AND
ALGORITHMS
Complete Study Notes – Core Concepts and Applications
Anna University | B.E / [Link] Computer Science Engineering
Unit 1: Arrays and Linked Lists
1.1 Arrays
An array is a linear data structure that stores a collection of elements of the same
data type in contiguous memory locations. Each element is accessed by its index,
starting from 0.
• One-Dimensional Array: A single row of elements. Declaration: int arr[10];
• Two-Dimensional Array: A matrix of elements arranged in rows and columns.
Declaration: int matrix[3][3];
• Advantages: Constant-time O(1) access by index, simple implementation,
cache-friendly memory layout.
• Disadvantages: Fixed size, costly insertion/deletion at arbitrary positions
(O(n)), memory waste if not fully used.
1.2 Linked Lists
A linked list is a dynamic data structure where each element (called a node) stores
the data and a pointer to the next node. Unlike arrays, nodes are not stored
contiguously in memory.
• Singly Linked List: Each node points to the next node only. Traversal is one-
directional.
• Doubly Linked List: Each node has pointers to both the next and previous
nodes. Enables bidirectional traversal.
• Circular Linked List: The last node points back to the first node, forming a
circle.
• Advantages: Dynamic size, efficient O(1) insertion and deletion at the head.
• Disadvantages: No random access (O(n) search), extra memory for pointers,
poor cache performance.
Unit 2: Stacks and Queues
2.1 Stack
A stack is a linear data structure that follows the Last In First Out (LIFO) principle.
The element added most recently is the first to be removed.
• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.
• Peek/Top: View the top element without removing it.
• Applications: Function call management (call stack), expression evaluation,
undo functionality in editors, depth-first search (DFS).
2.2 Queue
A queue is a linear data structure that follows the First In First Out (FIFO) principle.
The element added first is the first to be removed.
• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove an element from the front of the queue.
• Circular Queue: A queue where the last position is connected to the first,
making efficient use of allocated memory.
• Priority Queue: Elements are dequeued based on their priority rather than
their order of insertion.
• Applications: CPU scheduling, print queue management, breadth-first search
(BFS), packet routing.
Unit 3: Trees
A tree is a non-linear hierarchical data structure consisting of nodes connected by
edges. It has a root node at the top, with child nodes branching below it.
3.1 Binary Tree
A binary tree is a tree where each node has at most two children, referred to as the
left child and the right child.
• Full Binary Tree: Every node has exactly 0 or 2 children.
• Complete Binary Tree: All levels are fully filled except possibly the last, which
is filled from left to right.
• Perfect Binary Tree: All internal nodes have two children and all leaf nodes
are at the same level.
3.2 Tree Traversal Techniques
• Inorder (Left – Root – Right): Visits the left subtree, then root, then right
subtree. Produces sorted output in BST.
• Preorder (Root – Left – Right): Visits root first, then left subtree, then right
subtree. Used for tree copying.
• Postorder (Left – Right – Root): Visits left and right subtrees first, then root.
Used for tree deletion.
• Level Order (BFS): Visits nodes level by level from top to bottom using a
queue.
3.3 Binary Search Tree (BST)
A BST is a binary tree where for each node, all values in the left subtree are less
than the node's value, and all values in the right subtree are greater.
• Search: Average O(log n), worst case O(n) for a skewed tree.
• Insertion: Follow BST property to find correct position and insert.
• Deletion: Three cases — node with no child, one child, or two children. Two-
child case replaces with inorder successor.
3.4 AVL Tree
An AVL tree is a self-balancing BST where the height difference (balance factor)
between left and right subtrees of any node is at most 1. Rotations (LL, RR, LR, RL)
are used to restore balance after insertions and deletions. All operations are
guaranteed O(log n).
Unit 4: Sorting Algorithms
Sorting is the process of arranging elements in a specific order (ascending or
descending). Different sorting algorithms have different time and space complexities
making them suitable for different scenarios.
4.1 Bubble Sort
• Repeatedly compares adjacent elements and swaps them if they are in the
wrong order.
• Time Complexity: O(n²) average and worst case; O(n) best case (already
sorted with optimization).
• Space Complexity: O(1) — in-place sorting.
4.2 Selection Sort
• Finds the minimum element in the unsorted part and places it at the beginning
in each pass.
• Time Complexity: O(n²) in all cases.
• Makes fewer swaps than Bubble Sort, suitable when write operations are
expensive.
4.3 Insertion Sort
• Builds the sorted array one element at a time by inserting each new element
into its correct position.
• Time Complexity: O(n²) average and worst; O(n) best case. Efficient for nearly
sorted data.
4.4 Merge Sort
• Divide and Conquer algorithm. Divides the array into halves, recursively sorts
each half, and merges them.
• Time Complexity: O(n log n) in all cases. Space Complexity: O(n).
• Stable sort — preserves the relative order of equal elements.
4.5 Quick Sort
• Divide and Conquer algorithm. Picks a pivot element and partitions the array
such that elements less than the pivot are on the left and greater ones are on
the right.
• Time Complexity: O(n log n) average; O(n²) worst case (poor pivot choice).
Space: O(log n).
• Generally the fastest in practice due to small constant factors and in-place
partitioning.
Unit 5: Graph Data Structure
A graph is a non-linear data structure consisting of a set of vertices (nodes) and
edges (connections) between them. Graphs are used to model relationships in real-
world problems such as social networks, maps, and computer networks.
5.1 Types of Graphs
• Directed Graph (Digraph): Edges have a direction — each edge goes from
one vertex to another.
• Undirected Graph: Edges have no direction — the connection between two
vertices is bidirectional.
• Weighted Graph: Each edge carries a numerical value (weight) representing
cost, distance, or time.
• Cyclic Graph: Contains at least one cycle (a path that starts and ends at the
same vertex).
• Acyclic Graph: Contains no cycles. A Directed Acyclic Graph (DAG) is widely
used in scheduling and dependency resolution.
5.2 Graph Representations
• Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there is an edge from
vertex i to vertex j. Space: O(V²). Efficient for dense graphs.
• Adjacency List: An array of lists where each index stores the list of
neighboring vertices. Space: O(V + E). Efficient for sparse graphs.
5.3 Graph Traversal Algorithms
• Breadth-First Search (BFS): Explores all neighbors at the current depth before
moving to the next level. Uses a queue. Time: O(V + E). Used for shortest
path in unweighted graphs.
• Depth-First Search (DFS): Explores as far as possible along each branch
before backtracking. Uses a stack (or recursion). Time: O(V + E). Used for
topological sorting and cycle detection.
5.4 Shortest Path Algorithms
• Dijkstra's Algorithm: Finds the shortest path from a source vertex to all other
vertices in a weighted graph with non-negative weights. Time: O((V + E) log
V) with a priority queue.
• Bellman-Ford Algorithm: Handles graphs with negative weight edges. Detects
negative weight cycles. Time: O(V × E).
• Floyd-Warshall Algorithm: Computes shortest paths between all pairs of
vertices. Time: O(V³). Suitable for dense graphs.
Two Marks Questions and Answers
Q1. 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. Examples include arrays, linked lists, stacks,
queues, trees, and graphs.
Q2. What is the difference between a stack and a queue?
A stack follows the LIFO (Last In First Out) principle, where the last element added is
the first to be removed. A queue follows the FIFO (First In First Out) principle, where
the first element added is the first to be removed.
Q3. Define AVL Tree.
An AVL tree is a self-balancing binary search tree where the balance factor (height
difference between left and right subtrees) of every node is maintained at -1, 0, or +1
through rotations after each insertion or deletion.
Q4. What is the time complexity of Quick Sort?
Quick Sort has an average and best case time complexity of O(n log n) and a worst
case of O(n²), which occurs when the pivot is always the smallest or largest element.
Space complexity is O(log n) due to recursive stack calls.
Q5. What is BFS and DFS?
BFS (Breadth-First Search) traverses a graph level by level using a queue, visiting
all neighbors before going deeper. DFS (Depth-First Search) explores as far as
possible along each path using a stack or recursion before backtracking.
Q6. What is a Binary Search Tree?
A Binary Search Tree is a binary tree where each node's left subtree contains values
less than the node and the right subtree contains values greater than the node. This
property allows for efficient searching, insertion, and deletion in O(log n) average
time.
Q7. Differentiate between Array and Linked List.
Arrays store elements in contiguous memory locations with fixed size and O(1)
random access. Linked lists store elements in non-contiguous nodes with dynamic
size but O(n) access time. Arrays are better for read-heavy operations; linked lists
suit frequent insertions and deletions.
Q8. What is Dijkstra's Algorithm used for?
Dijkstra's Algorithm is used to find the shortest path from a source vertex to all other
vertices in a weighted graph with non-negative edge weights. It uses a greedy
approach with a priority queue and runs in O((V + E) log V) time.
Data Structures and Algorithms | Study Notes | Anna University | Prepared for Academic Use