LAB MANUAL Data Structures and Algorithms

LAB NO. 10 19 /11 / 2024

Implementation of Linked List
Lab outcomes:
After completing this lab, students will be able to.

 Implement the linked list

 Apply different operations on linked list

Corresponding CLO and PLO:

 CLO-2, PLO-3
Tools:
 Eclipse IDE
 JDK

Theory:
List ADT
A linked list is a data structure consisting of a group of nodes which together represent a sequence. Each
node is composed of a data part and a reference (in other words, a link) to the next node in the sequence.

The Linked List is a collection of elements called nodes, each node of which stores two items of
information, i.e., data part and link field.
The data part of each node consists of the data record of an entity. The link field is a pointer and
contains the address of next node.
The beginning of the linked list is stored in a pointer termed as head which points to the first node.
The head pointer will be passed as a parameter to any method, to perform an operation.
First node contains a pointer to second node, second node contains a pointer to the third node and so
on.

The last node in the list has its next field set to NULL to mark the end of the list.
 LAB MANUAL Data Structures and Algorithms

There are several variants of linked lists. These are as follows:

 Singly linked list
 Circular linked list
 Doubly linked list
 Doubly circular linked list

Single linked list:

Single Linked List is a collection of nodes. Each node contains 2 fields:
1) Info where the information is stored
2) link which points to the next node in the list.

Why do we need a Linked List?

You must be aware of the arrays which is also a linear data structure but arrays have certain
limitations such as:
1) Size of the array is fixed which is decided when we create an array so it is hard to predict the
number of elements in advance, if the declared size fall short then we cannot increase the size of an
array and if we declare a large size array and do not need to store that many elements then it is a
waste of memory.
2) Array elements need contiguous memory locations to store their values.
3) Inserting an element in an array is performance wise expensive as we must shift several
elements to make a space for the new element. For example:
Let’s say we have an array that has following elements: 10, 12, 15, 20, 4, 5, 100, now if we want to
insert a new element 99 after the element that has value 12 then we must shift all the elements after
12 to their right to make space for new element.
Similarly deleting an element from the array is also a performance wise expensive operation
because all the elements after the deleted element must be shifted left.
These limitations are handled in the Linked List by providing following features:
1. Linked list allows dynamic memory allocation, which means memory allocation is done at the
run time by the compiler and we do not need to mention the size of the list during linked list
declaration.
2. Linked list elements don’t need contiguous memory locations because elements are linked with
each other using the reference part of the node that contains the address of the next node of the list.
 LAB MANUAL Data Structures and Algorithms

3. Insert and delete operations in the Linked list are not performance wise expensive because adding
and deleting an element from the linked list doesn’t require element shifting, only the pointer of the
previous and the next node requires change

The operations that can be performed on single linked lists includes:

1) Insertion
2) Deletion
3) traversing the list

Procedure:
Tasks:
INSERTFIRST( START, ITEM)

This algorithm inserts ITEM as the first node in the LIST.

1. Set DATA[NEW] = ITEM;

[Copies new data into new node.]

2. Set NEXT[NEW] = START.

[New node now points to the original first node.]

3. Set START := NEW.

[Changes START so it points to the new node.]

4. Exit

DELETEFIRST( START, ITEM)

This algorithm deletes a node ITEM from the

beginning of the LIST.

1. If START = NULL, than: [If List is already Empty.]

a) Set ITEM := NULL. [Nothing to delete.]

b) Print “LIST EMPTY” and Return.

2. Set ITEM := DATA[FIRST]. [Save data to ITEM.]

3. Set FIRST:= NEXT[FIRST]. [Delete it.]

4. Return.

(Traversing a Linked List) TRAVERSE(LIST,START)

Let LIST be a linked list in memory. This algorithm

traverses LIST, applying an operation PRECESS to

 LAB MANUAL Data Structures and Algorithms

each element of LIST. The variable CURRENT points to the node currently being processed.

1. Set CURRENT:=START. [Initializes pointer CURRENT.]

2. Repeat Step 3 and 4 while CURRENT!=NULL.

3. Apply PROCESS to DATA[CURRENT].

4. Set CURRENT:= NEXT[CURRENT].

[CURRENT now points to the next node.] [End of step 2 loop.]

5. Exit

Code
Task-1:
Implement Below Linked List Operations
1. Insertion at first
2. Insertion at last
3. Insertion at specific position
4. Deletion at first
5. Deletion at last
6. Deletion at specific position
7. Display
Code
#include <iostream>
#include <cstdlib>
using namespace std; //Huzaifa Ali 59384

struct Node {
int data;
Node* link;
};

Node* head = nullptr;

void insertAtBegin(int value) {

Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->link = head;
head = new_node;
}

void display() {
Node* ptr = head;
while (ptr != nullptr) {
cout << ptr->data << " ";
ptr = ptr->link;
}
cout << endl;
}

void deleteAtBegin() {
if (head == nullptr) {
cout << "Linked list is empty" << endl;
return;
}
Node* temp = head;
head = head->link;
LAB MANUAL Data Structures and Algorithms

cout << ptr->data << " ";

ptr = ptr->link;
}
cout << endl;
}
void deleteAtBegin() {
if (head == nullptr) {
cout << "Linked list is empty" << endl;
return;
}
Node* temp = head;
head = head->link;
free(temp);
}
void insertAtEnd(int value) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->link = nullptr;
if (head == nullptr) {
head = new_node;
return;
}
Node* current = head;
while (current->link != nullptr) {
current = current->link;
}
current->link = new_node;
}
void deleteAtEnd() {
if (head == nullptr) {
cout << "Linked list is empty" << endl;
return;
}
if (head->link == nullptr) {
free(head);
head = nullptr;
return;
}
Node* prev = nullptr;
Node* current = head;
while (current->link != nullptr) {
prev = current;
current = current->link;
}
LAB MANUAL Data Structures and Algorithms

prev->link = nullptr;
free(current);
}
void deleteAtPos(int item) {
if (head == nullptr) {
cout << "Linked list is empty" << endl;
return;
}
if (head->data == item) {
Node* temp = head;
head = head->link;
free(temp);
return;
}
Node* prev = nullptr;
Node* current = head;
while (current != nullptr && current->data != item) {
prev = current;
current = current->link;
}
if (current == nullptr) {
cout << "Item not found" << endl;
return;
}
prev->link = current->link;
free(current);
}
free(current);
}
void insertAtPos(int value) {
int item;
cout << "Enter the item after which to insert: ";
cin >> item;
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->link = nullptr;
Node* current = head;
while (current != nullptr && current->data != item) {
current = current->link;
}
if (current == nullptr) {
cout << "Item not found" << endl;
free(new_node);
return;
}
}
new_node->link = current->link;
current->link = new_node;
}
int main() {
int opt;

do {
LAB MANUAL Data Structures and Algorithms

int opt;
do {
cout << "1: Insert at beginning\n2: Delete at beginning\n3: Display\n4: Insert at end\n5: Delete at end\n6:
Insert at position\n7: Delete at position\n8: Exit\n";
cout << "Enter your option: ";
cin >> opt;
switch (opt) {
case 1: {
int data;
cout << "Enter value to insert: ";
cin >> data;
insertAtBegin(data);
break;
}
case 2:
deleteAtBegin();
break;
case 3:
display();
break;
case 4: {
int data;
cout << "Enter value to insert: ";
cin >> data;
insertAtEnd(data);
break;
}
insertAtBegin(data);
break;
}
case 2:
deleteAtBegin();
break;
case 3:
display();
break;
case 4: {
int data;
cout << "Enter value to insert: ";
cin >> data;
insertAtEnd(data);
break;
} case 5:
deleteAtEnd();
break;
}
 LAB MANUAL Data Structures and Algorithms

case 6: {
int data;
cout << "Enter value to insert: ";
cin >> data;
insertAtPos(data);
break;
}
case 7: {
int item;
cout << "Enter value to delete: ";
cin >> item;
deleteAtPos(item);
break;
}
case 8:
cout << "Exiting..." << endl;
break;
default:
cout << "Invalid option" << endl;
}
} while (opt != 8);
return 0;
}

Output
 LAB MANUAL Data Structures and Algorithms

Observations:
In this lab we Learned about Linked list and we also implemented different operations on linked list
like insertion, deletion and displaying.
 LAB MANUAL Data Structures and Algorithms

Rubrics:

Absent Student is Student can Student has Student has Student

unable to understand followed constructed perfectly
follow the the provided instructions the implemented a
provided laboratory to construct functional/ working
instructions instructions the working model/ logic/
properly. and familiar fundamental schematic/ circuit/ block
The student with the lab schematic/ model/ block diagram/ code
can name the environment block diagram/ and
Demonstration hardware or (Trainer/ diagram/ code, and successfully
simulation software/ code/ model have executed the
platform, but IDE), but on the successfully lab objective in
unable to cannot protoboard/ executed the Realtime or in
implement implement on trainer/ program/ run a simulation
anything the platform simulation circuit on environment
practically or practically or software. software and produced
on the software on the platform the desired
software results
Category Ungraded Very Poor Poor Fair Good Excellent
Percentage [0] [1-20] [21-40] [41-60] [61-80] [81-100]
Marks 0.0 0.1 0.2 0.3 0.4 0.5

Date Total Marks Instructor’s Signature

Report not Plagiarized Requirements Observations Appropriate Correctly

submitted content are listed and are recorded computations drawn
presented or experimental along with or numerical conclusion
Laboratory incomplete procedure is detailed analysis is with
Reports submission presented procedure performed exact results
and complete
report in all
respects
Category Ungraded Very Poor Poor Fair Good Excellent
Percentage [0] [1-20] [21-40] [41-60] [61-80] [81-100]
Marks 0.0 0.1 0.2 0.3 0.4 0.5

Date Total Marks Instructor’s Signature

 LAB MANUAL Data Structures and Algorithms

LAB NO. 11 26/11/ 2024

Implementation of Queue ADT.
Lab outcomes:
After completing this lab, students will be able to.

 Implement Queue Operations

Corresponding CLO and PLO:

 CLO-2, PLO-3

Tools:
 Eclipse IDE
 JDK
 Dev C++

Theory:
Queue is a data structure in which the elements are added at one end, called the rear, and deleted from
the other end, called the front. A First in First Out data structure (FIFO). The rear of the queue is
accessed whenever a new element is added to the queue, and the front of the queue is accessed
whenever an element is deleted from the queue. As in a stack, the middle elements in the queue are in
accessible, even if the queue elements are sorted in an array.
BASIC QUEUE OPERATIONS:
1. Initialize Queue (): Initializes the queue to an empty state.
2. Determines whether the queue is empty. If the queue is empty, it returns the value true;
otherwise, it returns the value false.
3. Determines whether the queue is full. If the queue is empty, it returns the value true; otherwise, it
returns the value false.
4. Rear: Returns the last element of the queue. Prior to this operation, the queue must exit.
5. Front: Returns the front, that is, the first element of the queue. Priority to this operation, the queue
must exit.
Queue can be stored either in an array or in linked list. We will consider both implementations. Because
elements are added at one end and remove from the other end, we need two pointers to keep track of
the front and rear of the queue, called queue Front and queue Rear. Queues are restricted versions of
arrays and linked lists. The middle terms of queue should not be accessed directly.

Procedure:
Basic Operation Associated on Queues:
1) Insert an item into the Queue.
2) Delete an item into the Queue.
 LAB MANUAL Data Structures and Algorithms

a) Algorithm to insert an item into a Queue Q:

Procedure Insert(Q, SIZE, F, R, ITEM) Q Array
SIZE Queue size F front Pointer R rear pointer
ITEM: information to be inserted at the rear of queue. Step 1: {Check for Queue overflow} If
R>=SIZE then Prints(‘Queue overflow’)
Return
Step 2: {Increment rear pointer} R=R+1
Step 3: {Insert new element at rear end of queue} Q[R]=ITEM
Step 4: {If initially the queue is empty adjust the front pointer}
If F=0, then F=1
b) Algorithm to delete an item from a Queue Q:
Procedure Delete(Q, F, R) Q Array
F front Pointer R rear pointer
ITEM: information to be inserted at the rear of queue. Step 1: {Check for Queue underflow} If
F=0 then
Prints(‘Queue underflow’) Return
Step 2: {Delete the queue element at front end and store it into item} ITEM=Q[F] Step
3: {If queue is empty after deletion, set front and rear pointers to 0} If F=R then F=0
R=0
{Otherwise increment front pointer} Else
F=F+1
Return(ITEM)
c) Algorithm to display the items from the Queue Q
Procedure Dispaly(Q) Q Array
Step1: {Check queue values} If F<0
Prints(‘Queue is empty’) Step 2: {display Queue values} For I value F to R
Prints(Q[I])
I=I+1.

Tasks:
Task-1:
Write a program to implement Queue operations using arrays.
 Insert an item into the Queue.
 Delete an item into the Queue.
 LAB MANUAL Data Structures and Algorithms

CODE

#include <iostream> //Huzaifa Ali 59384

using namespace std;

int queue[100], n = 100, front = -1, rear = -1;

void insert() {
int val;
if (rear == n - 1) {
cout << "Queue is overflow" << endl;
} else {
if (front == -1)
front = 0;
cout << "Insert the element in queue: ";
cin >> val;
rear++;
queue[rear] = val;
}
}

void Delete() {
if (front == -1) {
cout << "Queue is empty" << endl;
return;
} else {
cout << "Element deleted from Queue: " << queue[front] << endl;
front++;
if (front > rear) {
front = rear = -1; // Reset the queue if it's empty
}
}
}

void Display() {
if (front == -1) {
cout << "Queue is empty" << endl;
} else {
cout << "Queue elements: ";
for (int i = front; i <= rear; i++) {
cout << queue[i] << " ";
}
cout << endl;
}
}

int main() {
int ch;
do {
cout << "1) Insert Element to Queue" << endl;
cout << "2) Delete Element from Queue" << endl;
cout << "3) Display all Elements of Queue" << endl;
cout << "4) Exit" << endl;

cout << "Enter your choice: ";

cin >> ch;

switch (ch) {
case 1:
 LAB MANUAL Data Structures and Algorithms

insert();
break;
case 2:
Delete();
break;
case 3:
Display();
break;
case 4:
cout << "Exit" << endl;
break;
default:
cout << "Invalid choice" << endl;
}
} while (ch != 4);
return 0;
}
Output:

Observations:
In this lab we learnt about how we Insert an item into the Queue and also we learnt that how we can
Delete an item into the Queue.
 LAB MANUAL Data Structures and Algorithms

Rubrics:
Absent Student is Student can Student has Student has Student
unable to understand followed constructed perfectly
follow the the provided instructions the implemented a
provided laboratory to construct functional/ working
instructions instructions the working model/ logic/
properly. and familiar fundamental schematic/ circuit/ block
The student with the lab schematic/ model/ block diagram/ code
can name the environment block diagram/ and
Demonstration hardware or (Trainer/ diagram/ code, and successfully
simulation software/ code/ model have executed the
platform, but IDE), but on the successfully lab objective in
unable to cannot protoboard/ executed the Realtime or in
implement implement on trainer/ program/ run a simulation
anything the platform simulation circuit on environment
practically or practically or software. software and produced
on the software on the platform the desired
software results
Category Ungraded Very Poor Poor Fair Good Excellent
Percentage [0] [1-20] [21-40] [41-60] [61-80] [81-100]
Marks 0.0 0.1 0.2 0.3 0.4 0.5

Date Total Marks Instructor’s Signature

Report not Plagiarized Requirements Observations Appropriate Correctly

submitted content are listed and are recorded computations drawn
presented or experimental along with or numerical conclusion
Laboratory incomplete procedure is detailed analysis is with
Reports submission presented procedure performed exact results
and complete
report in all
respects
Category Ungraded Very Poor Poor Fair Good Excellent
Percentage [0] [1-20] [21-40] [41-60] [61-80] [81-100]
Marks 0.0 0.1 0.2 0.3 0.4 0.5
Date Total Marks Instructor’s Signature