Data Structures – 3rd Semester – Complete
Detailed Material
Introduction to Data Structures
What is a Data Structure?
A data structure is a way of organizing, managing, and storing data in a computer so that it can
be accessed and modified efficiently. It is not just about storing data, but also about defining the
relationship between data and the operations we can perform.
Why Data Structures are Important:
1. Efficiency: Helps in optimizing time and space for data operations.
2. Reusability: Many data structures can be reused in different programs.
3. Scalability: Allows handling large amounts of data effectively.
4. Foundation for Algorithms: Efficient algorithms require proper data structures.
Example Analogy:
Think of a library: books can be arranged sequentially (like arrays) or in sections with
links (like linked lists). The way you organize books determines how fast you can find a
book.
Difference Between Data Structure and Abstract Data Type (ADT)
Feature Data Structure ADT
Definition Physical implementation of data Logical description of operations
Example Array, Linked List Stack, Queue
Focus How data is stored What operations are performed
Implementation Must exist in a programming language Independent of programming language
Explanation:
Data Structure: How the memory is arranged, e.g., an array in C++ is implemented as
contiguous memory.
ADT: Defines the behavior, e.g., a Stack allows Push/Pop operations, regardless of
whether it’s implemented as an array or linked list.
Linear and Nonlinear Data Structures
Linear Data Structures:
Elements arranged sequentially.
Examples: Array, Linked List, Stack, Queue
Traversal: One element after another.
Memory Allocation: Sequential in static array, dynamic in linked list.
Nonlinear Data Structures:
Elements have hierarchical or interconnected relationships.
Examples: Trees, Graphs
Traversal: Requires algorithms like DFS or BFS.
Memory Allocation: Dynamic and scattered.
Elementary Knowledge of Asymptotic Behavior
Asymptotic analysis measures the efficiency of an algorithm as the input size grows.
Big O Notation (O(f(n))): Upper bound (worst-case scenario)
Big Ω Notation (Ω(f(n))): Lower bound (best-case scenario)
Big Θ Notation (Θ(f(n))): Tight bound (average case)
Example:
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
sum += arr[i][j]; // Time complexity: O(n^2)
Time Complexity
Definition: Number of primitive operations executed as a function of input size.
For Selection Statements: O(1)
For Loops:
Single loop: O(n)
Nested loops: O(n^2)
Example:
for(int i=0; i<n; i++) // O(n)
for(int j=0; j<n; j++) // O(n^2)
sum += arr[i][j];
Space Complexity
Definition: Amount of memory required for an algorithm.
Includes variables, arrays, recursion stack, etc.
Example: For 2D array arr[n][m], space complexity = O(n*m)
Object-Oriented Concepts for Data Structures
Class, Object, Structure, Data Members, Functions
Class: Blueprint for creating objects.
Object: Instance of a class.
Structure: Collection of variables grouped together.
Data Members: Variables in a class.
Functions/Methods: Actions performed by objects.
Example in C++:
class Student {
public:
string name;
int rollNo;
void display() {
cout << "Name: " << name << ", Roll No: " << rollNo << endl;
}
};
Functions: Call by Value and Call by Reference
Call by Value: Passes a copy; original data remains unchanged.
Call by Reference: Passes memory address; original data can be modified.
Example:
void increment(int &x) { x++; } // Call by reference
Inter-class Communication
Objects of one class can be used in another.
Example:
class A { public: int x; };
class B { A objA; };
Operator and Function Overloading
Operator Overloading: Redefine operator for user-defined types.
Function Overloading: Same function name, different parameters.
Friend Function and Class
Friend Function: Access private/protected members.
Friend Class: All functions of a friend class can access private/protected members.
Static Functions and Classes
Static Function: Belongs to class, not object.
Static Class Members: Shared across all objects.
Inheritance
Derive a new class from an existing class.
Types: Single, Multiple, Multilevel, Hierarchical.
Virtual Functions: Runtime polymorphism.
Pure Virtual Function: Forces derived classes to implement the function.
Arrays
Static vs Dynamic Array
Static Array: Fixed size; memory allocated at compile-time.
Dynamic Array: Resizable; memory allocated at runtime using pointers.
Object Array
Array storing objects of a class.
Student s[10];
Pointer to Arrays
Traversal using pointers.
int arr[5] = {1,2,3,4,5};
int *ptr = arr;
for(int i=0;i<5;i++) cout << *(ptr+i);
Passing Array by Reference
Saves memory, allows modification of original data.
Printing Array
Using loops or pointers.
Declaration, Insertion, Deletion
Insertion: Shift elements, add new element.
Deletion: Shift elements, remove element.
Resizing Array
Increasing/decreasing size dynamically using new/delete in C++.
Searching Substring
Traverse and match sequence in character arrays.
Recursion
Function calls itself until base condition.
Example: Factorial
int factorial(int n) {
if(n==0) return 1;
return n*factorial(n-1);
}
Sorting Algorithms
Algorithm Time Complexity Space Complexity Notes
Insertion Sort O(n^2) O(1) Good for small arrays
Selection Sort O(n^2) O(1) Select min each iteration
Bubble Sort O(n^2) O(1) Swap adjacent elements
Merge Sort O(n log n) O(n) Divide and conquer
Quick Sort O(n log n) avg, O(n^2) worst O(log n) Partition based
Example of Insertion Sort in C++:
void insertionSort(int arr[], int n){
for(int i=1;i<n;i++){
int key=arr[i];
int j=i-1;
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
Linked Lists
Concept
Collection of nodes, each containing data and pointer.
Node Structure:
struct Node {
int data;
Node* next;
};
Operations
Insertion:
At head: O(1)
At tail: O(n)
Middle: O(n)
Traversal:
Follow next pointer from head to NULL.
Deletion:
First node: update head pointer
Last node: traverse to second last node, set next=NULL
Middle: update previous node’s next pointer
Searching:
Traverse and compare data.
Sorting Linked List:
Insertion sort or merge sort.
Complexity: O(n^2) for insertion, O(n log n) for merge.