Singly Linked List Operations | Data Structure MCQs

1.

What does the following function do for a given Linked List with first node as head?

void fun1(struct node* head)
{
    if(head == NULL)
    return;
    fun1(head->next);
    printf("%d  ", head->data);
}

   A.) Prints all nodes of linked lists
   B.) Prints all nodes of linked list in reverse order
   C.) Prints alternate nodes of Linked List
   D.) Prints alternate nodes in reverse order

Answer: Option 'B'

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

2.

Which of the following is not a disadvantage to the usage of array?

   A.) Fixed size
   B.) You know the size of the array prior to allocation
   C.) Insertion based on position
   D.) Accessing elements at specified positions

Answer: Option 'D'

Accessing elements at specified positions
Array elements can be accessed in two steps. First, multiply the size of the data type with the specified position, second, add this value to the base address. Both of these operations can be done in constant time, hence accessing elements at a given index/position is faster.

3.

What kind of linked list is best to answer question like “What is the item at position n?”

   A.) Singly linked list
   B.) Doubly linked list
   C.) Circular linked list
   D.) Array implementation of linked list

Answer: Option 'D'

Array implementation of linked list

4.

In Linked List implementation, a node carries information regarding

   A.) Data
   B.) Link
   C.) Data and Link
   D.) None of these

Answer: Option 'B'

Link

5.

What is the space complexity for deleting a linked list?

   A.) O(1)
   B.) O(n)
   C.) Either O(1) or O(n)
   D.) O(logn)

Answer: Option 'A'

O(1)
You need a temp variable to keep track of current node, hence the space complexity is O(1).

6.

The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?

   A.) Singly linked list
   B.) Doubly linked list
   C.) Circular doubly linked list
   D.) Array implementation of list

Answer: Option 'C'

Circular doubly linked list

7.

Linked list is considered as an example of ___________ type of memory allocation.

   A.) Dynamic
   B.) Static
   C.) Compile time
   D.) None of these

Answer: Option 'A'

Dynamic

8.

You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?

   A.) Delete the first element
   B.) Insert a new element as a first element
   C.) Delete the last element of the list
   D.) Add a new element at the end of the list

Answer: Option 'C'

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() here
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.

9.

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

   A.) log 2 n
   B.) n⁄2
   C.) log 2 n – 1
   D.) n

Answer: Option 'D'

In the worst case, the element to be searched has to be compared with all elements of linked list.

10.

What is the time complexity of inserting at the end in dynamic arrays?

   A.) O(1)
   B.) O(n)
   C.) O(logn)
   D.) Either O(1) or O(n)

Answer: Option 'D'

Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array which is not full, then the element is simply stored at the end, this takes O(1) time. If you try to insert into an array which is full, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O(n) time.

11.

How would you delete a node in the singly linked list? The position to be deleted is given.

   A.)
public void delete(int pos)
{
	if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
            {
		temp = temp.getNext();
            }
	    temp.setNext(temp.getNext().getNext());
	}
	    size--;
}
   B.)
public void delete(int pos)
{
	if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
	    {
		temp = temp.getNext();
	    }
	    temp.setNext(temp.getNext());
	}
	    size--;
}
   C.)
public void delete(int pos)
{
        if(pos < 0)
	pos = 0;
	if(pos > size)
	pos = size;
	if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=1; i<pos; i++)
	    {
		temp = temp.getNext().getNext();
            }
	    temp.setNext(temp.getNext().getNext());
	}
	    size--;
}
   D.)
public void delete(int pos)
{
        if(pos < 0)
        pos = 0;
        if(pos > size)
        pos = size;
        if( size == 0)
	return;
	if(pos == 0)
	head = head.getNext();
	else
	{
	    Node temp = head;
	    for(int i=0; i<pos; i++)
	    {
		temp = temp.getNext();
	    }
	    temp.setNext(temp.getNext().getNext());
	}
	size--;
}

Answer: Option 'A'

Loop through the list to get into position one behind the actual position given. temp.setNext(temp.getNext().getNext()) will delete the specified node.

12.

Which of these is an application of linked lists?

   A.) To implement file systems
   B.) For separate chaining in hash-tables
   C.) To implement non-binary trees
   D.) All of the mentioned

Answer: Option 'D'

Linked lists can be used to implement all of the above mentioned applications.

13.

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only.
Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list

   A.) I and II
   B.) I and III
   C.) I, II and III
   D.) I, II and IV

Answer: Option 'B'

I and III

14.

Consider the following definition in c programming language

struct node
{
    int data;
    struct node * next;
}
typedef struct node NODE;
NODE *ptr;
Which of the following c code is used to create new node?

   A.) ptr = (NODE*)malloc(sizeof(NODE));
   B.) ptr = (NODE)malloc(sizeof(NODE));
   C.) ptr = (NODE*)malloc(NODE);
   D.) ptr = (NODE*)malloc(sizeof(NODE*));

Answer: Option 'A'

ptr = (NODE*)malloc(sizeof(NODE));

15.

The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function.

/* Link list node */
struct node
{
    int data;
    struct node* next;
};
 
/* head_ref is a double pointer which points to head (or start) pointer 
  of 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;
    }
    /*ADD A STATEMENT HERE*/
}
What should be added in place of “/*ADD A STATEMENT HERE*/”, so that the function correctly reverses a linked list.

   A.) *head_ref = prev;
   B.) *head_ref = current;
   C.) *head_ref = NULL;
   D.) *head_ref = current;

Answer: Option 'A'

*head_ref = prev;
*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.

Singly Linked List Operations | Data Structure MCQs Download Pdf