Data Structures: Module 1 Study Guide

Comprehensive Review Notes for Exam Preparation

Unit 1: Introduction to Data Structures

1.1 Definition

A Data Structure is a specialized format for organizing, processing, retrieving, and storing data
in a computer so that it can be used efficiently. It is the logical or mathematical model of a
particular organization of data.

1.2 Classification of Data Structures

• Linear Data Structures: Elements are arranged in a sequential or linear order, where each
element is attached to its previous and next adjacent elements. Examples: Arrays, Linked
Lists, Stacks, Queues.

• Non-Linear Data Structures: Elements are not arranged sequentially. An element can be
connected to more than two other elements, forming a hierarchical relationship. Examples:
Trees, Graphs.

• Static Data Structures: The size and memory locations are allocated at compile time. The
size cannot be changed during runtime. Example: Arrays.

• Dynamic Data Structures: Memory is allocated at runtime. The size can shrink or grow
depending on the requirements. Example: Linked Lists.

1.3 Data Structure Operations

The standard operations performed on data structures include:

• Traversing: Accessing each data item exactly once to process it.

• Searching: Finding the location of a specific data item.

• Inserting: Adding a new data item to the structure.

• Deleting: Removing a specific data item from the structure.

• Sorting: Arranging the data items in a specific logical order (ascending or descending).

• Merging: Combining the data items of two sorted files into a single sorted file.
1.4 Applications

Operating System design (Queues for scheduling), Compiler design (Hash tables, Stacks for syntax
parsing), Database Management Systems (B-Trees for indexing), and Artificial Intelligence
(Graphs for pathfinding).

Unit 2: Array

2.1 Single Dimensional Array & Memory Representation

An array is a linear collection of homogenous (same type) data elements stored at contiguous
memory locations. It is the simplest data structure where each data element can be randomly
accessed by using its index number.

Memory Representation Formula:

Address(A[i]) = Base_Address + (i - lower_bound) × size

Where Base_Address is the address of the first element, and size is the memory required by
one element (e.g., 4 bytes for integer in C). Assuming 0-based indexing, it simplifies to
Address(A[i]) = B + i × c.

2.2 Operations: Insertion and Deletion

• Insertion: To insert an element at position k, all elements from index k to the end of the array
must be shifted one position to the right to create space. This takes O(n) time in the worst
case.

• Deletion: To delete an element at position k, all elements from index k+1 to the end must be
shifted one position to the left to fill the gap. This also takes O(n) time.

Unit 3: Searching

3.1 Linear Search

A simple sequential search algorithm that starts at one end and goes through each element of a
list until the desired element is found, otherwise the search continues till the end of the data set.

• Pre-requisite: None (array can be unsorted).

• Time Complexity: Best Case: O(1), Worst Case: O(n).

A search algorithm that finds the position of a target value within a sorted array using a divide
and conquer strategy. It compares the target value to the middle element of the array.

// Binary Search Pseudo-code

• Pre-requisite: Array MUST be sorted.

• Time Complexity: Best Case: O(1), Worst Case: O(log n).

Unit 4: Sorting

4.1 Bubble Sort

Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the
wrong order. The pass through the list is repeated until the list is sorted. The largest element
"bubbles" to the top in the first pass.

• Time Complexity: O(n²)

4.2 Selection Sort

Sorts an array by repeatedly finding the minimum element from the unsorted part and putting it
at the beginning. It maintains two subarrays: the sorted subarray and the remaining unsorted
subarray.

• Time Complexity: O(n²)

4.3 Insertion Sort

Builds the final sorted array one item at a time. It iterates, consuming one input element each
repetition, and grows a sorted output list by inserting the element into its correct position.

• Time Complexity: O(n²) (Best case O(n) if already sorted)

Algorithm analysis is evaluating the performance of an algorithm based on input size n.

• Time Complexity: The amount of time an algorithm takes to run as a function of the length
of the input. Represented using Big-O notation (e.g., O(n), O(n²)), which describes the upper
bound or worst-case scenario.

• Space Complexity: The amount of memory space required by the algorithm during its
execution. It includes both the auxiliary space (extra space or temporary variables used) and
space used by the input.

Unit 6: Multidimensional Array & Sparse Matrix

6.1 Multidimensional Array - Memory Representations

A 2D array is logically viewed as a table of rows and columns, but in memory, it is stored linearly
in 1D contiguous blocks. There are two major ways to map 2D coordinates to 1D addresses:

Row-Major Order: Elements of the first row are stored sequentially, followed by the second
row, etc.
Address(A[i][j]) = Base + ((i × number_of_columns) + j) × size

Column-Major Order: Elements of the first column are stored sequentially, followed by the
second column, etc.
Address(A[i][j]) = Base + ((j × number_of_rows) + i) × size

6.2 Sparse Matrix

A sparse matrix is a matrix in which the majority of the elements are zero. Using a standard 2D
array to store a sparse matrix is inefficient in terms of memory. Instead, we use alternative
representations to only store the non-zero elements.

Array Representation (Triplet form): A 2D array is used where each row has three columns:
Row, Column, and Value. The first row usually stores the total rows, total columns, and total non-
zero elements of the original matrix.

Row Index Col Index Value

(Total Rows) (Total Cols) (Total Non-Zeros)

i j Non-zero value