DS LAB MANUAL (PITW ) NIHAZRAHIM

List of Experiments:

Exercise 1: Array Manipulation

i) Write a program to reverse an array.

ii) C Programs to implement the Searching Techniques – Linear & Binary Search

iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort

Exercise 2: Linked List Implementation

i) Implement a singly linked list and perform insertion and deletion operations.

ii) Develop a program to reverse a linked list iteratively and recursively.

iii) Solve problems involving linked list traversal and manipulation.

Exercise 3: Linked List Applications

i) Create a program to detect and remove duplicates from a linked list.

ii) Implement a linked list to represent polynomials and perform addition.

iii) Implement a double-ended queue (deque) with essential operations.

Exercise 4: Double Linked List Implementation

i) Implement a doubly linked list and perform various operations to understand its

properties and applications.

ii) Implement a circular linked list and perform insertion, deletion, and traversal.

Exercise 5: Stack Operations

i) Implement a stack using arrays and linked lists.

ii) Write a program to evaluate a postfix expression using a stack.

iii) Implement a program to check for balanced parentheses using a stack.

Exercise 6: Queue Operations

i) Implement a queue using arrays and linked lists.

ii) Develop a program to simulate a simple printer queue system.

iii) Solve problems involving circular queues.

Exercise 7: Stack and Queue Applications

i) Use a stack to evaluate an infix expression and convert it to postfix.

 DS LAB MANUAL (PITW ) NIHAZRAHIM

ii) Create a program to determine whether a given string is a palindrome or not.

iii) Implement a stack or queue to perform comparison and check for symmetry.

Exercise 8: Binary Search Tree

i) Implementing a BST using Linked List.

ii) Traversing of BST.

Exercise 9: Hashing

i) Implement a hash table with collision resolution techniques.

ii) Write a program to implement a simple cache using hashing

i) Write a program to reverse an array.

#include <stdio.h>

#define MAX_SIZE 100

int main()

int arr[MAX_SIZE];

int i, j, size, temp;

/* Input size of array */

printf("Enter size of array: ");

scanf("%d", &size);

/* Input elements in array */

printf("Enter elements in array: ");

for(i=0; i<size; i++)

scanf("%d", &arr[i]);

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

j = i - 1; /* now j will point to the last element */

i = 0; /* and i will be point to the first element */

while(i<j)

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++; /* increment i */

j--; /* decrement j */

/* Print reversed array */

printf("\nReversed array is: ");

for(i=0; i<size; i++)

printf("%d ", arr[i]);

return 0;

ii) C Programs to implement the Searching Techniques – Linear & Binary Search

Linear Search:

#include <stdio.h>

int main()

int arr[10], i, num, flag=0;

 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("\nEnter 10 elements in the array:\n");

for(i=0; i<10; i++)

scanf("%d", &arr[i]);

printf("\nEnter element to search:");

scanf("%d", &num);

for(i=0; i<10; i++)

if(arr[i] == num)

flag = 1;

printf("\n%d is found at position %d", num, i+1);

break;

if(flag == 0)

printf("\n%d not found", num);

return 0;

Binary Search:

#include <stdio.h>

int main()

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int arr[10], i, num, first, last, middle, flag=0;

printf("\nEnter 10 elements in the array:\n");

for(i=0; i<10; i++)

scanf("%d", &arr[i]);

printf("\nEnter element to search:");

scanf("%d", &num);

first = 0;

last = 9;

while(first <= last)

middle = (first + last)/2;

if(arr[middle] == num)

flag = 1;

printf("\n%d is found at position %d", num, middle+1);

break;

else if(arr[middle] < num)

first = middle + 1;

else

last = middle - 1;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(flag == 0)

printf("\n%d not found", num);

return 0;

iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort

Bubble Sort:

#include<stdio.h>

int main()

int arr[10], i, j, temp;

printf("Enter 10 elements in the array:\n");

for(i=0; i<10; i++)

scanf("%d", &arr[i]);

for(i=0; i<9; i++)

for(j=0; j<9-i; j++)

if(arr[j]>arr[j+1])

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("\nSorted array in ascending order:\n");

for(i=0; i<10; i++)

printf("%d ", arr[i]);

return 0;

Selection Sort:

#include<stdio.h>

int main()

int arr[10], i, j, min, temp;

printf("Enter 10 elements in the array:\n");

for(i=0; i<10; i++)

scanf("%d", &arr[i]);

for(i=0; i<9; i++)

min = i;

for(j=i+1; j<10; j++)

if(arr[j]<arr[min])
 DS LAB MANUAL (PITW ) NIHAZRAHIM

min = j;

temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

printf("\nSorted array in ascending order:\n");

for(i=0; i<10; i++)

printf("%d ", arr[i]);

return 0;

Insertion Sort:

#include<stdio.h>

int main()

int arr[10], i, j, temp;

printf("Enter 10 elements in the array:\n");

for(i=0; i<10; i++)

scanf("%d", &arr[i]);

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

for(i=1; i<10; i++)

temp = arr[i];

j = i-1;

while(temp<arr[j] && j>=0)

arr[j+1] = arr[j];

j--;

arr[j+1] = temp;

printf("\nSorted array in ascending order:\n");

for(i=0; i<10; i++)

printf("%d ", arr[i]);

return 0;

Exercise 2: Linked List Implementation

i) Implement a singly linked list and perform insertion and deletion operations.

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *next;

};
 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node *start = NULL;

struct node* createNode(int);

void insertNode();

void deleteNode();

void displayList();

int main()

int choice;

while(1)

printf("\n--- Singly Linked List Operations ---\n");

printf("1. Insert Node\n");

printf("2. Delete Node\n");

printf("3. Display List\n");

printf("4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch(choice)

case 1:

insertNode();

break;

case 2:

deleteNode();

break;

case 3:
 DS LAB MANUAL (PITW ) NIHAZRAHIM

displayList();

break;

case 4:

exit(0);

default:

printf("Invalid choice, please try again.\n");

break;

return 0;

struct node* createNode(int data)

struct node *newNode = (struct node*)malloc(sizeof(struct node));

newNode->data = data;

newNode->next = NULL;

return newNode;

void insertNode()

int data;

printf("Enter data to insert: ");

scanf("%d", &data);

struct node *newNode = createNode(data);

if(start == NULL)

start = newNode;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

else

struct node *temp = start;

while(temp->next != NULL)

temp = temp->next;

temp->next = newNode;

printf("Node inserted successfully.\n");

void deleteNode()

int data;

printf("Enter data to delete: ");

scanf("%d", &data);

struct node *temp = start, *prev = NULL;

if(temp != NULL && temp->data == data)

start = temp->next;

free(temp);

printf("Node deleted successfully.\n");

return;

while(temp != NULL && temp->data != data)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

prev = temp;

temp = temp->next;

if(temp == NULL)

printf("Node not found.\n");

return;

prev->next = temp->next;

free(temp);

printf("Node deleted successfully.\n");

void displayList()

if(start == NULL)

printf("List is empty.\n");

return;

printf("--- List elements ---\n");

struct node *temp = start;

while(temp != NULL)

printf("%d -> ", temp->data);

temp = temp->next;

printf("\n");
 DS LAB MANUAL (PITW ) NIHAZRAHIM

ii) Develop a program to reverse a linked list iteratively and recursively.

Iterative Approach:

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *next;

};

struct node *start = NULL;

struct node* createNode(int);

void insertNode(int);

void reverseListIteratively();

void displayList();

int main()

insertNode(10);

insertNode(20);

insertNode(30);

insertNode(40);

insertNode(50);

printf("Original list:\n");

displayList();

reverseListIteratively();

printf("Reversed list:\n");

displayList();
 DS LAB MANUAL (PITW ) NIHAZRAHIM

return 0;

struct node* createNode(int data)

struct node *newNode = (struct node*)malloc(sizeof(struct node));

newNode->data = data;

newNode->next = NULL;

return newNode;

void insertNode(int data)

struct node *newNode = createNode(data);

if(start == NULL)

start = newNode;

else

struct node *temp = start;

while(temp->next != NULL)

temp = temp->next;

temp->next = newNode;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

void reverseListIteratively()

struct node *prevNode = NULL, *currentNode = start, *nextNode = NULL;

while(currentNode != NULL)

nextNode = currentNode->next;

currentNode->next = prevNode;

prevNode = currentNode;

currentNode = nextNode;

start = prevNode;

void displayList()

if(start == NULL)

printf("List is empty.\n");

return;

struct node *temp = start;

while(temp != NULL)

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");
 DS LAB MANUAL (PITW ) NIHAZRAHIM

Recursive Approach:

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *next;

};

struct node *start = NULL;

struct node* createNode(int);

void insertNode(int);

struct node* reverseListRecursively(struct node*);

void displayList();

int main()

insertNode(10);

insertNode(20);

insertNode(30);

insertNode(40);

insertNode(50);

printf("Original list:\n");

displayList();

start = reverseListRecursively(start);

printf("Reversed list:\n");

displayList();
 DS LAB MANUAL (PITW ) NIHAZRAHIM

return 0;

struct node* createNode(int data)

struct node *newNode = (struct node*)malloc(sizeof(struct node));

newNode->data = data;

newNode->next = NULL;

return newNode;

void insertNode(int data)

struct node *newNode = createNode(data);

if(start == NULL)

start = newNode;

else

struct node *temp = start;

while(temp->next != NULL)

temp = temp->next;

temp->next = newNode;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node* reverseListRecursively(struct node *currentNode)

if(currentNode == NULL || currentNode->next == NULL)

return currentNode;

struct node *nextNode = currentNode->next;

currentNode->next = NULL;

struct node *reverseRest = reverseListRecursively(nextNode);

nextNode->next = currentNode;

return reverseRest;

void displayList()

if(start == NULL)

printf("List is empty.\n");

return;

struct node *temp = start;

while(temp != NULL)

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");
 DS LAB MANUAL (PITW ) NIHAZRAHIM

iii) Solve problems involving linked list traversal and manipulation.

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *next;

};

void insert(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = NULL;

if(*head == NULL)

*head = new_node;

else

struct node *temp = *head;

while(temp->next != NULL)

temp = temp->next;

temp->next = new_node;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

void insertAtPosition(struct node **head, int data, int position)

if(position < 1)

printf("Invalid position.\n");

return;

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = NULL;

if(position == 1)

new_node->next = *head;

*head = new_node;

else

struct node *prev_node = *head;

for(int i=2; i<position; i++)

if(prev_node == NULL)

printf("Invalid position.\n");

return;

prev_node = prev_node->next;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(prev_node == NULL)

printf("Invalid position.\n");

return;

new_node->next = prev_node->next;

prev_node->next = new_node;

void delete(struct node **head, int data)

struct node *temp = *head, *prev;

if(temp != NULL && temp->data == data)

*head = temp->next;

free(temp);

return;

while(temp != NULL && temp->data != data)

prev = temp;

temp = temp->next;

if(temp == NULL)

printf("Data not found.\n");

 DS LAB MANUAL (PITW ) NIHAZRAHIM

return;

prev->next = temp->next;

free(temp);

void display(struct node *head)

struct node *temp = head;

while(temp != NULL)

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");

int main()

struct node *head = NULL;

insert(&head, 10);

insert(&head, 20);

insert(&head, 30);

display(head);

delete(&head, 20);

display(head);

insertAtPosition(&head, 40, 2);

insertAtPosition(&head, 50, 5);

display(head);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

return 0;

Exercise 3: Linked List Applications

i) Create a program to detect and remove duplicates from a linked list.

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *next;

};

void insert(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = NULL;

if(*head == NULL)

*head = new_node;

else

struct node *temp = *head;

while(temp->next != NULL)

temp = temp->next;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

temp->next = new_node;

void removeDuplicates(struct node *head)

struct node *current_node = head, *delete_node;

if(current_node == NULL)

return;

while(current_node->next != NULL)

if(current_node->data == current_node->next->data)

delete_node = current_node->next;

current_node->next = delete_node->next;

free(delete_node);

else

current_node = current_node->next;

void display(struct node *head)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node *temp = head;

while(temp != NULL)

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");

int main()

struct node *head = NULL;

insert(&head, 10);

insert(&head, 20);

insert(&head, 20);

insert(&head, 30);

insert(&head, 30);

insert(&head, 30);

insert(&head, 40);

display(head);

removeDuplicates(head);

display(head);

return 0;

ii) Implement a linked list to represent polynomials and perform addition.

#include <stdio.h>

#include <stdlib.h>

struct node
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int coefficient;

int exponent;

struct node *next;

};

void insert(struct node **head, int coefficient, int exponent)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->coefficient = coefficient;

new_node->exponent = exponent;

new_node->next = NULL;

if(*head == NULL)

*head = new_node;

else

struct node *temp = *head;

while(temp->next != NULL)

temp = temp->next;

temp->next = new_node;

void addPolynomials(struct node *poly1, struct node *poly2, struct node **result)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

while(poly1 != NULL && poly2 != NULL)

if(poly1->exponent > poly2->exponent)

insert(result, poly1->coefficient, poly1->exponent);

poly1 = poly1->next;

else if(poly2->exponent > poly1->exponent)

insert(result, poly2->coefficient, poly2->exponent);

poly2 = poly2->next;

else

insert(result, poly1->coefficient + poly2->coefficient, poly1->exponent);

poly1 = poly1->next;

poly2 = poly2->next;

while(poly1 != NULL)

insert(result, poly1->coefficient, poly1->exponent);

poly1 = poly1->next;

while(poly2 != NULL)

insert(result, poly2->coefficient, poly2->exponent);

 DS LAB MANUAL (PITW ) NIHAZRAHIM

poly2 = poly2->next;

void display(struct node *poly)

while(poly != NULL)

printf("%dX^%d", poly->coefficient, poly->exponent);

poly = poly->next;

if(poly != NULL)

printf(" + ");

printf("\n");

int main()

struct node *poly1 = NULL;

struct node *poly2 = NULL;

struct node *result = NULL;

insert(&poly1, 5, 2);

insert(&poly1, -2, 1);

insert(&poly1, 3, 0);

printf("Polynomial 1: ");

display(poly1);

insert(&poly2, 3, 2);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

insert(&poly2, -3, 0);

printf("Polynomial 2: ");

display(poly2);

addPolynomials(poly1, poly2, &result);

printf("Result: ");

display(result);

return 0;

iii) Implement a double-ended queue (deque) with essential operations.

#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node *prev;

struct node *next;

};

void insert_front(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->prev = NULL;

if(*head == NULL)

new_node->next = NULL;

*head = new_node;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

else

new_node->next = *head;

(*head)->prev = new_node;

*head = new_node;

void insert_rear(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = NULL;

if(*head == NULL)

new_node->prev = NULL;

*head = new_node;

else

struct node *temp = *head;

while(temp->next != NULL)

temp = temp->next;

temp->next = new_node;

new_node->prev = temp;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

void delete_front(struct node **head)

if(*head == NULL)

printf("Deque is empty.\n");

return;

struct node *temp = *head;

*head = (*head)->next;

if(*head != NULL)

(*head)->prev = NULL;

free(temp);

void delete_rear(struct node **head)

if(*head == NULL)

printf("Deque is empty.\n");

return;

struct node *temp = *head;

while(temp->next != NULL)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

temp = temp->next;

if(temp->prev != NULL)

temp->prev->next = NULL;

else

*head = NULL;

free(temp);

void display(struct node *head)

if(head == NULL)

printf("Deque is empty.\n");

return;

printf("Deque: ");

while(head != NULL)

printf("%d ", head->data);

head = head->next;

printf("\n");

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int main()

struct node *deque = NULL;

insert_rear(&deque, 10);

insert_rear(&deque, 20);

insert_front(&deque, 30);

insert_front(&deque, 40);

display(deque);

delete_front(&deque);

delete_rear(&deque);

display(deque);

insert_rear(&deque, 50);

insert_front(&deque, 60);

display(deque);

delete_front(&deque);

delete_rear(&deque);

delete_front(&deque);

delete_rear(&deque);

display(deque);

return 0;

Exercise 4: Double Linked List Implementation

i) Implement a doubly linked list and perform various operations to understand its

properties and applications.

#include <stdio.h>

#include <stdlib.h>

struct node
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int data;

struct node *prev;

struct node *next;

};

void insert_at_front(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->prev = NULL;

if(*head == NULL)

new_node->next = NULL;

*head = new_node;

else

new_node->next = *head;

(*head)->prev = new_node;

*head = new_node;

void insert_at_end(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = NULL;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(*head == NULL)

new_node->prev = NULL;

*head = new_node;

else

struct node *temp = *head;

while(temp->next != NULL)

temp = temp->next;

temp->next = new_node;

new_node->prev = temp;

void insert_at_position(struct node **head, int data, int position)

if(position < 1)

printf("Invalid position.\n");

return;

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

if(position == 1)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

new_node->prev = NULL;

if(*head == NULL)

new_node->next = NULL;

else

new_node->next = *head;

(*head)->prev = new_node;

*head = new_node;

else

struct node *temp = *head;

int i = 1;

while(i < position - 1)

if(temp == NULL)

printf("Invalid position.\n");

return;

temp = temp->next;

i++;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

new_node->next = temp->next;

new_node->prev = temp;

if(temp->next != NULL)

temp->next->prev = new_node;

temp->next = new_node;

void delete_at_position(struct node **head, int position)

if(*head == NULL || position < 1)

printf("Invalid position.\n");

return;

struct node *temp = *head;

if(position == 1)

*head = (*head)->next;

if(*head != NULL)

(*head)->prev = NULL;

else

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int i = 1;

while(i < position)

if(temp == NULL)

printf("Invalid position.\n");

return;

temp = temp->next;

i++;

if(temp->prev != NULL)

temp->prev->next = temp->next;

else

*head = temp->next;

if(temp->next != NULL)

temp->next->prev = temp->prev;

free(temp);

void display_forward(struct node *head)

 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node *temp = head;

printf("Forward list: ");

while(temp != NULL)

printf("%d ", temp->data);

temp = temp->next;

printf("\n");

void display_reverse(struct node *head)

struct node *temp = head;

if(temp == NULL)

printf("Reverse list: NULL\n");

return;

while(temp->next != NULL)

temp = temp->next;

printf("Reverse list: ");

while(temp != NULL)

printf("%d ", temp->data);

temp = temp->prev;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("\n");

int main()

struct node *head = NULL;

insert_at_front(&head, 10);

insert_at_front(&head, 20);

insert_at_end(&head, 30);

insert_at_end(&head, 40);

display_forward(head);

display_reverse(head);

insert_at_position(&head, 50, 3);

insert_at_position(&head, 60, 6);

display_forward(head);

display_reverse(head);

delete_at_position(&head, 4);

delete_at_position(&head, 1);

delete_at_position(&head, 6);

display_forward(head);

display_reverse(head);

return 0;

ii) Implement a circular linked list and perform insertion, deletion, and traversal.

#include <stdio.h>

#include <stdlib.h>
 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node

int data;

struct node *next;

};

void insert_at_front(struct node **head, int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

if(*head == NULL)

new_node->next = new_node;

*head = new_node;

else

struct node *temp = *head;

while(temp->next != *head)

temp = temp->next;

temp->next = new_node;

new_node->next = *head;

*head = new_node;

void insert_at_end(struct node **head, int data)

 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

if(*head == NULL)

new_node->next = new_node;

*head = new_node;

else

struct node *temp = *head;

while(temp->next != *head)

temp = temp->next;

temp->next = new_node;

new_node->next = *head;

void delete_at_pos(struct node **head, int position)

if(*head == NULL)

return;

struct node *prev_node, *cur_node;

prev_node = (*head)->next;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(position == 1)

while(prev_node->next != *head)

prev_node = prev_node->next;

cur_node = *head;

*head = (*head)->next;

prev_node->next = *head;

free(cur_node);

else

int i = 1;

while(i < position - 1 && prev_node != NULL)

prev_node = prev_node->next;

i++;

if(prev_node != NULL && prev_node->next != *head)

cur_node = prev_node->next;

prev_node->next = cur_node->next;

free(cur_node);

else

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("Invalid position\n");

void display_list(struct node *head)

if(head == NULL)

printf("List is empty.\n");

else

struct node *temp = head;

printf("Circular Linked List: \n");

do

printf("%d ", temp->data);

temp = temp->next;

} while(temp != head);

printf("\n");

int main()

struct node *head = NULL;

insert_at_front(&head, 10);

insert_at_front(&head, 20);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

insert_at_end(&head, 30);

insert_at_end(&head, 40);

display_list(head);

delete_at_pos(&head, 3);

display_list(head);

delete_at_pos(&head, 1);

display_list(head);

delete_at_pos(&head, 4);

display_list(head);

return 0;

Exercise 5: Stack Operations

i) Implement a stack using arrays and linked lists.

Implementing a Stack using Arrays:

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

int stack[MAX_SIZE];

int top = -1;

void push(int data)

if(top == MAX_SIZE - 1)

printf("Stack overflow.\n");

return;

stack[++top] = data;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int pop()

if(top == -1)

printf("Stack underflow.\n");

return -1;

return stack[top--];

int peek()

if(top == -1)

printf("Stack is empty.\n");

return -1;

return stack[top];

void display()

if(top == -1)

printf("Stack is empty.\n");

else

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

for(int i = top; i >= 0; i--)

printf("%d ", stack[i]);

printf("\n");

int main()

push(10);

push(20);

display();

push(30);

push(40);

display();

int element = pop();

printf("Popped element: %d\n", element);

display();

element = peek();

printf("Peeked element: %d\n", element);

display();

return 0;

Implementing a Stack using Linked Lists:

#include <stdio.h>

#include <stdlib.h>

struct node
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int data;

struct node *next;

};

struct node *top = NULL;

void push(int data)

struct node *new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->next = top;

top = new_node;

int pop()

if(top == NULL)

printf("Stack is empty.\n");

return -1;

int data = top->data;

struct node *temp = top;

top = top->next;

free(temp);

return data;

int peek()

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(top == NULL)

printf("Stack is empty.\n");

return -1;

return top->data;

void display()

if(top == NULL)

printf("Stack is empty.\n");

else

struct node *temp = top;

while(temp != NULL)

printf("%d ", temp->data);

temp = temp->next;

printf("\n");

int main()

push(10);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

push(20);

display();

push(30);

push(40);

display();

int element = pop();

printf("Popped element: %d\n", element);

display();

element = peek();

printf("Peeked element: %d\n", element);

display();

return 0;

ii) Write a program to evaluate a postfix expression using a stack.

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#define MAX_SIZE 100

int stack[MAX_SIZE];

int top = -1;

void push(int data)

if(top == MAX_SIZE - 1)

printf("Stack overflow.\n");

return;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

stack[++top] = data;

int pop()

if(top == -1)

printf("Stack underflow.\n");

return -1;

return stack[top--];

int evaluate_postfix(char *expr)

int i, operand1, operand2;

char ch;

for(i = 0; expr[i] != '\0'; i++)

ch = expr[i];

if(isdigit(ch))

push(ch - '0');

else

operand2 = pop();

operand1 = pop();

switch(ch)
 DS LAB MANUAL (PITW ) NIHAZRAHIM

case '+':

push(operand1 + operand2);

break;

case '-':

push(operand1 - operand2);

break;

case '*':

push(operand1 * operand2);

break;

case '/':

push(operand1 / operand2);

break;

return pop();

int main()

char expr[MAX_SIZE];

printf("Enter postfix expression: ");

scanf("%s", expr);

int result = evaluate_postfix(expr);

printf("Result: %d\n", result);

return 0;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

iii) Implement a program to check for balanced parentheses using a stack.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_SIZE 100

char stack[MAX_SIZE];

int top = -1;

void push(char symbol)

if(top == MAX_SIZE - 1)

printf("Stack overflow.\n");

return;

stack[++top] = symbol;

char pop()

if(top == -1)

printf("Stack underflow.\n");

return -1;

return stack[top--];

bool is_balanced(char *expression)

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

for(int i = 0; expression[i] != '\0'; i++)

char symbol = expression[i];

if(symbol == '(' || symbol == '[' || symbol == '{')

push(symbol);

else if(symbol == ')' || symbol == ']' || symbol == '}')

if(top == -1)

return false;

char top_symbol = pop();

if((top_symbol == '(' && symbol != ')') || (top_symbol == '[' && symbol != ']') || (top_symbol
== '{' && symbol != '}'))

return false;

return top == -1;

int main()

char expression[MAX_SIZE];

printf("Enter an expression: ");

scanf("%s", expression);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

bool is_balanced_expression = is_balanced(expression);

if(is_balanced_expression)

printf("The expression is balanced.\n");

else

printf("The expression is not balanced.\n");

return 0;

Exercise 6: Queue Operations

i) Implement a queue using arrays and linked lists.

#include <stdio.h>

#include <stdbool.h>

#define MAX_SIZE 100

int queue[MAX_SIZE];

int front = -1, rear = -1;

bool is_empty()

return front == -1 && rear == -1;

bool is_full()

return rear == MAX_SIZE - 1;

void enqueue(int data)

 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(is_full())

printf("Queue overflow.\n");

return;

else if(is_empty())

front = rear = 0;

else

rear++;

queue[rear] = data;

int dequeue()

int data = -1;

if(is_empty())

printf("Queue underflow.\n");

else if(front == rear)

data = queue[front];

front = rear = -1;

 DS LAB MANUAL (PITW ) NIHAZRAHIM

else

data = queue[front];

front++;

return data;

void display()

if(is_empty())

printf("Queue is empty.\n");

return;

for(int i = front; i <= rear; i++)

printf("%d ", queue[i]);

printf("\n");

int main()

enqueue(10);

enqueue(20);

enqueue(30);

display();
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("Dequeued: %d\n", dequeue());

display();

enqueue(40);

enqueue(50);

display();

return 0;

Implementation of Queue using Linked Lists:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

typedef struct node

int data;

struct node *next;

} Node;

Node *front = NULL, *rear = NULL;

bool is_empty()

return front == NULL && rear == NULL;

void enqueue(int data)

Node *new_node = (Node*) malloc(sizeof(Node));

new_node->data = data;

new_node->next = NULL;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(is_empty())

front = rear = new_node;

else

rear->next = new_node;

rear = new_node;

int dequeue()

int data = -1;

if(is_empty())

printf("Queue underflow.\n");

else

data = front->data;

if(front == rear)

front = rear = NULL;

else

front = front->next;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

free(temp);

return data;

void display()

if(is_empty())

printf("Queue is empty.\n");

return;

Node *ptr = front;

while(ptr != NULL)

printf("%d ", ptr->data);

ptr = ptr->next;

printf("\n");

int main()

enqueue(10);

enqueue(20);

enqueue(30);

display();

printf("Dequeued: %d\n", dequeue());

 DS LAB MANUAL (PITW ) NIHAZRAHIM

display();

enqueue(40);

enqueue(50);

display();

return 0;

ii) Develop a program to simulate a simple printer queue system.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_JOBS 100

typedef struct job

int job_id;

int pages;

int priority;

struct job *next;

} Job;

Job *head = NULL, *tail = NULL;

bool is_empty()

return head == NULL;

void print_jobs()

if(is_empty())

{
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("No jobs in queue.\n");

return;

Job *temp = head;

while(temp != NULL)

printf("Job ID: %d, Pages: %d, Priority: %d\n", temp->job_id, temp->pages, temp->priority);

temp = temp->next;

void add_job()

if(MAX_JOBS <= 0)

printf("No space available in the queue.\n");

return;

int job_id, pages, priority;

printf("Enter Job ID: ");

scanf("%d", &job_id);

printf("Enter Pages to Print: ");

scanf("%d", &pages);

printf("Enter Priority (1- Low, 2- Medium, 3- High): ");

scanf("%d", &priority);

Job *new_job = (Job*) malloc(sizeof(Job));

new_job->job_id = job_id;

new_job->pages = pages;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

new_job->priority = priority;

new_job->next = NULL;

if(is_empty())

head = tail = new_job;

else

tail->next = new_job;

tail = new_job;

MAX_JOBS--;

printf("Job added successfully!\n");

void remove_job()

if(is_empty())

printf("No jobs in queue.\n");

return;

Job *temp = head;

head = head->next;

printf("Job ID: %d removed successfully!\n", temp->job_id);

free(temp);

int main()
 DS LAB MANUAL (PITW ) NIHAZRAHIM

int choice = 0;

while(true)

printf("\n----- Printer Queue System -----\n");

printf("1. Add Job\n");

printf("2. Remove Job\n");

printf("3. Print Jobs\n");

printf("4. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch(choice)

case 1:

add_job();

break;

case 2:

remove_job();

break;

case 3:

print_jobs();

break;

case 4:

exit(0);

default:

printf("Invalid choice!\n");

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

return 0;

iii) Solve problems involving circular queues.

#include <stdio.h>

#include <stdbool.h>

#define MAX_SIZE 5

int queue[MAX_SIZE];

int front = -1, rear = -1;

bool is_empty()

return front == -1;

bool is_full()

return (rear + 1) % MAX_SIZE == front;

void enqueue(int data)

if(is_full())

printf("Queue is full.\n");

return;

else if(is_empty())

front = rear = 0;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

else

rear = (rear + 1) % MAX_SIZE;

queue[rear] = data;

int dequeue()

int data = -1;

if(is_empty())

printf("Queue is empty.\n");

return data;

data = queue[front];

if(front == rear)

front = rear = -1;

else

front = (front + 1) % MAX_SIZE;

return data;

void display()
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if(is_empty())

printf("Queue is empty.\n");

return;

int i = front;

do

printf("%d ", queue[i]);

i = (i + 1) % MAX_SIZE;

} while(i != (rear + 1) % MAX_SIZE);

printf("\n");

int main()

enqueue(10);

enqueue(20);

enqueue(30);

enqueue(40);

enqueue(50);

enqueue(60); // will fail as the queue is full

display();

printf("Dequeued: %d\n", dequeue());

printf("Dequeued: %d\n", dequeue());

display();

return 0;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

Exercise 7: Stack and Queue Applications

i) Use a stack to evaluate an infix expression and convert it to postfix.

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#define MAX_SIZE 100

char stack[MAX_SIZE];

int top = -1;

int precedence(char operator)

if (operator == '(' || operator == ')')

return 0;

else if (operator == '+' || operator == '-')

return 1;

else if (operator == '*' || operator == '/')

return 2;

else if (operator == '^')

return 3;

else

return -1;

void push(char element)

if (top == MAX_SIZE - 1) {

printf("Stack overflow\n");

exit(1);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

stack[++top] = element;

char pop()

if (top == -1) {

printf("Stack underflow\n");

exit(1);

char element = stack[top];

top--;

return element;

char peek()

if (top == -1) {

printf("Stack is empty\n");

exit(1);

return stack[top];

void infix_to_postfix(char infix[], char postfix[])

int i = 0;

int j = 0;

while (infix[i] != '\0') {

if (isdigit(infix[i])) {
 DS LAB MANUAL (PITW ) NIHAZRAHIM

postfix[j++] = infix[i++];

} else if (infix[i] == '(') {

push(infix[i++]);

} else if (infix[i] == ')') {

while (peek() != '(')

postfix[j++] = pop();

pop(); // remove '(' from stack

i++;

} else {

while (precedence(infix[i]) <= precedence(peek()))

postfix[j++] = pop();

push(infix[i++]);

while (top != -1)

postfix[j++] = pop();

postfix[j] = '\0';

int evaluate_postfix(char postfix[])

int i, result;

int number;

int operand1, operand2;

for (i = 0; postfix[i] != '\0'; i++) {

if (isdigit(postfix[i])) {

push(postfix[i] - '0');

} else {
 DS LAB MANUAL (PITW ) NIHAZRAHIM

operand2 = pop();

operand1 = pop();

switch (postfix[i]) {

case '+':

result = operand1 + operand2;

break;

case '-':

result = operand1 - operand2;

break;

case '*':

result = operand1 * operand2;

break;

case '/':

result = operand1 / operand2;

break;

push(result);

return pop();

int main()

char infix[MAX_SIZE];

char postfix[MAX_SIZE];

printf("Enter an infix expression: ");

scanf("%[^\n]", infix);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

infix_to_postfix(infix, postfix);

printf("Postfix notation: %s\n", postfix);

int result = evaluate_postfix(postfix);

printf("Result = %d\n", result);

return 0;

ii) Create a program to determine whether a given string is a palindrome or not.

#include<stdio.h>

#include<string.h>

int main()

char str[100];

int i, j, len, flag = 0;

printf("Enter a string: ");

scanf("%s", str);

len = strlen(str);

for (i = 0, j = len - 1; i < j; i++, j--) {

if (str[i] != str[j]) {

flag = 1;

break;

if (flag == 1)

printf("%s is not a palindrome\n", str);

else

printf("%s is a palindrome\n", str);

return 0;
 DS LAB MANUAL (PITW ) NIHAZRAHIM

iii) Implement a stack or queue to perform comparison and check for symmetry.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_SIZE 100

struct node {

char data;

struct node* next;

};

struct node* top = NULL;

bool is_empty()

return top == NULL;

void push(char data)

struct node* temp = malloc(sizeof(struct node));

temp->data = data;

temp->next = top;

top = temp;

char pop()

if (is_empty()) {

printf("Stack underflow\n");

exit(1);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

struct node* temp = top;

char data = temp->data;

top = top->next;

free(temp);

return data;

char peek()

if (is_empty()) {

printf("Stack is empty\n");

exit(1);

return top->data;

void print_stack()

if (is_empty()) {

printf("Stack is empty\n");

} else {

struct node* temp = top;

while (temp != NULL) {

printf("%c ", temp->data);

temp = temp->next;

printf("\n");

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

bool is_symmetrical(char* str)

int i;

int len = strlen(str);

for (i = 0; i < len / 2; i++) {

push(str[i]);

if (len % 2 == 1) {

i++;

while (str[i] != '\0') {

if (peek() == str[i]) {

pop();

} else {

return false;

i++;

return is_empty();

int main()

char str[MAX_SIZE];

printf("Enter a string: ");

scanf("%[^\n]", str);

printf("Input string: %s\n", str);

 DS LAB MANUAL (PITW ) NIHAZRAHIM

if (is_symmetrical(str)) {

printf("%s is symmetrical\n", str);

} else {

printf("%s is not symmetrical\n", str);

return 0;

Exercise 8: Binary Search Tree

i) Implementing a BST using Linked List.

#include <stdio.h>

#include <stdlib.h>

struct node {

int data;

struct node* left;

struct node* right;

};

struct node* create_node(int data)

struct node* new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->left = NULL;

new_node->right = NULL;

return new_node;

struct node* insert(struct node* root, int data)

if (root == NULL) {
 DS LAB MANUAL (PITW ) NIHAZRAHIM

return create_node(data);

if (data < root->data) {

root->left = insert(root->left, data);

} else {

root->right = insert(root->right, data);

return root;

void inorder(struct node* root)

if (root != NULL) {

inorder(root->left);

printf("%d ", root->data);

inorder(root->right);

int main()

struct node* root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("Inorder traversal: ");

inorder(root);

printf("\n");

return 0;

ii) Traversing of BST.

#include <stdio.h>

#include <stdlib.h>

struct node {

int data;

struct node* left;

struct node* right;

};

struct node* create_node(int data)

struct node* new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;

new_node->left = NULL;

new_node->right = NULL;

return new_node;

struct node* insert(struct node* root, int data)

if (root == NULL) {

return create_node(data);

if (data < root->data) {

 DS LAB MANUAL (PITW ) NIHAZRAHIM

root->left = insert(root->left, data);

} else {

root->right = insert(root->right, data);

return root;

void inorder(struct node* root)

if (root != NULL) {

inorder(root->left);

printf("%d ", root->data);

inorder(root->right);

void preorder(struct node* root)

if (root != NULL) {

printf("%d ", root->data);

preorder(root->left);

preorder(root->right);

void postorder(struct node* root)

if (root != NULL) {

postorder(root->left);

postorder(root->right);
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("%d ", root->data);

int main()

struct node* root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

printf("Inorder traversal: ");

inorder(root);

printf("\n");

printf("Preorder traversal: ");

preorder(root);

printf("\n");

printf("Postorder traversal: ");

postorder(root);

printf("\n");

return 0;

Exercise 9: Hashing

i) Implement a hash table with collision resolution techniques

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 DS LAB MANUAL (PITW ) NIHAZRAHIM

#define TABLE_SIZE 10
#define MAX_NAME 256
typedef struct {
char name[MAX_NAME];
int age;
} person;
person* hash_table[TABLE_SIZE];
unsigned int hash(char* name)
{
int length = strlen(name);
unsigned int hash_value = 0;
for (int i = 0; i < length; i++) {
hash_value += name[i];
hash_value = (hash_value * name[i]) % TABLE_SIZE;
}
return hash_value;
}
person* create_person(char* name, int age)
{
person* new_person = (person*)malloc(sizeof(person));
strncpy(new_person->name, name, MAX_NAME);
new_person->age = age;
return new_person;
}
void insert(person* p)
{
int index = hash(p->name);
for (int i = 0; i < TABLE_SIZE; i++) {
int attempt = (index + i) % TABLE_SIZE;
if (hash_table[attempt] == NULL) {
hash_table[attempt] = p;
return;
}
}
printf("Hash table is full\n");
}
person* search(char* name)
{
int index = hash(name);
for (int i = 0; i < TABLE_SIZE; i++) {
int attempt = (index + i) % TABLE_SIZE;
if (hash_table[attempt] != NULL && strcmp(hash_table[attempt]->name, name) == 0)
{
return hash_table[attempt];
 DS LAB MANUAL (PITW ) NIHAZRAHIM

}
}
return NULL;
}
void delete(person* p)
{
int index = hash(p->name);
for (int i = 0; i < TABLE_SIZE; i++) {
int attempt = (index + i) % TABLE_SIZE;

if (hash_table[attempt] != NULL && strcmp(hash_table[attempt]->name, p->name) == 0) {

hash_table[attempt] = NULL;
free(p);
return;
}
}
printf("Person not found in hash table\n");
}
void print_hash_table()
{
printf("Hash table:\n");
printf("-----------\n");
for (int i = 0; i < TABLE_SIZE; i++) {
if (hash_table[i] != NULL) {
printf("%d:%s:%d\n", i, hash_table[i]->name, hash_table[i]->age);
} else {
printf("%d:NULL\n", i);
}
}
}
int main()
{
for (int i = 0; i < TABLE_SIZE; i++) {
hash_table[i] = NULL;
}
insert(create_person("Alice", 25));
insert(create_person("Bob", 30));
insert(create_person("Charlie", 35));
insert(create_person("Dave", 40));
insert(create_person("Eve", 45));
insert(create_person("Frank", 50));
insert(create_person("Grace", 55));
insert(create_person("Henry", 60));
print_hash_table();
person* result = search("Alice");
 DS LAB MANUAL (PITW ) NIHAZRAHIM

if (result == NULL) {
printf("Person not found in hash table\n");
} else {
printf("%s:%d\n", result->name, result->age);
}
delete(result);
print_hash_table();
return 0;
}

ii) Write a program to implement a simple cache using hashing

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define CACHE_SIZE 10

#define MAX_KEY 256

#define MAX_VALUE 1024

typedef struct {

char key[MAX_KEY];

char value[MAX_VALUE];

} cache_entry;

cache_entry* hash_table[CACHE_SIZE];

unsigned int hash(char* key)

int length = strlen(key);

unsigned int hash_value = 0;

for (int i = 0; i < length; i++) {

hash_value += key[i];

hash_value = (hash_value * key[i]) % CACHE_SIZE;

return hash_value;

}
 DS LAB MANUAL (PITW ) NIHAZRAHIM

cache_entry* create_cache_entry(char* key, char* value)

cache_entry* new_entry = (cache_entry*)malloc(sizeof(cache_entry));

strncpy(new_entry->key, key, MAX_KEY);

strncpy(new_entry->value, value, MAX_VALUE);

return new_entry;

void put(char* key, char* value)

int index = hash(key);

for (int i = 0; i < CACHE_SIZE; i++) {

int attempt = (index + i) % CACHE_SIZE;

if (hash_table[attempt] == NULL) {

hash_table[attempt] = create_cache_entry(key, value);

return;

} else if (strcmp(hash_table[attempt]->key, key) == 0) {

strncpy(hash_table[attempt]->value, value, MAX_VALUE);

return;

printf("Cache is full\n");

char* get(char* key)

int index = hash(key);

for (int i = 0; i < CACHE_SIZE; i++) {

 DS LAB MANUAL (PITW ) NIHAZRAHIM

int attempt = (index + i) % CACHE_SIZE;

if (hash_table[attempt] != NULL && strcmp(hash_table[attempt]->key, key) == 0) {

return hash_table[attempt]->value;

return NULL;

void delete(char* key)

int index = hash(key);

for (int i = 0; i < CACHE_SIZE; i++) {

int attempt = (index + i) % CACHE_SIZE;

if (hash_table[attempt] != NULL && strcmp(hash_table[attempt]->key, key) == 0) {

free(hash_table[attempt]);

hash_table[attempt] = NULL;

return;

printf("Key not found in cache\n");

void print_cache()

printf("Cache:\n");

printf("------\n");

for (int i = 0; i < CACHE_SIZE; i++) {

if (hash_table[i] != NULL) {

printf("%s:%s\n", hash_table[i]->key, hash_table[i]->value);

 DS LAB MANUAL (PITW ) NIHAZRAHIM

} else {

printf("NULL\n");

int main()

for (int i = 0; i < CACHE_SIZE; i++) {

hash_table[i] = NULL;

put("key1", "value1");

put("key2", "value2");

put("key3", "value3");

put("key4", "value4");

put("key5", "value5");

put("key6", "value6");

put("key7", "value7");

put("key8", "value8");

put("key9", "value9");

put("key10", "value10");

print_cache();

printf("%s\n", get("key1"));

printf("%s\n", get("key2"));

printf("%s\n", get("key3"));

printf("%s\n", get("key4"));

printf("%s\n", get("key5"));

printf("%s\n", get("key6"));
 DS LAB MANUAL (PITW ) NIHAZRAHIM

printf("%s\n", get("key7"));

printf("%s\n", get("key8"));

printf("%s\n", get("key9"));

printf("%s\n", get("key10"));

delete("key1");

print_cache();

return 0;