Nafil.DSA

#include <iostream>
#include<stdio.h>
#include<iomanip>
#include<cmath>
#include<string>
#include<algorithm>
#include<bitset>
#include<numeric>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<list>

#include<cstdlib>

using namespace std;

// Structure for a singly linked list node
struct SinglyNode {
    int data;
    SinglyNode* next;
};

// Create a new node
SinglyNode* createSinglyNode(int value) {
    SinglyNode* newNode = (SinglyNode*)malloc(sizeof(SinglyNode));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insert at the beginning
void insertSinglyAtBeginning(SinglyNode** head, int value) {
    SinglyNode* newNode = createSinglyNode(value);
    newNode->next = *head;
    *head = newNode;
}

// Insert at the end
void insertSinglyAtEnd(SinglyNode** head, int value) {
    SinglyNode* newNode = createSinglyNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    SinglyNode* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

// Insert at a specific position
void insertSinglyAtPosition(SinglyNode** head, int value, int position) {
    if (position == 1) {
        insertSinglyAtBeginning(head, value);
        return;
    }
    SinglyNode* newNode = createSinglyNode(value);
    SinglyNode* temp = *head;
    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        cout << "Position out of bounds\n";
        free(newNode);
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

// Delete the first node
void deleteSinglyFirst(SinglyNode** head) {
    if (*head == NULL) return;
    SinglyNode* temp = *head;
    *head = (*head)->next;
    free(temp);
}

// Delete the last node
void deleteSinglyLast(SinglyNode** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    SinglyNode* temp = *head;
    while (temp->next->next != NULL)
        temp = temp->next;
    free(temp->next);
    temp->next = NULL;
}

// Delete at a specific position
void deleteSinglyAtPosition(SinglyNode** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteSinglyFirst(head);
        return;
    }
    SinglyNode* temp = *head;
    SinglyNode* prev = NULL;
    for (int i = 1; temp != NULL && i < position; i++) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

// Display the list
void displaySingly(SinglyNode* head) {
    while (head != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL\n";
}

// Structure for a doubly linked list node
struct DoublyNode {
    int data;
    DoublyNode* next;
    DoublyNode* prev;
};

// Create a new node
DoublyNode* createDoublyNode(int value) {
    DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
    newNode->data = value;
    newNode->next = newNode->prev = NULL;
    return newNode;
}

// Insert at the beginning
void insertDoublyAtBeginning(DoublyNode** head, int value) {
    DoublyNode* newNode = createDoublyNode(value);
    newNode->next = *head;
    if (*head != NULL) (*head)->prev = newNode;
    *head = newNode;
}

// Insert at the end
void insertDoublyAtEnd(DoublyNode** head, int value) {
    DoublyNode* newNode = createDoublyNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    DoublyNode* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

// Insert at a specific position
void insertDoublyAtPosition(DoublyNode** head, int value, int position) {
    if (position == 1) {
        insertDoublyAtBeginning(head, value);
        return;
    }
    DoublyNode* newNode = createDoublyNode(value);
    DoublyNode* temp = *head;
    for (int i = 1; temp != NULL && i < position - 1; i++)
        temp = temp->next;
    if (temp == NULL) return;
    newNode->next = temp->next;
    if (temp->next != NULL)
        temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}

// Delete the first node
void deleteDoublyFirst(DoublyNode** head) {
    if (*head == NULL) return;
    DoublyNode* temp = *head;
    *head = (*head)->next;
    if (*head != NULL) (*head)->prev = NULL;
    free(temp);
}

// Delete the last node
void deleteDoublyLast(DoublyNode** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    DoublyNode* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->prev->next = NULL;
    free(temp);
}

// Delete at a specific position
void deleteDoublyAtPosition(DoublyNode** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteDoublyFirst(head);
        return;
    }
    DoublyNode* temp = *head;
    for (int i = 1; temp != NULL && i < position; i++)
        temp = temp->next;
    if (temp == NULL) return;
    if (temp->next != NULL)
        temp->next->prev = temp->prev;
    if (temp->prev != NULL)
        temp->prev->next = temp->next;
    free(temp);
}

// Display the list
void displayDoubly(DoublyNode* head) {
    while (head != NULL) {
        cout << head->data << " <-> ";
        head = head->next;
    }
    cout << "NULL\n";
}

// Structure for a circular linked list node
struct CircularNode {
    int data;
    CircularNode* next;
};

// Create a new node
CircularNode* createCircularNode(int value) {
    CircularNode* newNode = (CircularNode*)malloc(sizeof(CircularNode));
    newNode->data = value;
    newNode->next = newNode;
    return newNode;
}

// Insert at the beginning
void insertCircularAtBeginning(CircularNode** head, int value) {
    CircularNode* newNode = createCircularNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    CircularNode* temp = *head;
    while (temp->next != *head)
        temp = temp->next;
    newNode->next = *head;
    temp->next = newNode;
    *head = newNode;
}

// Insert at the end
void insertCircularAtEnd(CircularNode** head, int value) {
    CircularNode* newNode = createCircularNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    CircularNode* temp = *head;
    while (temp->next != *head)
        temp = temp->next;
    temp->next = newNode;
    newNode->next = *head;
}

// Insert at a specific position
void insertCircularAtPosition(CircularNode** head, int value, int position) {
    if (position == 1) {
        insertCircularAtBeginning(head, value);
        return;
    }
    CircularNode* newNode = createCircularNode(value);
    CircularNode* temp = *head;
    for (int i = 1; temp->next != *head && i < position - 1; i++)
        temp = temp->next;
    newNode->next = temp->next;
    temp->next = newNode;
}

// Delete the first node
void deleteCircularFirst(CircularNode** head) {
    if (*head == NULL) return;
    CircularNode* temp = *head;
    CircularNode* last = *head;
    while (last->next != *head)
        last = last->next;
    if (*head == last) {
        free(*head);
        *head = NULL;
        return;
    }
    last->next = (*head)->next;
    *head = (*head)->next;
    free(temp);
}

// Delete the last node
void deleteCircularLast(CircularNode** head) {
    if (*head == NULL) return;
    CircularNode* temp = *head;
    CircularNode* prev = NULL;
    while (temp->next != *head) {
        prev = temp;
        temp = temp->next;
    }
    if (prev == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    prev->next = *head;
    free(temp);
}

// Delete at a specific position
void deleteCircularAtPosition(CircularNode** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteCircularFirst(head);
        return;
    }
    CircularNode* temp = *head;
    CircularNode* prev = NULL;
    for (int i = 1; temp->next != *head && i < position; i++) {
        prev = temp;
        temp = temp->next;
    }
    if (temp->next == *head && position > 1) return;
    prev->next = temp->next;
    free(temp);
}

// Display the list
void displayCircular(CircularNode* head) {
    if (head == NULL) return;
    CircularNode* temp = head;
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    cout << "(head)\n";
}

// Find data in Circular Linked List
bool findData(CircularNode** head, int value) {
    if (*head == NULL) return false;
    CircularNode* temp = *head;
    do {
        if (temp->data == value) return true;
        temp = temp->next;
    } while (temp != *head);
    return false;
}

// Define the structure for a node to count data and node number
struct Node {
    int intData;
    char charData;
    float floatData;
    struct Node* next;
};

// Function to count nodes in the linked list
int countNodes(struct Node* head) {
    int count = 0;
    struct Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

// Function to create a new node
struct Node* createNode(int i, char c, float f) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->intData = i;
    newNode->charData = c;
    newNode->floatData = f;
    newNode->next = NULL;
    return newNode;
}

// Function to append a node to the linked list
void appendNode(struct Node** head, int i, char c, float f) {
    struct Node* newNode = createNode(i, c, f);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Function to print the list
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("(%d, %c, %.2f) -> ", temp->intData, temp->charData, temp->floatData);
        temp = temp->next;
    }
    printf("NULL\n");
}


// Structure for Stack Node
struct StackNode {
    int data;
    StackNode* next;
};

// Structure for Queue Node
struct QueueNode {
    int data;
    QueueNode* next;
};

// Stack Functions
StackNode* stackTop = NULL; // Stack top pointer

void push(int value) {
    StackNode* newNode = new StackNode();
    newNode->data = value;
    newNode->next = stackTop;
    stackTop = newNode;
    cout << "Pushed to Stack: " << value << endl;
}

void pop() {
    if (stackTop == NULL) {
        cout << "Stack is empty!\n";
        return;
    }
    StackNode* temp = stackTop;
    cout << "Popped from Stack: " << temp->data << endl;
    stackTop = stackTop->next;
    free(temp);
}

// Queue Functions
QueueNode* front = NULL; // Queue front pointer
QueueNode* rear = NULL;  // Queue rear pointer

void enqueue(int value) {
    QueueNode* newNode = new QueueNode();
    newNode->data = value;
    newNode->next = NULL;
    
    if (rear == NULL) { // If queue is empty
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    cout << "Enqueued to Queue: " << value << endl;
}

void dequeue() {
    if (front == NULL) {
        cout << "Queue is empty!\n";
        return;
    }
    QueueNode* temp = front;
    cout << "Dequeued from Queue: " << temp->data << endl;
    front = front->next;
    
    if (front == NULL) {
        rear = NULL; // If queue becomes empty
    }
    free(temp);
}

// Display Stack
void displayStack() {
    cout << "Final Stack: ";
    StackNode* temp = stackTop;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

// Display Queue
void displayQueue() {
    cout << "Final Queue: ";
    QueueNode* temp = front;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}


// Main function
int main() {
    SinglyNode* singlyHead = NULL;
    int value, position;

    // User input for Singly Linked List
    cout << "Enter value to insert at beginning: ";
    cin >> value;
    insertSinglyAtBeginning(&singlyHead, value);

    cout << "Enter value to insert at end: ";
    cin >> value;
    insertSinglyAtEnd(&singlyHead, value);

    cout << "Enter value and position to insert in Singly Linked List: ";
    cin >> value >> position;
    insertSinglyAtPosition(&singlyHead, value, position);

    cout << "Singly Linked List: ";
    displaySingly(singlyHead);

    deleteSinglyFirst(&singlyHead);
    deleteSinglyLast(&singlyHead);
    cout << "Singly Linked List after deletions: ";
    displaySingly(singlyHead);

    cout << "Enter position to delete in Singly Linked List: ";
    cin >> position;
    deleteSinglyAtPosition(&singlyHead, position);
    cout << "Singly Linked List after deletion at position " << position << ": ";
    displaySingly(singlyHead);

    DoublyNode* doublyHead = NULL;

    // User input for Doubly Linked List
    cout << "Enter value to insert at beginning of Doubly Linked List: ";
    cin >> value;
    insertDoublyAtBeginning(&doublyHead, value);

    cout << "Enter value to insert at end of Doubly Linked List: ";
    cin >> value;
    insertDoublyAtEnd(&doublyHead, value);

    cout << "Enter value and position to insert in Doubly Linked List: ";
    cin >> value >> position;
    insertDoublyAtPosition(&doublyHead, value, position);

    cout << "Doubly Linked List: ";
    displayDoubly(doublyHead);

    deleteDoublyFirst(&doublyHead);
    deleteDoublyLast(&doublyHead);
    cout << "Doubly Linked List After Deletation: ";
    displayDoubly(doublyHead);

    cout << "Enter position to delete from Doubly Linked List: ";
    cin >> position;
    deleteDoublyAtPosition(&doublyHead, position);

    cout << "Doubly Linked List after deletion at position " << position << ": ";
    displayDoubly(doublyHead);

    CircularNode* circularHead = NULL;

    // User input for Circular Linked List
    cout << "Enter value to insert at beginning of Circular Linked List: ";
    cin >> value;
    insertCircularAtBeginning(&circularHead, value);

    cout << "Enter value to insert at end of Circular Linked List: ";
    cin >> value;
    insertCircularAtEnd(&circularHead, value);

    cout << "Enter value and position to insert in Circular Linked List: ";
    cin >> value >> position;
    insertCircularAtPosition(&circularHead, value, position);

    cout << "Circular Linked List: ";
    displayCircular(circularHead);

    deleteCircularFirst(&circularHead);
    deleteCircularLast(&circularHead);
    cout << "Circular Linked List After Deletation: ";
    displayCircular(circularHead);

    cout << "Enter position to delete from Circular Linked List: ";
    cin >> position;
    deleteCircularAtPosition(&circularHead, position);

    cout << "Circular Linked List after deletion at position " << position << ": ";
    displayCircular(circularHead);

    cout << "Enter value to find in Circular Linked List: ";
    cin >> value;
    if (findData(&circularHead, value)) {
        cout << "Value " << value << " found in Circular Linked List.\n";
    } else {
        cout << "Value " << value << " not found in Circular Linked List.\n";
    }

    struct Node* head = NULL;

    // Creating a linked list with some nodes
    appendNode(&head, 10, 'A', 1.1);
    appendNode(&head, 20, 'B', 2.2);
    appendNode(&head, 30, 'C', 3.3);

    // Counting nodes and data
    int nodeCount = countNodes(head);
    int dataCount = nodeCount * 3; // Each node has 3 data elements

    // Printing the results
    printf("Linked List: ");
    printList(head);
    printf("Number of Nodes: %d\n", nodeCount);
    printf("Total Data Elements: %d\n", dataCount);

    int choice, value2;
    
    while (true) {
        cout << "\nChoose an operation:\n";
        cout << "1. Push to Stack\n";
        cout << "2. Pop from Stack\n";
        cout << "3. Enqueue to Queue\n";
        cout << "4. Dequeue from Queue\n";
        cout << "5. Display Stack\n";
        cout << "6. Display Queue\n";
        cout << "7. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        if (choice == 1) {
            cout << "Enter value to push: ";
            cin >> value2;
            push(value2);
        } 
        else if (choice == 2) {
            pop();
        } 
        else if (choice == 3) {
            cout << "Enter value to enqueue: ";
            cin >> value2;
            enqueue(value2);
        } 
        else if (choice == 4) {
            dequeue();
        } 
        else if (choice == 5) {
            displayStack();
        } 
        else if (choice == 6) {
            displayQueue();
        } 
        else if (choice == 7) {
            cout << "Exiting program...\n";
            break;
        } 
        else {
            cout << "Invalid choice! Try again.\n";
        }
    }

    return 0;

    //NAFI ARDUL RIDIN
}