[go: up one dir, main page]
Scribd
Upload
20 views23 pages

C++ Linked List Operations Guide

The document contains a series of programming assignments focused on data structures, specifically linked lists, using C++ and Java. It includes tasks such as creating a student list with functionalities for adding, searching, deleting, and updating employee information, as well as shuffling, finding intersections and unions of linked lists, sorting, and removing duplicates. Each section provides code examples and explanations for implementing the required functionalities.

Uploaded by

Gaming Inside
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
20 views23 pages

C++ Linked List Operations Guide

The document contains a series of programming assignments focused on data structures, specifically linked lists, using C++ and Java. It includes tasks such as creating a student list with functionalities for adding, searching, deleting, and updating employee information, as well as shuffling, finding intersections and unions of linked lists, sorting, and removing duplicates. Each section provides code examples and explanations for implementing the required functionalities.

Uploaded by

Gaming Inside
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 23

Data Structures-W1

Assignment No. 01
Muhammad Abubaker
F2023065223
Q1: It is required to make a list of students registered in Data Structures course.
To achieve this functionality, develop a C++ program/Java and use linked list to store Employee ids and
names. Each node in the linked list will contain three items: employee id, employee name, pointer to
next node. When the program starts, it should display the following menu:

1. Enter Employee information


2. Search employee by ID
3. Search Employee by Name
4. Delete Employee information
5. Update Employee information
6. Print all Employees
7.Quit
(Main menu will be displayed again after any action performed)

Code:
#include <iostream>
#include <string>
using namespace std;

class Employee {
public:
int id;
string name;
Employee* next;

Employee(int id, string name) {


this->id = id;
this->name = name;
this->next = nullptr;
}
};
// Global pointer to head of linked list
Employee* head = nullptr;

// Function to enter employee information


void enterEmployee() {
int id;
string name;
cout << "Enter Employee ID: ";
cin >> id;
cout << "Enter Employee Name: ";
cin >> ws; // This discards leading whitespace
getline(cin, name);
Employee* newEmployee = new Employee(id, name);

if (head == nullptr) {
head = newEmployee;
} else {
Employee* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newEmployee;
}
cout << "Employee added successfully!" << endl;
}

void searchEmployeeById() {
int id;
cout << "Enter Employee ID to search: ";
cin >> id;
Employee* temp = head;
while (temp != nullptr) {
if (temp->id == id) {
cout << "Employee found!" << endl;
cout << "ID: " << temp->id << endl;
cout << "Name: " << temp->name << endl;
return;
}
temp = temp->next;
}
cout << "Employee not found!" << endl;
}

// Function to search employee by name


void searchEmployeeByName() {
string name;
cout << "Enter Employee Name to search: ";
cin >> ws; // This discards leading whitespace
getline(cin, name);
Employee* temp = head;
while (temp != nullptr) {
if (temp->name == name) {
cout << "Employee found!" << endl;
cout << "ID: " << temp->id << endl;
cout << "Name: " << temp->name << endl;
return;
}
temp = temp->next;
}
cout << "Employee not found!" << endl;
}

// Function to delete employee information


void deleteEmployee() {
int id;
cout << "Enter Employee ID to delete: ";
cin >> id;
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
if (head->id == id) {
Employee* temp = head;
head = head->next;
delete temp;
cout << "Employee deleted successfully!" << endl;
return;
}
Employee* temp = head;
while (temp->next != nullptr) {
if (temp->next->id == id) {
Employee* employeeToDelete = temp->next;
temp->next = temp->next->next;
delete employeeToDelete;
cout << "Employee deleted successfully!" << endl;
return;
}
temp = temp->next;
}
cout << "Employee not found!" << endl;
}

// Function to update employee information


void updateEmployee() {
int id;
cout << "Enter Employee ID to update: ";
cin >> id;
Employee* temp = head;
while (temp != nullptr) {
if (temp->id == id) {
cout << "Enter new Employee Name: ";
cin >> ws; // This discards leading whitespace
getline(cin, temp->name);
cout << "Employee updated successfully!" << endl;
return;
}
temp = temp->next;
}
cout << "Employee not found!" << endl;
}

// Function to print all employees


void printEmployees() {
Employee* temp = head;
while (temp != nullptr) {
cout << "ID: " << temp->id << endl;
cout << "Name: " << temp->name << endl;
cout << endl;
temp = temp->next;
}
}

int main() {
int choice;
while (true) {
cout << "Data Structures Course Student List" << endl;
cout << "-----------------------------------" << endl;
cout << "1. Enter Employee Information" << endl;
cout << "2. Search Employee by ID" << endl;
cout << "3. Search Employee by Name" << endl;
cout << "4. Delete Employee Information" << endl;
cout << "5. Update Employee Information" << endl;
cout << "6. Print All Employees" << endl;
cout << "7. Quit" << endl;
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
enterEmployee();
break;
case 2:
searchEmployeeById();
break;
case 3:
searchEmployeeByName();
break;
case 4:
deleteEmployee();
break;
case 5:
updateEmployee();
break;
case 6:
printEmployees();
break;
case 7:
cout << "Exiting program." << endl;
return 0;
default:
cout << "Invalid choice! Please enter a number between 1 and 7." << endl;
}
}
return 0;
}

Q2: Shuffling in Link List


Provide a function which will shuffle two lists.
Example List 1:

3579
List 2:1 2 4 8
Output: 3 1 2 5 4 7 8 9
First element from the first list and first element of the second list then second element of
the first list and second element of the second list and so on.
Code:
#include <iostream>
using namespace std;

class Node {
public:
int A;
Node* next;
Node(int A)
this->A = A;
this->next = nullptr;
}
};

void append(Node** head, int newA)


Node* newNode = new Node(newA);
Node* last = *head;
if (*head == nullptr) {
*head = newNode;
return;
}
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}

void printList(Node* node) {


while (node != nullptr) {
cout << node->A << " ";
node = node->next;
}
cout << endl;
}

Node* shuffleLists(Node* a, Node* b) {


Node* result = nullptr;
Node** lastPtrRef = &result;

while (a != nullptr || b != nullptr) {


if (a != nullptr) {
append(lastPtrRef, a->A);
a = a->next;
}
if (b != nullptr) {
append(lastPtrRef, b->A);
b = b->next;
}
lastPtrRef = &((*lastPtrRef)->next);
}
return result;
}

int main() {
Node* list1 = nullptr;
Node* list2 = nullptr;

append(&list1, 3);
append(&list1, 5);
append(&list1, 7);
append(&list1, 9);

append(&list2, 1);
append(&list2, 2);
append(&list2, 4);
append(&list2, 8);

cout << "List 1: ";


printList(list1);
cout << "List 2: ";
printList(list2);

Node* shuffledList = shuffleLists(list1, list2);


cout << "Shuffled List: ";
printList(shuffledList);

return 0;
}

Q3 (a): Intersection of Link Lists Given two sorted lists, L1 and L2, write a procedure to
compute L1 ∩ L2 Intersection. Hint: Take a Link List of your choice
Example List A = (1,2,3) and List B = (3,4,5) their intersection is A ∩ B = (3).
Code:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};

void append(Node** head, int newData) {


Node* newNode = new Node(newData);
Node* last = *head;
if (*head == nullptr) {
*head = newNode;
return;
}
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}

void printList(Node* node) {


while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}

Node* findIntersection(Node* a, Node* b) {


Node* result = nullptr;
Node** lastPtrRef = &result;

while (a != nullptr && b != nullptr) {


if (a->data == b->data) {
append(lastPtrRef, a->data);
a = a->next;
b = b->next;
} else if (a->data < b->data) {
a = a->next;
} else {
b = b->next;
}
}
return result;
}

int main() {
Node* list1 = nullptr;
Node* list2 = nullptr;

// List A = (1, 2, 3)
append(&list1, 1);
append(&list1, 2);
append(&list1, 3);

// List B = (3, 4, 5)
append(&list2, 3);
append(&list2, 4);
append(&list2, 5);

cout << "List 1: ";


printList(list1);
cout << "List 2: ";
printList(list2);

Node* intersection = findIntersection(list1, list2);


cout << "Intersection: ";
printList(intersection);

return 0;
}

Q3 (b): Union of Link Lists Given two sorted lists, L1 and L2, write a procedure to
compute L1 u L2 Intersection. Hint: Take a Link List of your choice
Example List A = (1,2,3) and List B = (4,5,6) their union
Code:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
void append(Node** head, int newData) {
Node* newNode = new Node(newData);
Node* last = *head;
if (*head == nullptr) {
*head = newNode;
return;
}
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}

void printList(Node* node) {


while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}

Node* findUnion(Node* a, Node* b) {


Node* result = nullptr;
Node** lastPtrRef = &result;

while (a != nullptr && b != nullptr) {


if (a->data == b->data) {
append(lastPtrRef, a->data);
a = a->next;
b = b->next;
} else if (a->data < b->data) {
append(lastPtrRef, a->data);
a = a->next;
} else {
append(lastPtrRef, b->data);
b = b->next;
}
lastPtrRef = &((*lastPtrRef)->next);
}

while (a != nullptr) {
append(lastPtrRef, a->data);
a = a->next;
lastPtrRef = &((*lastPtrRef)->next);
}

while (b != nullptr) {
append(lastPtrRef, b->data);
b = b->next;
lastPtrRef = &((*lastPtrRef)->next);
}

return result;
}

int main() {
Node* list1 = nullptr;
Node* list2 = nullptr;

// List A = (1, 2, 3)
append(&list1, 1);
append(&list1, 2);
append(&list1, 3);
// List B = (3, 4, 5)
append(&list2, 3);
append(&list2, 4);
append(&list2, 5);

cout << "List 1: ";


printList(list1);
cout << "List 2: ";
printList(list2);

Node* unionList = findUnion(list1, list2);


cout << "Union: ";
printList(unionList);

return 0;
}

Q4: Sorting of Link List You are given a Linked List. Write an Insert Sort() function which
sorts the nodes in ascending order. Example: List A = { 8,9,1,2} which be sorted in to List
Code:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};

// Function to add a new node at the rear (end) of the list


void appendOnRear(Node** head, int newData) {
Node* newNode = new Node(newData);
if (*head == nullptr) {
*head = newNode;
return;
}
Node* last = *head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}

// Function to print the linked list


void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}

// Function to sort the linked list using insertion sort


void insertionSort(Node** head) {
Node* S= nullptr; // Initialize sorted linked list

Node* C = *head;
while (C != nullptr) {
Node* next = current->next;
if (S == nullptr || S->data >= C->data) {
C->next = sorted;
S = current;
} else {
Node* temp = sorted;
while (temp->next != nullptr && temp->next->data < C->data) {
temp = temp->next;
}
C->next = temp->next;
temp->next = C;
}

// Update current
C = next;
}

// Update head to point to sorted linked list


*head = S;
}

int main() {
Node* head = nullptr;

// List A = {8, 9, 1, 2}
appendOnRear(&head, 8);
appendOnRear(&head, 9);
appendOnRear(&head, 1);
appendOnRear(&head, 2);

cout << "Original list: ";


printList(head);
insertionSort(&head);

cout << "Sorted list: ";


printList(head);

return 0;
}

Q5: Removal of Duplicates in Link List. You are given a Linked List. Write a Remove All
Duplicates () function which takes a list sorted in an ascending and deletes any duplicate
nodes from the list. (Ideally, the list should only be traversed once)
Example: List A=4,1,1,2,2,3,3,3} which be sorted in to List A ={4,1,2,3}
Code:
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};

// Function to add a new node at the rear (end) of the list


void appendOnRear(Node** head, int newData) {
Node* newNode = new Node(newData);
if (*head == nullptr) {
*head = newNode;
return;
}
Node* last = *head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
}

// Function to print the linked list


void printList(Node* node) {
while (node != nullptr) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}

// Function to remove duplicates from the sorted linked list


void removeAllDuplicates(Node* head) {
if (head == nullptr) {
return;
}
Node* current = head;
while (current->next != nullptr) {
if (current->data == current->next->data) {
Node* duplicate = current->next;
current->next = current->next->next;
delete duplicate;
} else {
current = current->next;
}
}
}

int main() {
Node* head = nullptr;

// List A = {4, 1, 1, 2, 2, 3, 3, 3}
appendOnRear(&head, 4);
appendOnRear(&head, 1);
appendOnRear(&head, 1);
appendOnRear(&head, 2);
appendOnRear(&head, 2);
appendOnRear(&head, 3);
appendOnRear(&head, 3);
appendOnRear(&head, 3);

cout << "Original list: ";


printList(head);

removeAllDuplicates(head);

cout << "List after removing duplicates: ";


printList(head);

return 0;
}

Q7: Theoretical Part: Explore sentinel Link list by yourself for insertion and deletion

Code:
#include <iostream>

using namespace std;


class Node {

public:

int data;

Node* next;

Node(int data = 0) { // Default value for sentinel node

this->data = data;

this->next = nullptr;

};

class SentinelList {

public:

Node* head;

SentinelList() {

head = new Node(); // Create sentinel node

// Function to add a new node at the rear (end) of the list

void appendOnRear(int newData) {

Node* newNode = new Node(newData);

Node* temp = head;

while (temp->next != nullptr) {

temp = temp->next;

temp->next = newNode;

// Function to delete a node with a specific value

void deleteNode(int value) {

Node* temp = head;

while (temp->next != nullptr) {

if (temp->next->data == value) {

Node* nodeToDelete = temp->next;

temp->next = temp->next->next;
delete nodeToDelete;

return;

temp = temp->next;

cout << "Value not found in the list" << endl;

// Function to print the linked list

void printList() {

Node* temp = head->next; // Skip sentinel node

while (temp != nullptr) {

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

temp = temp->next;

cout << endl;

};

int main() {

SentinelList list;

// List A = {8, 9, 1, 2}

list.appendOnRear(8);

list.appendOnRear(9);

list.appendOnRear(1);

list.appendOnRear(2);

cout << "Original list: ";

list.printList();

// Deleting an element

list.deleteNode(1);

cout << "List after deleting 1: ";


list.printList();

// Deleting a non-existing element

list.deleteNode(5);

cout << "List after attempting to delete 5: ";

list.printList();

return 0;

You might also like