Assignment: Linked List | DSA in C++ - Software Development PDF Download

Multiple Choice Questions (MCQs)

Q.1. Which of the following is true about a linked list?

(a) It is a linear data structure
(b) It stores elements in contiguous memory locations
(c) It allows constant-time access to any element
(d) It supports random access to elements

Ans. (a)

Q.2. Which of the following is an advantage of a linked list over an array?
(a) Constant-time access to any element
(b) Efficient memory utilization
(c) Supports random access to elements
(d) Easy implementation of sorting algorithms

Ans. (b)

Q.3. Which of the following is a disadvantage of a singly linked list?
(a) Requires contiguous memory allocation
(b) Takes up more memory than an array
(c) Cannot be traversed in both directions
(d) Supports efficient deletion of elements

Ans. (c)

Q.4. What is the time complexity for inserting a node at the beginning of a linked list?
(a) O(1)
(b) O(log n)
(c) O(n)
(d) O(n²)

Ans. (a)

Q.5. Which of the following is true about the recursive approach to find the length of a linked list?

(a) It has a time complexity of O(n)
(b) It requires additional space for recursion stack
(c) It is more efficient than the iterative approach
(d) It is not possible to find the length recursively

Ans. (a)

High Order Thinking Questions (HOTS)

Q.1. Write a function in C++ to insert a node at the end of a singly linked list.

void insertAtEnd(Node* &head, int data) {

    Node* newNode = new Node(data);

    if (head == nullptr) {

        head = newNode;

    } else {

        Node* current = head;

        while (current->next != nullptr) {

            current = current->next;

        }

        current->next = newNode;

    }

}

Q.2. How can you implement a circular linked list using a singly linked list?

To implement a circular linked list using a singly linked list, we need to make the last node's next pointer point to the head node instead of nullptr.

Q.3. Write a function in C++ to reverse a linked list iteratively.

void reverseLinkedListIterative(Node* &head) {

    Node* prev = nullptr;

    Node* current = head;

    Node* next = nullptr;

        while (current != nullptr) {

        next = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

        head = prev;

}

Q.4. Explain the concept of a doubly linked list and its advantages over a singly linked list.

A doubly linked list is a type of linked list in which each node contains references (links) to both the previous and next nodes. It allows traversal in both directions, which simplifies certain operations like deletion. However, it requires additional memory to store the previous pointers.

Q.5. Write a function in C++ to delete a node with a given key from a singly linked list.

void deleteNode(Node* &head, int key) {

    if (head == nullptr) {

        return;

    }

        if (head->data == key) {

        Node* temp = head;

        head = head->next;

        delete temp;

        return;

    }

        Node* current = head;

    Node* prev = nullptr;

        while (current != nullptr && current->data != key) {

        prev = current;

        current = current->next;

    }

        if (current == nullptr) {

        return;

    }

        prev->next = current->next;

    delete current;

}

Fill in the Blanks:

1. In a linked list, each node contains a data element and a ________________ to the next node.

In a linked list, each node contains a data element and a pointer/link to the next node.

2. The time complexity for searching an element in a linked list using an iterative approach is ________________.

The time complexity for searching an element in a linked list using an iterative approach is O(n), where n is the number of nodes in the linked list.

3. The time complexity for finding the length of a linked list recursively is ________________.

The time complexity for finding the length of a linked list recursively is O(n), where n is the number of nodes in the linked list.

4. In a circular linked list, the last node's next pointer points to the ________________.

In a circular linked list, the last node's next pointer points to the head node.

5. The time complexity for reversing a linked list iteratively is ________________.

The time complexity for reversing a linked list iteratively is O(n), where n is the number of nodes in the linked list.

True or False

1. Linked list allows efficient insertion and deletion of elements at any position. (True/False)

True

2. Singly linked list requires less memory compared to an array. (True/False)

True

3. Doubly linked list can be traversed in both directions. (True/False)

True

4. Searching an element in a linked list using a recursive approach requires additional space for recursion stack. (True/False)

True

5. Reversing a linked list using a recursive approach is more efficient than the iterative approach. (True/False)

False

Hands-On Questions

Q.1. Write a C++ program to create a singly linked list with 5 nodes and display its elements.

#include <iostream>

struct Node {

    int data;

    Node* next;

        Node(int value) : data(value), next(nullptr) {}

};

void displayLinkedList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

}

int main() {

    Node* head = nullptr;

    for (int i = 1; i <= 5; i++) {

        Node* newNode = new Node(i);

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* current = head;

            while (current->next != nullptr) {

                current = current->next;

            }

            current->next = newNode;

        }

    }

        displayLinkedList(head);

        return 0;

}

Q.2. Write a C++ program to find the nth node from the end of a singly linked list.

#include <iostream>

struct Node {

    int data;

    Node* next;

        Node(int value) : data(value), next(nullptr) {}

};

Node* getNthNodeFromEnd(Node* head, int n) {

    Node* fast = head;

    Node* slow = head;

        for (int i = 0; i < n; i++) {

        if (fast == nullptr) {

            return nullptr; // Invalid position

        }

        fast = fast->next;

    }

        while (fast != nullptr) {

        fast = fast->next;

        slow = slow->next;

    }

        return slow;

}

int main() {

    Node* head = nullptr;

    for (int i = 1; i <= 5; i++) {

        Node* newNode = new Node(i);

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* current = head;

            while (current->next != nullptr) {

                current = current->next;

            }

            current->next = newNode;

        }

    }

        int n = 3;

    Node* nthNode = getNthNodeFromEnd(head, n);

    if (nthNode != nullptr) {

        std::cout << "Node at position " << n << " from the end: " << nthNode->data << std::endl;

    } else {

        std::cout << "Invalid position." << std::endl;

    }

        return 0;

}

Q.3. Write a C++ program to insert a node at a given position in a singly linked list.

#include <iostream>

struct Node {

    int data;

    Node* next;

        Node(int value) : data(value), next(nullptr) {}

};

void insertAtPosition(Node* &head, int data, int position) {

    Node* newNode = new Node(data);

        if (position == 1) {

        newNode->next = head;

        head = newNode;

        return;

    }

        Node* current = head;

    int count = 1;

        while (current != nullptr && count < position - 1) {

        current = current->next;

        count++;

    }

        if (current == nullptr) {

        return; // Invalid position

    }

        newNode->next = current->next;

    current->next = newNode;

}

void displayLinkedList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

}

int main() {

    Node* head = nullptr;

    for (int i = 1; i <= 5; i++) {

        Node* newNode = new Node(i);

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* current = head;

            while (current->next != nullptr) {

                current = current->next;

            }

            current->next = newNode;

        }

    }

        int position = 3;

    int data = 10;

    insertAtPosition(head, data, position);

        displayLinkedList(head);

        return 0;

}

Q.4. Write a C++ program to search for an element in a singly linked list using recursion.

#include <iostream>

struct Node {

    int data;

    Node* next;

        Node(int value) : data(value), next(nullptr) {}

};

bool searchElementRecursive(Node* head, int key) {

    if (head == nullptr) {

        return false;

    }

        if (head->data == key) {

        return true;

    }

        return searchElementRecursive(head->next, key);

}

int main() {

    Node* head = nullptr;

    for (int i = 1; i <= 5; i++) {

        Node* newNode = new Node(i);

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* current = head;

            while (current->next != nullptr) {

                current = current->next;

            }

            current->next = newNode;

        }

    }

        int key = 3;

    bool found = searchElementRecursive(head, key);

        if (found) {

        std::cout << "Element " << key << " found in the linked list." << std::endl;

    } else {

        std::cout << "Element " << key << " not found in the linked list." << std::endl;

    }

        return 0;

}

Q.5. Write a C++ program to reverse a doubly linked list.

#include <iostream>

struct Node {

    int data;

    Node* prev;

    Node* next;

        Node(int value) : data(value), prev(nullptr), next(nullptr) {}

};

void reverseDoublyLinkedList(Node* &head) {

    Node* current = head;

    Node* temp = nullptr;

        while (current != nullptr) {

        temp = current->prev;

        current->prev = current->next;

        current->next = temp;

        current = current->prev;

    }

        if (temp != nullptr) {

        head = temp->prev;

    }

}

void displayDoublyLinkedList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

}

int main() {

    Node* head = nullptr;

    for (int i = 1; i <= 5; i++) {

        Node* newNode = new Node(i);

        if (head == nullptr) {

            head = newNode;

        } else {

            Node* current = head;

            while (current->next != nullptr) {

                current = current->next;

            }

            current->next = newNode;

            newNode->prev = current;

        }

    }

        displayDoublyLinkedList(head);

    std::cout << std::endl;

        reverseDoublyLinkedList(head);

        displayDoublyLinkedList(head);

        return 0;

}