Nafil.DSA
LinkList: singly, doubly,circuler. Search, count. Stack: PushPop Queue: EnqueueDequeue user input implementation.unknown
c_cpp
2 months ago
17 kB
11
Indexable
#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 }
Editor is loading...
Leave a Comment