Data Structures and Algorithms

A Comprehensive Study Guide for Computer Science Students

University: Savitribai Phule Pune University (SPPU)

Course: Second Year Engineering - Computer Science & IT

Subject Code: 210241

Academic Year: 2024-2025

Unit 1: Introduction to Data Structures

1.1 What are Data Structures?

Data structures are specialized formats for organizing, processing, retrieving, and storing
data. They enable efficient access and modification of data and are essential building blocks
of algorithms.

Key Concept: A data structure is not just about storing data, but about organizing it in a
way that enables efficient operations like insertion, deletion, searching, and traversal.

1.2 Classification of Data Structures

Primitive Data Structures:

Integer

Float

Character

Boolean

Non-Primitive Data Structures:

Linear: Arrays, Linked Lists, Stacks, Queues

 Non-Linear: Trees, Graphs

1.3 Abstract Data Types (ADT)

An ADT is a mathematical model that defines data types by their behavior from the point of
view of a user, specifically in terms of possible values, operations, and behavior.

Example: A Stack ADT supports operations like push(), pop(), peek(), isEmpty()
without specifying how these operations are implemented internally.

Unit 2: Arrays and Strings

2.1 Arrays

An array is a collection of elements of the same type stored in contiguous memory locations.
Arrays provide constant-time access to elements using indices.

Operation Time Complexity Description

Access O(1) Direct access using index

Search O(n) Linear search in unsorted array

Insertion O(n) May require shifting elements

Deletion O(n) May require shifting elements

2.2 Common Array Operations

// Array Declaration and Initialization int arr[5] = {1, 2, 3, 4, 5}; //

Traversal for(int i = 0; i < 5; i++) { printf("%d ", arr[i]); } //
Insertion at position void insert(int arr[], int n, int pos, int value) {
for(int i = n; i > pos; i--) { arr[i] = arr[i-1]; } arr[pos] = value; }

2.3 Two-Dimensional Arrays

2D arrays are arrays of arrays, commonly used to represent matrices and tables.
 Important: In C/C++, 2D arrays are stored in row-major order in memory.
Understanding memory layout is crucial for optimization.

Unit 3: Linked Lists

3.1 Introduction to Linked Lists

A linked list is a linear data structure where elements are not stored in contiguous memory
locations. Each element (node) contains data and a reference (pointer) to the next node.

3.2 Types of Linked Lists

1. Singly Linked List:

Each node points to the next node

Last node points to NULL

Traversal is only in forward direction

2. Doubly Linked List:

Each node has pointers to both next and previous nodes

Allows bidirectional traversal

Requires more memory than singly linked list

3. Circular Linked List:

Last node points back to the first node

No NULL pointer at the end

Useful for round-robin scheduling

// Node Structure for Singly Linked List struct Node { int data; struct
Node* next; }; // Creating a new node struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data; newNode->next = NULL; return newNode; } //
Insertion at beginning void insertAtBeginning(struct Node** head, int
data) { struct Node* newNode = createNode(data); newNode->next = *head;
*head = newNode; }
3.3 Advantages and Disadvantages

Advantages:

Dynamic size - can grow or shrink during runtime

Efficient insertion and deletion (O(1) at known positions)

No memory wastage

Disadvantages:

Random access not possible (O(n) to access elements)

Extra memory for pointers

Not cache-friendly due to non-contiguous memory

Unit 4: Stacks and Queues

4.1 Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements
are added and removed from the same end called the "top".

Stack Operations:

push(item): Add an item to the top

pop(): Remove and return the top item

peek(): Return the top item without removing it

isEmpty(): Check if stack is empty

isFull(): Check if stack is full (for array implementation)

4.2 Applications of Stack

Function call management (call stack)

Expression evaluation (infix to postfix conversion)

Undo mechanism in text editors

Backtracking algorithms
 Browser history (back button)

Example - Balanced Parentheses: Use a stack to check if parentheses in an expression

are balanced. Push opening brackets, pop for closing brackets, and verify they match.

4.3 Queue

A queue is a linear data structure that follows the First In First Out (FIFO) principle. Elements
are added at the rear and removed from the front.

Queue Operations:

enqueue(item): Add an item to the rear

dequeue(): Remove and return the front item

front(): Return the front item without removing

isEmpty(): Check if queue is empty

4.4 Types of Queues

Simple Queue: Basic FIFO structure

Circular Queue: Last position connected back to first position

Priority Queue: Elements have priorities; highest priority served first

Double-Ended Queue (Deque): Insertion and deletion at both ends

Unit 5: Trees

5.1 Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children,
referred to as left child and right child.

Tree Terminology:

Root: The topmost node

Parent: A node that has children

 Child: A node connected below another node

Leaf: A node with no children

Height: Length of longest path from root to leaf

Depth: Length of path from root to a node

5.2 Binary Search Tree (BST)

A Binary Search Tree is a binary tree with the following properties:

Left subtree contains nodes with values less than parent

Right subtree contains nodes with values greater than parent

Both left and right subtrees are also BSTs

Operation Average Case Worst Case

Search O(log n) O(n)

Insertion O(log n) O(n)

Deletion O(log n) O(n)

5.3 Tree Traversal Methods

1. Inorder Traversal (Left-Root-Right):

Gives nodes in ascending order for BST

Used for expression tree evaluation

2. Preorder Traversal (Root-Left-Right):

Used to create a copy of tree

Used for prefix expression

3. Postorder Traversal (Left-Right-Root):

Used to delete a tree

Used for postfix expression

4. Level Order Traversal:

Visits nodes level by level

Uses queue for implementation

Unit 6: Graphs

6.1 Graph Representation

A graph G = (V, E) consists of a set of vertices V and a set of edges E. Graphs can be directed
or undirected.

Representation Methods:

1. Adjacency Matrix:

2D array of size V × V

Space complexity: O(V²)

Edge lookup: O(1)

Good for dense graphs

2. Adjacency List:

Array of lists

Space complexity: O(V + E)

Edge lookup: O(V)

Good for sparse graphs

6.2 Graph Traversal Algorithms

Breadth-First Search (BFS):

Explores vertices level by level

Uses queue data structure

Time complexity: O(V + E)

Applications: Shortest path, connected components

Depth-First Search (DFS):

 Explores as far as possible along each branch

Uses stack (or recursion)

Time complexity: O(V + E)

Applications: Cycle detection, topological sorting

Unit 7: Sorting Algorithms

7.1 Comparison of Sorting Algorithms

Algorithm Best Case Average Case Worst Case Space Stable

Bubble Sort O(n) O(n²) O(n²) O(1) Yes

Selection Sort O(n²) O(n²) O(n²) O(1) No

Insertion Sort O(n) O(n²) O(n²) O(1) Yes

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes

Quick Sort O(n log n) O(n log n) O(n²) O(log n) No

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

Exam Tip: Be prepared to analyze time complexity, write pseudocode, and trace
algorithms with sample inputs. Understanding when to use which sorting algorithm is
crucial.

7.2 Key Sorting Concepts

Stable Sorting: Maintains relative order of equal elements

In-place Sorting: Requires only constant extra space (O(1))

Adaptive Sorting: Performance improves on partially sorted data

Unit 8: Searching Algorithms

8.1 Linear Search

Sequentially checks each element

Time complexity: O(n)

Works on unsorted arrays

Simple but inefficient for large datasets

8.2 Binary Search

Divides search space in half each iteration

Time complexity: O(log n)

Requires sorted array

Much more efficient than linear search

// Binary Search Implementation int binarySearch(int arr[], int n, int

target) { int left = 0, right = n - 1; while(left <= right) { int mid =
left + (right - left) / 2; if(arr[mid] == target) return mid; else
if(arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1;
// Not found }

8.3 Hashing

Hashing provides average O(1) time complexity for search, insert, and delete operations using
hash functions and hash tables.

Collision Resolution Techniques:

Chaining: Each bucket contains a linked list of elements

Open Addressing: Linear probing, quadratic probing, double hashing

Practice Problems and Important Questions

Previous Year Exam Questions (SPPU Pattern)

Q1: Implement a stack using arrays. Write functions for push, pop, and display
operations. Also explain overflow and underflow conditions. (10 marks)
 Q2: Explain Binary Search Tree with suitable example. Write an algorithm for insertion
and deletion in BST. (10 marks)

Q3: Compare and contrast BFS and DFS graph traversal algorithms. Trace both
algorithms on a given graph. (8 marks)

Q4: Write a program to convert infix expression to postfix expression using stack.
Explain with example: A + B * C - D / E (10 marks)

Q5: Explain Quick Sort algorithm with an example. Analyze its time complexity for
best, average, and worst cases. (8 marks)

Important Topics for Examination

1. Time and Space complexity analysis (Big O notation)

2. Stack applications: Expression conversion, evaluation

3. Linked list operations: Insertion, deletion, reversal

4. Tree traversals: Inorder, Preorder, Postorder, Level order

5. Binary Search Tree operations and properties

6. Graph representations and traversal algorithms

7. Sorting algorithms: Merge sort, Quick sort, Heap sort

8. Hashing and collision resolution techniques

9. Recursion and its applications

10. Dynamic programming basics

Study Tips and Exam Strategy

Preparation Strategy:

Practice coding implementations by hand

Trace algorithms with different inputs

 Understand time and space complexity derivations

Solve previous year question papers

Create flowcharts and diagrams for complex concepts

Form study groups for algorithm discussions

Common Mistakes to Avoid

Not checking boundary conditions (empty lists, single element)

Forgetting to update pointers in linked list operations

Incorrect complexity analysis

Not handling base cases in recursion

Mixing up traversal order in trees

Not initializing variables properly

Recommended Resources

Textbooks: "Data Structures Using C" by Reema Thareja

Online: GeeksforGeeks, LeetCode for practice problems

Video Lectures: MIT OpenCourseWare, Abdul Bari on YouTube

Practice: HackerRank, CodeChef for coding practice

Study Guide prepared for Pune University Students

This document covers key concepts from the Data Structures and Algorithms syllabus

For detailed explanations and additional practice, refer to your course textbooks and lecture notes

© 2024 | Educational Resource | Not affiliated with SPPU