Centre for Distance and Online Education
Online MCA Program
Semester- I
(Data Structures & Algorithms)
ASSIGNMENT
Prepared by
Yash Dadasaheb Chandanshive
Enrollment no: 2501J00600172
CDOE, PARUL UNIVERSITY 1
PART 1: THEORY QUESTIONS
1. What is data Structure? Explain the Classification of Data Structure in detail.
What is a Data Structure?
A Data Structure is a systematic way of organizing, managing, and storing data in a
computer so that it can be used and processed efficiently. It defines the relationship
between the data, the functions that operate on the data, and the logical way the data
elements are arranged. The choice of a data structure is crucial as it affects the
efficiency of algorithms that process the data.
Classification of Data Structure
Data structures are primarily classified into two types: Primitive and Non-Primitive.
The Non-Primitive structures are further divided into Linear and Non-Linear.
1. Primitive Data Structures
These are the fundamental data types directly operated upon by machine-level
instructions. They serve as the building blocks for non-primitive structures.
● Examples: int, float, char, double, and pointer.
2. Non-Primitive Data Structures
These are more complex structures derived from primitive data structures. They focus on
grouping data elements to represent real-world entities.
A. Linear Data Structures
In linear data structures, elements are arranged in a sequential or linear order. Each
element has a unique predecessor and successor (except the first and last).
● Arrays: A collection of fixed-size, same-type data elements stored in contiguous
CDOE, PARUL UNIVERSITY 2
memory locations. Access is efficient using an index.
● Linked Lists: A collection of nodes, where each node contains data and a pointer
(link) to the next node in the sequence. Memory allocation is dynamic.
● Stacks: A Last-In, First-Out (LIFO) structure , meaning the last element inserted
is the first one to be removed. Used in function calls and expression evaluation.
● Queues: A First-In, First-Out (FIFO) structure , where the element that has been
in the queue the longest is processed first. Used in job scheduling and
buffering.
B. Non-Linear Data Structures
In non-linear data structures, elements are not arranged sequentially. An element can
be connected to multiple elements, reflecting hierarchical or complex relationships.
● Trees: A collection of nodes starting with a root node, where each node has zero
or more child nodes. Used for representing hierarchical data, searching, and
sorting.
● Graphs: A collection of vertices (nodes) and edges (links) that connect the
vertices. Used for modeling real-world networks like road maps or social
connections.
2. Explain the Types of an Array. Write down syntax for declaration, initialization and
how to access elements from Array in C.
Types of an Array
An Array is a linear data structure that stores a collection of elements of the same
data type in contiguous memory locations. They are categorized based on their
dimensions:
1. One-Dimensional Array (1D Array):
○ This is the simplest type of array where data elements are organized
linearly, like a list or a row.
CDOE, PARUL UNIVERSITY 3
○ It uses a single index (subscript) to access its elements.
○ Example: Storing a list of student marks.
2. Multi-Dimensional Array:
○ Arrays that have more than one dimension. The most common is the Two-
Dimensional Array.
○ Two-Dimensional Array (2D Array): Organized like a matrix or a table, with
rows and columns. It requires two indices to access an element: one for the
row and one for the column.
○ Example: Storing data in a spreadsheet format or representing a chess
board.
Syntax in C
Operation Syntax Explanation
Declaration (1D data_type array_name[size]; Reserves memory for the
Array) array.
Initialization (1D int marks[5] = {80, 75, 90, 60, 85}; Assigns initial values during
Array) declaration.
Declaration (2D data_type array_name[row_size] Declares a matrix-like
Array) [col_size]; structure.
Initialization (2D int matrix[2][3] = {{1, 2, 3}, {4, 5, Initializes a 2x3 matrix.
Array) 6}};
Export to Sheets
Accessing Elements
Array elements are accessed using the array name followed by the index (or indices)
enclosed in square brackets []. Array indexing always starts from 0.
CDOE, PARUL UNIVERSITY 4
#include <stdio.h>
int main() {
// Declaration and Initialization
int numbers[5] = {10, 20, 30, 40, 50};
// Accessing an element
printf("The element at index 2 is: %d\n", numbers[2]); // Output: 30
// Modifying an element
numbers[0] = 100;
printf("The element at index 0 is now: %d\n", numbers[0]); // Output: 100
return 0;
3. What is stack? Explain the working of PUSH and POP operations in the stack with
examples.
What is a Stack?
A Stack is a linear data structure that follows the Last-In, First-Out (LIFO)
principle. This means the element inserted most recently is the first one to be
removed.
A stack has only two primary operations: PUSH (to insert an element) and POP (to remove
an element). All operations are performed at one end, called the Top of the stack.
CDOE, PARUL UNIVERSITY 5
Working of PUSH and POP Operations
1. PUSH Operation (Insertion)
The PUSH operation adds a new element to the top of the stack.
● Steps:
○ Check if the stack is full (Stack Overflow condition).
○ If not full, increment the TOP pointer to the next available location.
○ Place the new item at the location pointed to by TOP.
● Example:
○ Initial Stack: [10, 20] (TOP points to 20)
○ PUSH(30): TOP moves up. 30 is added to the new TOP position.
○ Resulting Stack: [10, 20, 30] (TOP points to 30)
2. POP Operation (Deletion)
The POP operation removes the element that is currently at the top of the stack.
● Steps:
○ Check if the stack is empty (Stack Underflow condition).
○ If not empty, retrieve the item pointed to by TOP.
○ Decrement the TOP pointer to move to the previous element.
○ Return the retrieved item.
● Example:
○ Initial Stack: [10, 20, 30] (TOP points to 30)
○ POP(): Item 30 is retrieved. TOP moves down.
○ Resulting Stack: [10, 20] (TOP points to 20)
4. Give the difference between Simple Queue V/S Circular Queue.
A Queue is a linear data structure that follows the First-In, First-Out (FIFO)
principle, where insertion (Enqueue) occurs at the Rear and deletion (Dequeue) occurs
CDOE, PARUL UNIVERSITY 6
at the Front.
The primary difference between a Simple Queue and a Circular Queue lies in how they
manage the rear of the array when a deletion occurs.
Feature Simple Queue Circular Queue
Structure Linear array implementation where elements The array is treated as a
move from Front to Rear. ring or circle; the last
element is followed by the
first element.
Space Inefficient. After several Dequeue Efficient. The empty space
Utilization operations, the front part of the array at the front of the queue is
becomes empty, but this space cannot be reused. The Rear pointer
reused unless the entire queue is shifted wraps around to the
(which is costly). This leads to a "Queue beginning of the array.
Full" error even if there are empty slots at
the front.
Full REAR == MAX_SIZE - 1 (REAR + 1) % MAX_SIZE ==
Condition FRONT
Working Dequeue moves the FRONT pointer forward. When Both FRONT and REAR pointers
Principle the REAR reaches the end, no more elements move in a circular manner.
can be inserted. The modulo operator % is
used to wrap the index
around.
Complexity Simple implementation. More complex implementation
due to the wrapping
condition.
Export to Sheets
5. How do singly and doubly linked lists differ from each other? Explain with Proper
Example.
A Linked List is a linear collection of data elements called nodes, where each node
CDOE, PARUL UNIVERSITY 7
contains data and a pointer (or link) to the next node. The primary difference between
singly and doubly linked lists is the direction of traversal and the number of pointers
in each node.
Differences
Feature Singly Linked List (SLL) Doubly Linked List (DLL)
Pointers per Node One pointer: next. Two pointers: next and prev (or
back).
Traversal Unidirectional. Can only traverse Bidirectional. Can traverse both
forward (from Head to Tail). forward and backward.
Memory Less memory required per node. More memory required per node to
store the extra prev pointer.
Insertion/Deletion Deleting a specific node requires Deletion of a specific node (if
traversing from the beginning to the node address is known) is
find the previous node. Time faster (O(1)) because the prev
complexity is O(n) in the worst and next nodes are immediately
case. accessible.
Export to Sheets
Example (Node Structure)
Singly Linked List Node
struct Node {
int data; // Data part
struct Node *next; // Pointer to the next node
};
CDOE, PARUL UNIVERSITY 8
Analogy: A chain of cars where each car only has a tow hook at the back, allowing it to
pull the next car but not be pushed back by it.
Doubly Linked List Node
struct Node {
int data; // Data part
struct Node *prev; // Pointer to the previous node
struct Node *next; // Pointer to the next node
};
Analogy: A train car with couplers on both the front and back, allowing the train to
move and be manipulated from either end.
PART 2: PRACTICAL PROBLEMS
For this section, copy the code provided into separate C/Java files. You must compile
and execute the code. Include a screenshot of the command line output for each problem
in your submission.
1. Write a Program to Perform Tower of Hanoi Problem.
Program: TowerOfHanoi.c (C Program)
#include <stdio.h>
// Function to solve Tower of Hanoi problem
CDOE, PARUL UNIVERSITY 9
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
printf("\nMove disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
// Move n-1 disks from source to auxiliary rod
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
// Move the largest disk n from source to destination rod
printf("\nMove disk %d from rod %c to rod %c", n, from_rod, to_rod);
// Move the n-1 disks from auxiliary rod to destination rod
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
int main() {
int n = 3; // Number of disks
printf("--- Tower of Hanoi with %d Disks ---\n", n);
// A: Source, C: Destination, B: Auxiliary
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
2. Write a Program to calculate the sum of the first N natural numbers using Recursive
CDOE, PARUL UNIVERSITY 10
function.
Program: SumOfNRecursive.c (C Program)
#include <stdio.h>
// Recursive function to calculate sum
int sum(int n) {
if (n == 0) {
return 0;
// Recursive step: n + sum of (n-1) numbers
return n + sum(n - 1);
int main() {
int N = 10;
int result = sum(N);
printf("--- Recursive Sum of First N Natural Numbers ---\n");
printf("The sum of the first %d natural numbers is: %d\n", N, result);
N = 5;
result = sum(N);
printf("The sum of the first %d natural numbers is: %d\n", N, result);
CDOE, PARUL UNIVERSITY 11
return 0;
3. Write a program to implement Insertion (Push) & deletion (Pop) operation using
linked list in c.
Program: StackLinkedList.c (C Program implementing a Stack using a Linked List)
#include <stdio.h>
#include <stdlib.h>
// Node structure for the linked list
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL; // Global pointer for the top of the stack
// PUSH operation (Insertion at the beginning of the list)
void push(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
CDOE, PARUL UNIVERSITY 12
printf("\nStack Overflow (Memory allocation failed)");
return;
newNode->data = val;
newNode->next = top; // New node points to the current top
top = newNode; // Top now points to the new node
printf("Pushed: %d\n", val);
// POP operation (Deletion from the beginning of the list)
void pop() {
if (top == NULL) {
printf("\nStack Underflow (Stack is empty)");
return;
struct Node* temp = top;
printf("Popped: %d\n", temp->data);
top = top->next; // Move top to the next node
free(temp); // Free the memory of the popped node
int main() {
printf("--- Stack Operations (Linked List Implementation) ---\n");
push(10);
CDOE, PARUL UNIVERSITY 13
push(20);
push(30);
pop(); // Popped: 30
pop(); // Popped: 20
pop(); // Popped: 10
pop(); // Stack Underflow check
return 0;
4. Write a C Program to Implement a queue using array.
Program: QueueArray.c (C Program)
#include <stdio.h>
#define MAX_SIZE 5
int queue[MAX_SIZE];
int front = -1, rear = -1;
// ENQUEUE operation (Insertion)
CDOE, PARUL UNIVERSITY 14
void enqueue(int data) {
if (rear == MAX_SIZE - 1) {
printf("Queue Overflow (Queue is full)\n");
return;
if (front == -1) {
front = 0; // Initialize front for the first element
rear++;
queue[rear] = data;
printf("Enqueued: %d\n", data);
// DEQUEUE operation (Deletion)
void dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow (Queue is empty)\n");
return;
printf("Dequeued: %d\n", queue[front]);
front++;
// Optional: Reset queue if it becomes empty
if (front > rear) {
front = rear = -1;
CDOE, PARUL UNIVERSITY 15
}
int main() {
printf("--- Queue Operations (Array Implementation) ---\n");
enqueue(1);
enqueue(2);
enqueue(3);
enqueue(4);
enqueue(5);
enqueue(6); // Overflow check
dequeue(); // Dequeued: 1
dequeue(); // Dequeued: 2
enqueue(7); // Can insert again (Simple Queue limitation on space reuse)
dequeue(); // Dequeued: 3
dequeue(); // Dequeued: 4
dequeue(); // Dequeued: 5
dequeue(); // Dequeued: 7
dequeue(); // Underflow check
CDOE, PARUL UNIVERSITY 16
return 0;
5. Write a program to implement Singly Linked List.
Program: SinglyLinkedList.c (C Program)
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node *next;
};
// Global head pointer
struct Node *head = NULL;
// Function to insert a new node at the beginning
void insertAtBeginning(int data) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
CDOE, PARUL UNIVERSITY 17
return;
newNode->data = data;
newNode->next = head; // New node points to the current head
head = newNode; // Head now points to the new node
// Function to display the linked list
void displayList() {
struct Node *current = head;
printf("Linked List: ");
if (head == NULL) {
printf("The list is empty.\n");
return;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
printf("NULL\n");
int main() {
printf("--- Singly Linked List Implementation ---\n");
CDOE, PARUL UNIVERSITY 18
// Insert elements
insertAtBeginning(30);
insertAtBeginning(20);
insertAtBeginning(10);
// List: 10 -> 20 -> 30 -> NULL
displayList();
insertAtBeginning(40);
// List: 40 -> 10 -> 20 -> 30 -> NULL
displayList();
// Free allocated memory before exiting (good practice)
struct Node *temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
return 0;
CDOE, PARUL UNIVERSITY 19
CDOE, PARUL UNIVERSITY 20