Lists

Questions And Solutions.

2080 Chaitra

Explain array representation of list? How does it differ from dynamic list?

Solution

Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from '0' to 'n-1', where n is the size of that particular array. For example, an array with size 10 will have buckets indexed from 0 to 9.

Arrays have a fixed size set during creation. Lists are dynamic and can change in size during runtime. All elements in an array must be of the same data type. Lists can accommodate elements of different data types.

2079 Ashwin

How do you implement array to represent queue as list?

Solution

Implementing a queue using an array involves using the array to store the elements of the queue and maintaining indices for the front and rear to track the beginning and end of the queue.

Operation in queue

1. Enqueue(insert): Add new elements to the end of the queue.
   
2. Dequeue(remove): Remove the front element by shifting all remaining elements to the left.
   
3. Peek: Get the front element without removing it.
   
4. isEmpty: Check if the queue is empty.
   
5. isFull (for fixed-size arrays): Check if the queue is full.
   

Implementation in C++

#include <iostream>
using namespace std;

class Queue {
private:
    int front, rear, size;
    int* queue;

public:
    Queue(int s) {
        front = -1;
        rear = -1;
        size = s;
        queue = new int[s];
    }

    ~Queue() {
        delete[] queue;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return rear == size - 1;
    }

    void enqueue(int data) {
        if (isFull()) {
            cout << "Queue is full" << endl;
            return;
        }
        if (front == -1) {
            front = 0;
        }
        queue[rear++] = data;
        cout << "Enqueued: " << data << endl;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        cout << "Dequeued: " << queue[front] << endl;
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        return queue[front];
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return;
        }
        cout << "Queue elements: ";
        for (int i = front; i <= rear; i++) {
            cout << queue[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q(3);

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.display();
    cout << "Front element: " << q.peek() << endl;
    q.dequeue();
    q.display();
    q.enqueue(40);
    q.display();
    q.dequeue();
    q.display();

    return 0;
}

Output

Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue elements: 10 20 30
Front element: 10
Dequeued: 10
Queue elements: 20 30
Enqueued: 40
Queue elements: 20 30 40
Dequeued: 20
Queue elements: 30 40

2073 Bhadra

Differentiate between a static and dynamic list structure and write an algorithm for getnode() and freenode() of static list structure.

Solution

Algorithm for getnode by index:

1. Start at the head of the linked list.
   
2. Traverse through the list node by node.
   
3. For each node, increment the counter (starting from 0).
   
4. When the counter matches the desired index, return the node.
   
5. If you reach the end of the list (i.e., the next node is nullptr), return nullptr (indicating that the index is out of bounds).
   

Algorithm for freenode in a linked list
When freeing a node, we need to ensure that:

1. The node is removed from the list.
   
2. The memory allocated to the node is freed.
   

In a singly linked list, the freeNode operation is typically used to delete a node at a specific position (or with a specific value) by:

1. Finding the node to be deleted.
   
2. Updating the previous node's next pointer to skip the current node.
   
3. Deallocating (freeing) the memory occupied by the node.
   

2072 Ashwin

Differentiate static and dynamic implementation of list with suitable example.

Solution

Q.N. 5 Discuss the merits and demerits of contiguous list and linked list. Write algorithms to insert and delete a node after a node in a singly linked list.

Solution

Merits of Contiguous List:
1.Efficient Access
2.Simple Implementation
3.Memory Overhead.
4.Cache Efficiency

Demerits of Contiguous List: 1.Fixed Size:
2.Inefficient Insertions/Deletions
3.Wasted Space.

Merits of Linked List: 1.Dynamic Size.
2.Efficient Insertions/Deletions
3.No Wasted Space.
4.Flexible Memory Usage.

Demerits of Contiguous List: 1.Extra Memory for Pointers.
2.Inefficient excess.
3.complex implementation

Algorithm for the insertion of new node at the beginning in SLL:
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

Algorithm for the deletion of new node at the beginning in SLL:

Step 1 - Check whether the list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminates the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4 - Check whether the list is having only one node (temp → next == NULL)
Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.

Q.N. 6 Explain array implementation of list with suitable example. Consider an array to represent the list. Write an algorithm to insert an element at i^th position in the list.

Solution

Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from '0' to 'n-1', where n is the size of that particular array. For example, an array with size 10 will have buckets indexed from 0 to 9.

Algorithm to insert an element at ith position:

Step 1- Create a newNode with the given value.
Step 2- Check whether list is Empty (head == NULL)
Step 3- If it is Empty then, set newNode → next = NULL and head = newNode.
Step 4- If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5- Keep moving the temp to its next node until it reaches the node after which we want to insert the newNode (until temp1 → data is equal to location, here location is the node value after which we want to insert the newNode).
Step 6- Every time check whether temp is reached to the last node or not. If it is reached to the last node then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the function. Otherwise, move the temp to the next node.
Step 7- Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'