Tutorial 11 and 12 Code

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


#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 DoublyCircularLinkedList {
private:
    Node* head; // Pointer to the head node of the list

public:
    // Constructor to initialize an empty linked list
    DoublyCircularLinkedList() {
        head = nullptr;
    }

    // Destructor to free memory allocated for nodes
    ~DoublyCircularLinkedList() {
        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;
            head->next = head;
            head->prev = head;
        } else {
            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
            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;
            head->next = head;
            head->prev = head;
        } else {
            newNode->next = head;
            newNode->prev = head->prev;
            head->prev->next = newNode;
            head->prev = newNode;
        }
    }

    // Function to delete the first occurrence of a node with given data
    void deleteNode(int data) {
        if (head == nullptr)
            return;

        Node* current = head;
        do {
            if (current->data == data) {
                if (current == head) { // If the node to be deleted is the head
                    if (head->next == head) { // If head is the only node
                        delete head;
                        head = nullptr;
                        return;
                    } else {
                        head->prev->next = head->next;
                        head->next->prev = head->prev;
                        Node* temp = head;
                        head = head->next;
                        delete temp;
                        return;
                    }
                } else { // If the node to be deleted is not the head
                    current->prev->next = current->next;
                    current->next->prev = current->prev;
                    delete current;
                    return;
                }
            }
            current = current->next;
        } while (current != head);
    }

    // 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() {
    DoublyCircularLinkedList 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;
}

No comments:

Post a Comment

Fell free to write your query in comment. Your Comments will be fully encouraged.