This set of Data Structure Interview Questions & Answers focuses on “Singly Linked List Operations

1. What would be the asymptotic time complexity to find an element in the linked list?
A) O(1)
B) O(n)
C) O(n2)
D) O(n4)

Explanation: We must traverse the entire linked list if the necessary element is in the last place. The element will be searched in O (n) time.

2. What would be the asymptotic time complexity to insert an element at the second position in the linked list?
A) O(1)
B) O(n)
C) O(n2)
D) O(n3)

Explanation: The necessary element is added to a new node. The new node’s pointer points to the same node that the linked list’s head node points to. The pointer for the head node has been modified to point to the new node that we generated earlier. The entire procedure takes O (1) time to complete. As a consequence, the asymptotic time complexity of adding an element in the linked list’s second position is O. (1).

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

Explanation: We can easily concatenate two lists in O (1) time using a singly or doubly linked list, as long as at least one of the lists has a pointer to the last node. In the case of circular doubly linked lists, however, we can break the relation between the two lists and connect them. In O (1) time, a circular doubly connected list concatenates two lists.

4. 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(NODE);
C) ptr = (NODE*)malloc(sizeof(NODE*));
D) ptr = (NODE)malloc(sizeof(NODE));

Explanation: Since it exemplifies the proper way to construct a node.

5. A linear collection of data elements where the linear node is given by means of pointer is called?
B) Node list
C) Primitive list
D) Unordered list

Explanation: Each node in a linked list has its own data and the address of the next node. Pointers are used to link these nodes. A node list is an entity that contains a list of all nodes in a document that are included within a certain collection of nodes.

6. 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

Explanation: In the given linked list, we know where the head node is. Insertion and deletion of elements at the front of the linked list takes O (1) time, while insertion and deletion at the end of the linked list necessitates traversing through all of the linked list’s nodes. In the case of a linked list with n elements, we must traverse each node. As a result, the time complexity is O. (n).

7. In linked list each node contains a minimum of two fields. One field is data field to store the data second field is?
A) Pointer to character
B) Pointer to integer
C) Pointer to node
D) Node

Explanation: In a linked list, each node contains data as well as a reference to the next node. The second field includes a node pointer.

8. What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?
A) O(1)
B) O(n)
C) θ(n)
D) θ(1)

Explanation: In the case of a connected list with n elements, we must traverse each node of the list in order to add the element at the end. As a result, asymptotic time complexity is (n).

9. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?
A) O(1)
B) O(n)
C) O(n2)
D) O(n3)

Explanation: To add an element to the front of the linked list, we’ll create a new node that contains the data to be added and a pointer that points to the linked list’s head location. The entire event occurs in O (1) time. As a result, the asymptotic time complexity equals O. (1).

10. Linked list data structure offers considerable saving in _____________
A) Computational Time
B) Space Utilization
C) Space Utilization and Computational Time
D) Speed Utilization

Explanation: Linked lists save space as well as time.

11. Which of the following points is/are not true about Linked List data structure when it is compared with an array?
A) Arrays have better cache locality that can make them better in terms of performance
B) It is easy to insert and delete elements in Linked List
C) Random access is not allowed in a typical implementation of Linked Lists
D) Access of elements in linked list takes less time than compared to arrays

Explanation: To get to an element in a linked list, we must go through all of the elements before we find the one we want. Since arrays have random access to their elements, this may take longer.

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

```void fun1(struct node* head)
{
return;
}```

13. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
a) Insertion Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort

Explanation: 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(n2), merge sort is preferred.

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

Explanation: fun1() reverses the Linked List that is passed to it.
For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1.

14. What kind of linked list is best to answer questions like “What is the item at position n?”
D) Array implementation of linked list

Explanation: By enclosing the index value in square brackets, arrays allow for random access to elements. We must go through each element in the linked list until we reach the nth location. Accessing an element represented in an array takes less time than accessing an element represented in a singly, doubly, or circular connected list. As a result, the item at position n is accessed using array implementation.

15. Linked lists are not suitable for the implementation of ___________
A) Insertion sort
C) Polynomial manipulation
D) Binary search

Explanation: Related lists cannot be used to execute it.

16. Linked list is considered as an example of ___________ type of memory allocation.
A) Dynamic
B) Static
C) Compile time
D) Heap

Explanation: Due to the fact that memory is allocated at runtime.

17. In Linked List implementation, a node carries information regarding ___________
A) Data
D) Node

Explanation: A linked list is a group of objects that are linked together by references from one object to another. These objects are referred to as nodes by convention. A linked list is made up of nodes, each of which has one or more data fields and a connection to the next node.

18. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

```struct node
{
int value;
struct node *next;
};
void rearrange(struct node *list)
{
struct node *p, * q;
int temp;
if ((!list) || !list->next)
return;
p = list;
q = list->next;
while(q)
{
temp = p->value;
p->value = q->value;
q->value = temp;
p = q->next;
q = p?p->next:0;
}
}```

A) 1, 2, 3, 4, 5, 6, 7
B) 2, 1, 4, 3, 6, 5, 7
C) 1, 3, 2, 5, 4, 7, 6
D) 2, 3, 4, 5, 6, 7, 1

Explanation: Any node’s data is exchanged with its next node using the function rearrange(). It begins exchanging data with the first node.

19. 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) n2
C) log 2 n – 1
D) n

Explanation: In the worst-case scenario, the element to be searched must be compared to all of the linked list’s elements.

20. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
A) Possible if X is not last node
B) Possible if size of linked list is even
C) Possible if size of linked list is odd
D) Possible if X is not first node

Explanation: Following are simple steps.

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

21. 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

Explanation:

By deleting memory and modifying the first pointer, the first element of the list is deleted in O (1) time.
It is possible to insert an element as the first element in O (1) time. We’ll make a data-holding node that points to the beginning of the linked list. A newly generated node was used as the head pointer.
The pointer to the previous node of last is required for deletion of the last element, which can only be obtained by traversing the list. This necessitates the linked list’s length.
In O (1), you can add a new element to the end of the list by changing the pointer of the last node to the newly created node, and last is moved to a newly created node.

22. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is?
A) log2 n
B) n2
C) log2 n – 1
D) n

Explanation: If the necessary element is last or not present in the list, the worst-case scenario occurs. We must compare each element in the linked list to achieve this. In the worst-case scenario, if n elements are present, n comparisons will occur.

23. 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
{
struct node* prev   = NULL;
struct node* next;
while (current != NULL)
{
next  = current->next;
current->next = prev;
prev = current;
current = next;
}
}```

What should be added in place of “/*ADD A STATEMENT HERE*/”, so that the function correctly reverses a linked list.

Explanation:

*head ref = prev; The prev pointer refers to the last node of the original linked list at the end of the while loop.
*head ref must be changed so that the head pointer now points to the last node.

24. What is the output of following function for start pointing to first node of following linked list?

```1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d  ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d  ", start->data);
}```

A) 1 4 6 6 4 1
B) 1 3 5 1 3 5
C) 1 2 3 5
D) 1 3 5 5 3 1

Explanation: fun() prints the given Linked List’s alternate nodes, first from head to end and then from end to head.
If the Linked List has an even number of nodes, the last node is skipped.
public relations

25. The following C function takes a simply-linked list as an input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. Choose the correct alternative to replace the blank line.

```typedef struct node
{
int value;
struct node *next;
}Node;

{
Node *p, *q;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________