Test: Linked List - Computer Science Engineering (CSE) MCQ

fun1() prints the given Linked List in reverse manner. For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1. 

Both Merge sort and Insertion sort can be used for linked lists.

The slow random-access performance of a linked list makes other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Since worst case time complexity of Merge Sort is O(nLogn) and Insertion sort is O(n²), merge sort is preferred.

*head_ref = prev;

At the end of while loop, the prev pointer points to the last node of original linked list. We need to change *head_ref so that the head pointer now starts pointing to the last node.

See the following complete running program.

#include<stdio.h>
#include<stdlib.h>
   
/* Link list node */
struct node
{
    int data;
    struct node* next;
};
   
/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    *head_ref = prev;
}
   
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
              
    /* put in the data  */
    new_node->data  = new_data;
                  
    /* link the old list off the new node */
    new_node->next = (*head_ref);    
          
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
   
/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while(temp != NULL)
    {
        printf("%d  ", temp->data);    
        temp = temp->next;  
    }
}    
   
/* Drier program to test above function*/
int main()
{
    /* Start with the empty list */
    struct node* head = NULL;
     
     push(&head, 20);
     push(&head, 4);
     push(&head, 15); 
     push(&head, 85);      
       
     printList(head);    
     reverse(&head);                      
     printf("\n Reversed Linked list \n");
     printList(head);    
     return 0;
}

fun() prints alternate nodes of the given Linked List, first from head to end, and then from end to head. If Linked List has even number of nodes, then skips the last node.

The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

1. Union:

To compute the union of two sets represented as linked lists:

• Traverse each linked list and insert elements into a new list, ensuring no duplicates.
• This requires $O(n^2)$ in the worst case if we need to check for duplicates by comparing each new element to all existing elements in the result list.

2. Intersection:

To compute the intersection of two sets:

• For each element in the first linked list, check if it exists in the second linked list.
• Since checking for membership in a linked list takes $O(n)$, the total time complexity is $O(n \cdot m)$, where $n$ and $m$ are the sizes of the two lists.
• This is slower than union because it involves repeated membership checks.

3. Membership:

To check if an element exists in the set:

• Traverse the linked list to search for the element.
• This is a linear operation, $O(n)$, where $n$ is the size of the list.

4. Cardinality:

To determine the number of elements in the set:

• Traverse the linked list and count the elements.
• This is a single traversal operation, $O(n)$.

Comparison:

• Union and Intersection involve operations over two lists.
• Membership and Cardinality work with a single list.
• Among these, Intersection is the slowest because it requires repeated membership checks, making it $O(n \cdot m)$, which is typically more computationally expensive than union's $O(n^2)$ in most implementations.

Conclusion:

The intersection operation and union is the slowest when sets are represented as linked lists.

The function f() works as follows
1) If linked list is empty return 1
2) Else If linked list has only one element return 1
3) Else if node->data is smaller than equal to node->next->data and same thing holds for rest of the list then return 1
4) Else return 0

Answer is not “(b) front node”, as we can not get rear from front in O(1), but if p is rear we can implement both enQueue and deQueue in O(1) because from rear we can get front in O(1). Below are sample functions. Note that these functions are just sample are not working. Code to handle base cases is missing.

/* p is pointer to address of rear (double pointer).  This function adds new 

   node after rear and updates rear which is *p to point to new node  */

void  enQueue(struct node **p, struct node *new_node)

{

    /* Missing code to handle base cases like *p is NULL */

     new_node->next = (*p)->next;

     (*p)->next = new_node;

     (*p) = new_node /* new is now rear */

     /* Note that p->next is again front and  p is rear */

 }

/* p is pointer to rear. This function removes the front element and 

    returns the dequeued element from the queue */

struct node *deQueue(struct node *p)

{

    /* Missing code to handle base cases like p is NULL,

        p->next is NULL,...  etc */

    struct node *temp = p->next;

    p->next = p->next->next;

    return temp;

    /* Note that p->next is again front and  p is rear */

}

Following are simple steps.

    struct node *temp  = X->next;
    X->data  = temp->data;
    X->next  = temp->next;
    free(temp); 

a) Can be done in O(1) time by deleting memory and changing the first pointer.

b) Can be done in O(1) time, see push()

c) Delete the last element requires pointer to previous of last, which can only be obtained by traversing the list.

d) Can be done in O(1) by changing next of last and then last.

To delete node x, we should find out the previous node to the x. To find the previous nodes to the x will take O(n).
Therefore it takes O(n).

The time complexity of decrease-key operation is Θ(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take Θ(N) time and since there are Θ(N) decrease-key operations, the time complexity becomes O(N²).

Singly linked list cannot be answer because we cannot find last element of a singly linked list in O(1) time.

Doubly linked list cannot also not be answer because of the same reason as singly linked list.

i -STACK is the data structure that follows Last In First Out (LIFO) or First In Last Out (FILO) order, in which the element which is inserted at last is removed out first.

ii – Implementing LISTS on linked lists is more efficient than implementing it on an array for almost all the basic LIST operations because the insertion and deletion of elements can be done in O(1) in Linked List but it takes O(N) time in Arrays.

iii- Implementing QUEUES on a circular array is more efficient than implementing it on a linear array with two indices because using circular arrays, it takes less space and can reuse it again.

iv – QUEUE is the data structure that follows First In First Out (FIFO) or Last In Last Out (LILO) order, in which the element which is inserted first is removed first.

only (ii) and (iii) are TRUE.
Option (A) is correct.

For Enqueue operation, performs in constant amount of time (i.e., Θ(1)), because it modifies only two pointers, i.e.,

Create a Node P.
P-->Data = Data
P-->Next = Head
Head = P
For Dequeue operation, we need address of second last node of single linked list to make NULL of its next pointer. Since we can not access its previous node in singly linked list, so need to traverse entire linked list to get second last node of linked list, i.e.,

temp = head;
 While( temp-Next-->Next != NULL){
        temp = temp-Next;
        }
temp-->next = NULL;
Tail = temp;
Since, we are traversing entire linked for each Dequeue, so time complexity will be Θ(n).

Option (B) is correct.