Tutorial 11 and 12 Code:
---Doubly Linked List in c++
#include <iostream>
// Node class to represent each element in the linked list
class Node {
public:
int data; // Data stored in the node
Node* next; // Pointer to the next node
Node* prev; // Pointer to the previous node
// Constructor to initialize the node with data and nullptr
Node(int data) {
this->data = data;
next = nullptr;
prev = nullptr;
}
};
// Linked list class
class DoublyLinkedList {
private:
Node* head; // Pointer to the first node (head) of the list
public:
// Constructor to initialize an empty linked list
DoublyLinkedList() {
head = nullptr;
}
// Destructor to free memory allocated for nodes
~DoublyLinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
// Function to insert a new node at the beginning of the list
void insertAtBeginning(int data)
{
Node* newNode = new Node(data);
if (head != nullptr)
head->prev = newNode;
newNode->next = head;
head = newNode;
}
// Function to insert a new node at the end of the list
void insertAtEnd(int data)
{
Node* newNode = new Node(data);
if (head == nullptr)
{
head = newNode;
return;
}
Node* current = head;
while (current->next != nullptr)
{
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
// Function to insert a new node at a given position
void insertAtPosition(int data, int position)
{
if (position < 0)
return;
Node* newNode = new Node(data);
if (position == 0)
{
newNode->next = head;
if (head != nullptr)
head->prev = newNode;
head = newNode;
return;
}
Node* current = head;
int currentPosition = 0;
while (currentPosition < position - 1 && current != nullptr)
{
current = current->next;
currentPosition++;
}
if (current == nullptr)
return;
newNode->next = current->next;
newNode->prev = current;
if (current->next != nullptr)
current->next->prev = newNode;
current->next = newNode;
}
// Function to delete the first occurrence of a node with given data
void deleteNode(int data)
{
if (head == nullptr)
return;
if (head->data == data)
{
Node* temp = head;
head = head->next;
if (head != nullptr)
head->prev = nullptr;
delete temp;
return;
}
Node* current = head;
while (current != nullptr)
{
if (current->data == data)
{
if (current->prev != nullptr)
current->prev->next = current->next;
if (current->next != nullptr)
current->next->prev = current->prev;
delete current;
return;
}
current = current->next;
}
}
// Function to search for a node with given data
bool search(int data) {
Node* current = head;
while (current != nullptr)
{
if (current->data == data) {
return true; // Node found
}
current = current->next;
}
return false; // Node not found
}
// Function to display the elements of the linked list
void display() {
Node* current = head;
std::cout << "Linked List Elements: ";
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList list;
int choice, data, position;
do {
std::cout << "\nChoose operation:\n";
std::cout << "1. Insert at beginning\n";
std::cout << "2. Insert at end\n";
std::cout << "3. Insert at position\n";
std::cout << "4. Delete node\n";
std::cout << "5. Search node\n";
std::cout << "6. Display list\n";
std::cout << "0. Exit\n";
std::cout << "Enter your choice: ";
std::cin >> choice;
switch (choice) {
case 1:
std::cout << "Enter data to insert at the beginning: ";
std::cin >> data;
list.insertAtBeginning(data);
break;
case 2:
std::cout << "Enter data to insert at the end: ";
std::cin >> data;
list.insertAtEnd(data);
break;
case 3:
std::cout << "Enter data to insert: ";
std::cin >> data;
std::cout << "Enter position to insert: ";
std::cin >> position;
list.insertAtPosition(data, position);
break;
case 4:
std::cout << "Enter data to delete: ";
std::cin >> data;
list.deleteNode(data);
break;
case 5:
std::cout << "Enter data to search for: ";
std::cin >> data;
if (list.search(data)) {
std::cout << "Node with data " << data << " found in the list.\n";
} else {
std::cout << "Node with data " << data << " not found in the list.\n";
}
break;
case 6:
list.display();
break;
case 0:
std::cout << "Exiting...\n";
break;
default:
std::cout << "Invalid choice. Please try again.\n";
}
} while (choice != 0);
return 0;
}
----------- Singly Circular Linked List
#include <iostream>
// Node class to represent each element in the linked list
class Node {
public:
int data; // Data stored in the node
Node* next; // Pointer to the next node
// Constructor to initialize the node with data and nullptr
Node(int data)
{
this->data = data;
next = nullptr;
}
};
// Linked list class
class CircularSinglyLinkedList {
private:
Node* head; // Pointer to the head node of the list
public:
// Constructor to initialize an empty linked list
CircularSinglyLinkedList() {
head = nullptr;
}
// Destructor to free memory allocated for nodes
~CircularSinglyLinkedList()
{
if (head == nullptr)
return;
Node* current = head->next;
while (current != head)
{
Node* temp = current;
current = current->next;
delete temp;
}
delete head;
}
// Function to insert a new node at the beginning of the list
void insertAtBeginning(int data)
{
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
newNode->next = head;
} else {
Node* current = head;
while (current->next != head)
{
current = current->next;
}
newNode->next = head;
head = newNode;
current->next = head;
}
}
// Function to insert a new node at the end of the list
void insertAtEnd(int data)
{
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
newNode->next = head;
} else {
Node* current = head;
while (current->next != head) {
current = current->next;
}
current->next = newNode;
newNode->next = head;
}
}
// Function to delete the first occurrence of a node with given data
void deleteNode(int data)
{
if (head == nullptr)
return;
Node* current = head;
Node* prev = nullptr;
while (current->next != head) {
if (current->data == data)
{
if (prev == nullptr) { // If the node to be deleted is the head
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = head->next;
delete head;
head = temp->next;
return;
} else {
prev->next = current->next;
delete current;
return;
}
}
prev = current;
current = current->next;
}
// Check if the last node needs to be deleted
if (current->data == data)
{
if (prev == nullptr) { // If the node to be deleted is the only node
delete head;
head = nullptr;
} else {
prev->next = head;
delete current;
}
}
}
// Function to search for a node with given data
bool search(int data)
{
if (head == nullptr)
return false;
Node* current = head;
do {
if (current->data == data) {
return true; // Node found
}
current = current->next;
} while (current != head);
return false; // Node not found
}
// Function to display the elements of the linked list
void display() {
if (head == nullptr) {
std::cout << "Empty list" << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data << " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
};
int main() {
CircularSinglyLinkedList list;
int choice, data;
do {
std::cout << "\nChoose operation:\n";
std::cout << "1. Insert at beginning\n";
std::cout << "2. Insert at end\n";
std::cout << "3. Delete node\n";
std::cout << "4. Search node\n";
std::cout << "5. Display list\n";
std::cout << "0. Exit\n";
std::cout << "Enter your choice: ";
std::cin >> choice;
switch (choice) {
case 1:
std::cout << "Enter data to insert at the beginning: ";
std::cin >> data;
list.insertAtBeginning(data);
break;
case 2:
std::cout << "Enter data to insert at the end: ";
std::cin >> data;
list.insertAtEnd(data);
break;
case 3:
std::cout << "Enter data to delete: ";
std::cin >> data;
list.deleteNode(data);
break;
case 4:
std::cout << "Enter data to search for: ";
std::cin >> data;
if (list.search(data)) {
std::cout << "Node with data " << data << " found in the list.\n";
} else {
std::cout << "Node with data " << data << " not found in the list.\n";
}
break;
case 5:
list.display();
break;
case 0:
std::cout << "Exiting...\n";
break;
default:
std::cout << "Invalid choice. Please try again.\n";
}
} while (choice != 0);
return 0;
}
----------- Doubly Circular Linked List
No comments:
Post a Comment
Fell free to write your query in comment. Your Comments will be fully encouraged.