By practicing these MCQs of Single Linked List MCQs (Data Structure ) MCQs – Latest Competitive MCQs , an individual for exams performs better than before. This post comprising of objective questions and answers related to Single Linked Listed MCQs (Data Structure ) mcqs “. As wise people believe “Perfect Practice make a Man Perfect”. It is therefore practice these mcqs of Data Structure to approach the success. Tab this page to check “Singel Linked List MCQs (Data Structure)” for the preparation of competitive exmas.

The most occurred mcqs of Single Linked List MCQs ( Data Structure ) in past papers. Past papers of Single Linked Listed MCQs (Data structure ) Mcqs. Past papers of Single Linked Listed MCQs (Data Structure ) Mcqs . Mcqs are the necessary part of any competitive / job related exams. The Mcqs having specific numbers in any written test. It is therefore everyone have to learn / remember the related Single Linked List MCQs ( Data Structure ) Mcqs. The Important series of Single Linked List MCQs ( Data Structure ) Mcqs are given below:

This set of Data Structure Interview Questions & Answers focuses on “Single Linked List”.

1. A linear collection of data elements where the linear node is given by means of pointer is called?

a) Node list

c) Primitive list

d) Unordered list

Explanation: In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.

2. 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, II and III

c) I and III

d) I, II and III

Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).

3. 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) Node

d) Pointer to node

Explanation: Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node.

4. 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) θ(1)

d) θ(n)

Explanation: In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).

5. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?

a) O(n)

b) O(1)

c) O(n2)

d) O(n3)

Explanation: To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).

6. What would be the asymptotic time complexity to find an element in the linked list?

a) O(1)

b) O(n2)

c) O(n4)

b) O(n)

Explanation: If the required element is in the last position, we need to traverse the entire linked list. This will take O (n) time to search the element.

7. What would be the asymptotic time complexity to insert an element at the second position in the linked list?

a) O(n)

b) O(n2)

c) O(1)

d) O(n3)

Explanation: A new node is created with the required element. The pointer of the new node points the node to which the head node of the linked list is also pointing. The head node pointer is changed and it points to the new node which we created earlier. The entire process completes in O (1) time. Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1).

8. 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 singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.

9. 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(NODE);

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

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

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

Explanation: As it represents the right way to create a node.

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

c) Array implementation of linked list

Explanation: Arrays provide random access to elements by providing the index value within square brackets. In the linked list, we need to traverse through each element until we reach the nth position. Time taken to access an element represented in arrays is less than the singly, doubly and circular linked lists. Thus, array implementation is used to access the item at the position n.

11. Linked lists are not suitable for the implementation of ___________

a) Binary search

b) Insertion sort

d) Polynomial manipulation

Explanation: It cannot be implemented using linked lists.

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

a) Static

b) Compile time

c) Heap

d) Dynamic

Explanation: As memory is allocated at the run time.

13. In Linked List implementation, a node carries information regarding ___________

a) Data

b) Node

Explanation: A linked list is a collection of objects linked together by references from an object to another object. By convention these objects are names as nodes. Linked list consists of nodes where each node contains one or more data fields and a reference(link) to the next node.

14. Linked list data structure offers considerable saving in _____________

a) Space Utilization and Computational Time

b) Computational Time

c) Space Utilization

d) Speed Utilization

Explanation: Linked lists saves both space and time.

15. 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) Access of elements in linked list takes less time than compared to arrays

c) It is easy to insert and delete elements in Linked List

d) Random access is not allowed in a typical implementation of Linked Lists

Explanation: To access an element in a linked list, we need to traverse every element until we reach the desired element. This will take more time than arrays as arrays provide random access to its elements.

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

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

a) Prints all nodes of linked lists

b) Prints alternate nodes of Linked List

c) Prints all nodes of linked list in reverse order

d) Prints alternate nodes in reverse order

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

17. 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) Merge Sort

d) Heap 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.

18. 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; 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.

19. 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 3 5 5 3 1

b) 1 2 3 5

Explanation: 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.

20. 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;
}
_______________________________
}```

d) head = p; p->next = q; q->next = NULL;

Explanation: When while loop completes its execution, node ‘p’ refers to the last node whereas the ‘q’ node refers to the node before ‘p’ in the linked list. q->next=NULL makes q as the last node. p->next=head places p as the first node. the head must be modified to ‘p’ as ‘p’ is the starting node of the list (head=p). Thus the sequence of steps are q->next=NULL, p->next=head, head=p.

21. 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) 1, 3, 2, 5, 4, 7, 6

c) 2, 3, 4, 5, 6, 7, 1

d) 2, 1, 4, 3, 6, 5, 7

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

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) log 2 n

b) n

c) n2

d) log 2 n – 1

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

23. 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 size of linked list is even

b) Possible if size of linked list is odd

c) Possible if X is not first node

d) Possible if X is not last node

Explanation: Following are simple steps.

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

24. 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) Delete the last element of the list

c) Insert a new element as a first element

d) Add a new element at the end of the list

Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.
Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.
Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.
Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.

25. 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) n

c) n2

d) log2 n – 1

Explanation: The worst-case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case.

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

a) Fixed size

b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

c) Accessing elements at specified positions

d) Insertion based on position

Explanation: 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.

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

a) O(1)

b) O(n)

c) Either O(1) or O(n)

d) O(logn)

Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array that 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.

28. What is the time complexity to count the number of elements in the linked list?

a) O(n)

b) O(1)

c) O(logn)

d) O(n2)

Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n).

29. Which of the following performs deletion of the last element in the list? Given below is the Node class.

```class Node
{
protected Node next;
protected Object ele;
Node(Object e,Node n)
{
ele = e;
next = n;
}
public void setNext(Node n)
{
next = n;
}
public void setEle(Object e)
{
ele = e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}
class SLL
{
int size;
SLL()
{
size = 0;
}
}```

a)

```public Node removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur.getNext() != null)
{
temp = cur;
cur = cur.getNext();
}
temp.setNext(null);
size--;
return cur;
}```

b)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur != null)
{
temp = cur;
cur = cur.getNext();
}
temp.setNext(null);
return cur;
}```

c)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}```

d)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur.getNext() != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}```
Explanation: Since you have to traverse to the end of the list and delete the last node, you need two reference pointers. ‘cur’ to traverse all the way and find the last node, and ‘temp’ is a trailing pointer to ‘cur’. Once you reach the end of the list, setNext of ‘temp’ to null, ‘cur’ is not being pointed to by any node, and hence it is available for garbage collection.

30. What is the functionality of the following code?

```public void function(Node node)
{
if(size == 0)
else
{
Node temp,cur;
for(cur = head; (temp = cur.getNext())!=null; cur = temp);
cur.setNext(node);
}
size++;
}```

a) Inserting a node at the beginning of the list

b) Deleting a node at the beginning of the list

c) Deleting a node at the end of the list

d) Inserting a node at the end of the list

Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext(node);

31. What is the space complexity for deleting a linked list?

a) O(n)

b) O(1)

c) Either O(1) or O(n)

d) O(logn)

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

32. 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)
else
{
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)
else
{
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)
else
{
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)
else
{
for(int i=0; i<pos; i++)
{
temp = temp.getNext();
}
temp.setNext(temp.getNext().getNext());
}
size--;
}```
Explanation: Loop through the list to get into position one behind the actual position given. temp.setNext(temp.getNext().getNext()) will delete the specified node.

33. Which of these is not an application of a linked list?

a) To implement file systems

b) For separate chaining in hash-tables

c) To implement non-binary trees

d) Random Access of elements

Explanation: To implement file system, for separate chaining in hash-tables and to implement non-binary trees linked lists are used. Elements are accessed sequentially in linked list. Random access of elements is not an applications of linked list.

34. Which of the following piece of code has the functionality of counting the number of elements in the list?

a)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext();
}
return size;
}```

b)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
cur = cur.getNext();
size++;
}
return size;
}```

c)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext();
}
}```

d)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext().getNext();
}
return size;
}```
Explanation: ‘cur’ pointer traverses through list and increments the size variable until the end of list is reached.

35. How do you insert an element at the beginning of the list?

a)

```public void insertBegin(Node node)
{
size++;
}```

b)

```public void insertBegin(Node node)
{
size++;
}```

c)

```public void insertBegin(Node node)
{
node.setNext(temp);
size++;
}```

d)

```public void insertBegin(Node node)
{
node.setNext(temp);
size++;
}```
Explanation: Set the ‘next’ pointer point to the head of the list and then make this new node as the head.

36. What is the functionality of the following piece of code?

```public int function(int data)
{
int var = 0;
while(temp != null)
{
if(temp.getData() == data)
{
return var;
}
var = var+1;
temp = temp.getNext();
}
return Integer.MIN_VALUE;
}```

a) Find and delete a given element in the list

b) Find and return the given element in the list

c) Find and insert a new element in the list

d) Find and return the position of the given element in the list

Explanation: When temp is equal to data, the position of data is returned.

By practicing these MCQs of Single Linked List MCQs (Data Structure ) MCQs – Latest Competitive MCQs , an individual for exams performs better than before. This post comprising of objective questions and answers related to Single Linked Listed MCQs (Data Structure ) mcqs “. As wise people believe “Perfect Practice make a Man Perfect”. It is therefore practice these mcqs of Data Structure to approach the success. Tab this page to check “Singel Linked List MCQs (Data Structure)” for the preparation of competitive exmas.

The most occurred mcqs of Single Linked List MCQs ( Data Structure ) in past papers. Past papers of Single Linked Listed MCQs (Data structure ) Mcqs. Past papers of Single Linked Listed MCQs (Data Structure ) Mcqs . Mcqs are the necessary part of any competitive / job related exams. The Mcqs having specific numbers in any written test. It is therefore everyone have to learn / remember the related Single Linked List MCQs ( Data Structure ) Mcqs. The Important series of Single Linked List MCQs ( Data Structure ) Mcqs are given below:

This set of Data Structure Interview Questions & Answers focuses on “Single Linked List”.

1. A linear collection of data elements where the linear node is given by means of pointer is called?

a) Node list

c) Primitive list

Explanation: In Linked list each node has its own data and the address of next node. These nodes are linked by using pointers. Node list is an object that consists of a list of all nodes in a document with in a particular selected set of nodes.

2. 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, II and III

c) I and III

d) I, II and IIIAnswer: c
Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list. Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).

3. 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) Node

Explanation: Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node.

4. 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) θ(1)

Explanation: In case of a linked list having n elements, we need to travel through every node of the list to add the element at the end of the list. Thus asymptotic time complexity is θ(n).

5. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?

a) O(n)

b) O(1)

c) O(n2)

d) O(n3)

Explanation: To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).

6. What would be the asymptotic time complexity to find an element in the linked list?

a) O(1)

b) O(n2)

c) O(n4)

Explanation: If the required element is in the last position, we need to traverse the entire linked list. This will take O (n) time to search the element.

7. What would be the asymptotic time complexity to insert an element at the second position in the linked list?

a) O(n)

b) O(n2)

c) O(1)

Explanation: A new node is created with the required element. The pointer of the new node points the node to which the head node of the linked list is also pointing. The head node pointer is changed and it points to the new node which we created earlier. The entire process completes in O (1) time. Thus the asymptotic time complexity to insert an element in the second position of the linked list is O (1).

8. 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 listAnswer: b
Explanation: We can easily concatenate two lists in O (1) time using singly or doubly linked list, provided that we have a pointer to the last node at least one of the lists. But in case of circular doubly linked lists, we will break the link in both the lists and hook them together. Thus circular doubly linked list concatenates two lists in O (1) time.

9. 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(NODE);

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

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

Explanation: As it represents the right way to create a node.

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

c) Array implementation of linked list

Explanation: Arrays provide random access to elements by providing the index value within square brackets. In the linked list, we need to traverse through each element until we reach the nth position. Time taken to access an element represented in arrays is less than the singly, doubly and circular linked lists. Thus, array implementation is used to access the item at the position n.

11. Linked lists are not suitable for the implementation of ___________

a) Binary search

b) Insertion sort

Explanation: It cannot be implemented using linked lists.

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

a) Static

b) Compile time

c) Heap

Explanation: As memory is allocated at the run time.

13. In Linked List implementation, a node carries information regarding ___________

a) Data

b) Node

Explanation: A linked list is a collection of objects linked together by references from an object to another object. By convention these objects are names as nodes. Linked list consists of nodes where each node contains one or more data fields and a reference(link) to the next node.

14. Linked list data structure offers considerable saving in _____________

a) Space Utilization and Computational Time

b) Computational Time

c) Space Utilization

Explanation: Linked lists saves both space and time.

15. 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) Access of elements in linked list takes less time than compared to arrays

c) It is easy to insert and delete elements in Linked List

d) Random access is not allowed in a typical implementation of Linked ListsAnswer: b
Explanation: To access an element in a linked list, we need to traverse every element until we reach the desired element. This will take more time than arrays as arrays provide random access to its elements.

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

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

a) Prints all nodes of linked lists

b) Prints alternate nodes of Linked List

c) Prints all nodes of linked list in reverse order

d) Prints alternate nodes in reverse orderAnswer: c
Explanation: fun1() prints the given Linked List in reverse manner.
For Linked List 1->2->3->4->5, fun1() prints 5->4->3->2->1.

17. 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) 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.

18. 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; 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.

19. 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 3 5 5 3 1

b) 1 2 3 5Answer: c
Explanation: 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.

20. 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;
}
_______________________________
}```

Explanation: When while loop completes its execution, node ‘p’ refers to the last node whereas the ‘q’ node refers to the node before ‘p’ in the linked list. q->next=NULL makes q as the last node. p->next=head places p as the first node. the head must be modified to ‘p’ as ‘p’ is the starting node of the list (head=p). Thus the sequence of steps are q->next=NULL, p->next=head, head=p.

21. 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) 1, 3, 2, 5, 4, 7, 6

c) 2, 3, 4, 5, 6, 7, 1

d) 2, 1, 4, 3, 6, 5, 7Answer: d
Explanation: The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

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) log 2 n

b) n

c) n2

d) log 2 n – 1Answer: b
Explanation: In the worst case, the element to be searched has to be compared with all elements of the linked list.

23. 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 size of linked list is even

b) Possible if size of linked list is odd

c) Possible if X is not first node

d) Possible if X is not last nodeAnswer: d
Explanation: Following are simple steps.

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

24. 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) Delete the last element of the list

c) Insert a new element as a first element

d) Add a new element at the end of the listAnswer: b
Explanation: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.
Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.
Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.
Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.

25. 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) n

c) n2

d) log2 n – 1Answer: b
Explanation: The worst-case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case.

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

a) Fixed size

b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size

c) Accessing elements at specified positions

d) Insertion based on positionAnswer: c
Explanation: 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.

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

a) O(1)

b) O(n)

c) Either O(1) or O(n)

Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array that 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.

28. What is the time complexity to count the number of elements in the linked list?

a) O(n)

b) O(1)

c) O(logn)

Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n).

29. Which of the following performs deletion of the last element in the list? Given below is the Node class.

```class Node
{
protected Node next;
protected Object ele;
Node(Object e,Node n)
{
ele = e;
next = n;
}
public void setNext(Node n)
{
next = n;
}
public void setEle(Object e)
{
ele = e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}
class SLL
{
int size;
SLL()
{
size = 0;
}
}```

a)

```public Node removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur.getNext() != null)
{
temp = cur;
cur = cur.getNext();
}
temp.setNext(null);
size--;
return cur;
}```

b)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur != null)
{
temp = cur;
cur = cur.getNext();
}
temp.setNext(null);
return cur;
}```

c)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}```

d)

```public void removeLast()
{
if(size == 0)
return null;
Node cur;
Node temp;
while(cur.getNext() != null)
{
cur = cur.getNext();
temp = cur;
}
temp.setNext(null);
return cur;
}```

Explanation: Since you have to traverse to the end of the list and delete the last node, you need two reference pointers. ‘cur’ to traverse all the way and find the last node, and ‘temp’ is a trailing pointer to ‘cur’. Once you reach the end of the list, setNext of ‘temp’ to null, ‘cur’ is not being pointed to by any node, and hence it is available for garbage collection.

30. What is the functionality of the following code?

```public void function(Node node)
{
if(size == 0)
else
{
Node temp,cur;
for(cur = head; (temp = cur.getNext())!=null; cur = temp);
cur.setNext(node);
}
size++;
}```

a) Inserting a node at the beginning of the list

b) Deleting a node at the beginning of the list

c) Deleting a node at the end of the list

d) Inserting a node at the end of the listAnswer: d
Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext(node);

31. What is the space complexity for deleting a linked list?

a) O(n)

b) O(1)

c) Either O(1) or O(n)

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

32. 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)
else
{
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)
else
{
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)
else
{
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)
else
{
for(int i=0; i<pos; i++)
{
temp = temp.getNext();
}
temp.setNext(temp.getNext().getNext());
}
size--;
}```

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

33. Which of these is not an application of a linked list?

a) To implement file systems

b) For separate chaining in hash-tables

c) To implement non-binary trees

d) Random Access of elementsAnswer: d
Explanation: To implement file system, for separate chaining in hash-tables and to implement non-binary trees linked lists are used. Elements are accessed sequentially in linked list. Random access of elements is not an applications of linked list.

34. Which of the following piece of code has the functionality of counting the number of elements in the list?

a)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext();
}
return size;
}```

b)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
cur = cur.getNext();
size++;
}
return size;
}```

c)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext();
}
}```

d)

```public int length(Node head)
{
int size = 0;
while(cur!=null)
{
size++;
cur = cur.getNext().getNext();
}
return size;
}```

Explanation: ‘cur’ pointer traverses through list and increments the size variable until the end of list is reached.
35. How do you insert an element at the beginning of the list?

a)

```public void insertBegin(Node node)
{
size++;
}```

b)

```public void insertBegin(Node node)
{
size++;
}```

c)

```public void insertBegin(Node node)
{
node.setNext(temp);
size++;
}```

d)

```public void insertBegin(Node node)
{
node.setNext(temp);
size++;
}```

Explanation: Set the ‘next’ pointer point to the head of the list and then make this new node as the head.

36. What is the functionality of the following piece of code?

```public int function(int data)
{
int var = 0;
while(temp != null)
{
if(temp.getData() == data)
{
return var;
}
var = var+1;
temp = temp.getNext();
}
return Integer.MIN_VALUE;
}```

a) Find and delete a given element in the list

b) Find and return the given element in the list

c) Find and insert a new element in the list

d) Find and return the position of the given element in the list