Data Structure and algorithm

Lab # 3

Name : Kinza Eiman

Reg no : SP22-BCT-020
Class: BCT 4A
Submitted to : Hafiz Syed Muhammad Muslim
Activity # 1
#include <iostream>
using namespace std;

struct Nodetype
{
int data; // Add data member to store the data in the node
struct Nodetype* next; // points towards next
struct Nodetype* prev; // points to previous
};

Nodetype* first = NULL; // Use NULL instead of Null

Nodetype* last = NULL; // Use NULL instead of Null

void insert_end()
{
Nodetype* p;
p = new Nodetype;
cout << "Enter the data in node: ";
cin >> p->data;

if (first == NULL)
first = last = p;
else {
last->next = p;
p->prev = last;
last = p;
}
}

int main() {
insert_end();
return 0;
}

Output:

Activity # 2
#include <iostream>

struct Node {
int data;
Node* next;
Node* prev;
 Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}

// Function to insert a node at the end of the doubly linked list

void insert(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}

// Function to access a node in forward direction and return its value

int forwardAccess(int position) {
Node* current = head;
int count = 0;

while (current) {
if (count == position) {
return current->data;
}
current = current->next;
count++;
}

return -1; // Node not found

}

// Function to access a node in backward direction and return its value

int backwardAccess(int position) {
Node* current = tail;
int count = 0;
while (current) {
if (count == position) {
return current->data;
}
current = current->prev;
count++;
}
return -1; // Node not found
}
// Function to display the doubly linked list
void display() {
 Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
private:
Node* head;
Node* tail;
};

int main() {
DoublyLinkedList dll;

// Insert some nodes into the doubly linked list

dll.insert(1);
dll.insert(2);
dll.insert(3);
dll.insert(4);

// Display the doubly linked list

std::cout << "Doubly Linked List: ";
dll.display();

// Ask the user for the position to access

int position;
std::cout << "Enter the position of the node to access: ";
std::cin >> position;

// Access the node in forward direction

int forwardValue = dll.forwardAccess(position);
if (forwardValue != -1) {
std::cout << "Value at position " << position << " (forward): " << forwardValue << std::endl;
} else {
std::cout << "Node not found at position " << position << " (forward)." << std::endl;
}
// Access the node in backward direction
int backwardValue = dll.backwardAccess(position);
if (backwardValue != -1) {
std::cout << "Value at position " << position << " (backward): " << backwardValue << std::endl;
} else {
std::cout << "Node not found at position " << position << " (backward)." << std::endl;
}

return 0;
}
Output:

Activity # 3 Activity # 4
#include <iostream>
using namespace std;

struct Nodetype
{
int data;
struct Nodetype* next;
struct Nodetype* prev;
};

Nodetype* first = NULL;

Nodetype* last = NULL;

void insert_before_first_Node(int value) {

Nodetype* p = new Nodetype;
p->data = value;

if (first == NULL) {
// The list is empty
first = last = p;
p->next = NULL;
p->prev = NULL;
}
else {
p->next = first;
p->prev = NULL;
first->prev = p;
first = p;
}
}

void insert_after_Last_node(int value) {

Nodetype* p = new Nodetype;
p->data = value;

if (first == NULL) {
// The list is empty
first = last = p;
p->next = NULL;
p->prev = NULL;
}
 else {
p->next = NULL;
p->prev = last;
last->next = p;
last = p;
}
}

void delete_first()
{
Nodetype* nodePtr = first;
if (first == nullptr)
{
return; // list is empty
}

if (first == last)
{
// list has only one node
first = last = nullptr;
}
else
{
// list has more than one node
first = first->next;
first->prev = nullptr;
}
delete nodePtr;
}

void delete_last()
{
Nodetype* nodePtr = last;

if (first == nullptr)
{
return; // list is empty
}

if (first == last)
{
// list has only one node
first = last = nullptr;
}
else
{
// list has more than one node
last = last->prev;
last->next = nullptr;
}
delete nodePtr;
}

void deleteSpecific(int key)

{
Nodetype* temp = first;
while (temp != NULL && temp->data != key) {
temp = temp->next;
}

if (temp == NULL) {
// Node with the specified key not found
return;
}

if (temp == first) {
// Node to be deleted is the first node
delete_first();
}
else if (temp == last) {
// Node to be deleted is the last node
delete_last();
}
else {
// Node to be deleted is in the middle
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}
}

int main() {
// Initialize an empty doubly linked list
first = last = NULL;

// Insert nodes before the first node

insert_before_first_Node(1);

// Print the list forward

cout << "List forward: ";
Nodetype* Current = first;
while (Current != NULL) {
cout << Current->data << " ";
Current = Current->next;
}
cout << endl;

// Insert nodes after the last node

insert_after_Last_node(4);
insert_after_Last_node(6);
insert_after_Last_node(7);
insert_after_Last_node(9);
 // Print the list forward again
cout << "List after insertion: ";
Nodetype* current = first;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;

delete_first();
cout << "List after deletion of first element: ";
current = first;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;

delete_last();
cout << "List after deletion of last element: ";
current = first;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;

deleteSpecific(4);
cout << "List after deleting a specific number: ";
current = first;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;

// Don't forget to free memory by deleting any remaining nodes in the list.
while (first != NULL) {
Nodetype* temp = first;
first = first->next;
delete temp;
}

return 0;
}
OutPut:

Activity # 5
#include <iostream>
using namespace std;

struct Nodetype
{
int data;
struct Nodetype* next;
struct Nodetype* prev;
};

Nodetype* first = NULL;

Nodetype* last = NULL;

void insert_before_first_Node(int value) {

Nodetype* p = new Nodetype;
p->data = value;

if (first == NULL) {
// The list is empty
first = last = p;
p->next = NULL;
p->prev = NULL;
}
else {
p->next = first;
p->prev = NULL;
first->prev = p;
first = p;
}
}

void completeDelete()
{
Nodetype* temp = first;
while (temp != NULL)
{
 Nodetype * toDelete = temp;
temp = temp -> next;
delete toDelete;
}
}

Output:
Graded Task#1
#include <bits/stdc++.h>

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

Node(int data)

this->data = data;

next = NULL;

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/* Function to reverse the linked list */

void reverse()

// Initialize current, previous and next pointers

Node* current = head;

Node *prev = NULL, *next = NULL;

while (current != NULL) {

// Store next

next = current->next;

// Reverse current node's pointer

current->next = prev;
 // Move pointers one position ahead.

prev = current;

current = next;

head = prev;

/* Function to print linked list */

void print()

struct Node* temp = head;

while (temp != NULL) {

cout << temp->data << " ";

temp = temp->next;

void push(int data)

Node* temp = new Node(data);

temp->next = head;

head = temp;

};

int main()

/* Starting with the empty list */

LinkedList ll;

ll.push(1);

ll.push(2);
 ll.push(3);

ll.push(4);

cout << "Given linked list\n";

ll.print();

ll.reverse();

cout << "\nReversed linked list \n";

ll.print();

return 0;

Output:

Graded Task # 2
#include <iostream>

using namespace std;

// Define a structure for a singly linked list node

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};
// Function to search for two values in the linked list

pair<Node*, Node*> searchTwoValues(Node* head, int value1, int value2) {

Node* node1 = nullptr; // Pointer to the node containing the first value

Node* node2 = nullptr; // Pointer to the node containing the second value

// Traverse the linked list

while (head != nullptr) {

if (head->data == value1) {

node1 = head;

if (head->data == value2) {

node2 = head;

head = head->next;

// Return a pair of pointers to the found nodes (may be nullptr)

return make_pair(node1, node2);

int main() {

Node* head = nullptr;

// Create a sample linked list (1 -> 2 -> 3 -> 4 -> 5)

for (int i = 1; i <= 5; ++i) {

Node* newNode = new Node(i);

newNode->next = head;

head = newNode

cout << "Original linked list: ";

 for (Node* current = head; current != nullptr; current = current->next) {

cout << current->data << " ";

cout << endl;

int value1, value2;

cout << "Enter two values to search in the linked list: ";

cin >> value1 >> value2;

pair<Node*, Node*> result = searchTwoValues(head, value1, value2);

if (result.first != nullptr && result.second != nullptr) {

cout << "Both values found in nodes: " << result.first->data << " and " << result.second->data <<
endl;

} else {

cout << "At least one of the values was not found in the linked list." << endl;

// Clean up memory (delete nodes in a real application)

while (head != nullptr) {

Node* temp = head;

head = head->next;

delete temp;

return 0;

Output:
Graded Activity # 3

#include <iostream>

struct SinglyNode {

int data;

SinglyNode* next;

SinglyNode(int val) : data(val), next(nullptr) {}

};

struct DoublyNode {

int data;

DoublyNode* prev;

DoublyNode* next;

DoublyNode(int val) : data(val), prev(nullptr), next(nullptr) {}

};

// Function to convert a singly linked list to a doubly linked list

DoublyNode* convertSinglyToDoubly(SinglyNode* singlyHead) {

if (!singlyHead)

return nullptr;

DoublyNode* doublyHead = new DoublyNode(singlyHead->data);

DoublyNode* currentDoublyNode = doublyHead;

SinglyNode* currentSinglyNode = singlyHead->next;

while (currentSinglyNode) {

DoublyNode* newDoublyNode = new DoublyNode(currentSinglyNode->data);

currentDoublyNode->next = newDoublyNode;

newDoublyNode->prev = currentDoublyNode;
 currentDoublyNode = newDoublyNode;

currentSinglyNode = currentSinglyNode->next;

return doublyHead;

// Function to print a doubly linked list

void printDoublyLinkedList(DoublyNode* head) {

DoublyNode* current = head;

while (current) {

std::cout << current->data << " ";

current = current->next;

std::cout << std::endl;

int main() {

// Create a singly linked list

SinglyNode* singlyHead = new SinglyNode(1);

singlyHead->next = new SinglyNode(2);

singlyHead->next->next = new SinglyNode(3);

singlyHead->next->next->next = new SinglyNode(4);

// Convert the singly linked list to a doubly linked list

DoublyNode* doublyHead = convertSinglyToDoubly(singlyHead);

// Print the doubly linked list

std::cout << "Doubly Linked List: ";

printDoublyLinkedList(doublyHead);
 // Clean up memory (not shown in this simplified example)

return 0;

Output: