Linked List Traversal

ptr = head

while (ptr!=NULL)

ptr = ptr -> next

Consider the above operation to be performed over the linked list 1->2->3->4->5.What will be the output?

• 1 2 3 4 5

• 1 2 3

• 1 3 5

• 1 1 1 1 1

Answer explanation

Linked list is traversed entirely

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

• O(1)

• O(n logn)

• O(n)

• None of the above

Answer explanation

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

What is the time complexity to search ith element in the linked list?

• O(1)

• O(n logn)

• O(n)

• None of the above

Answer explanation

Searching an ith element in the linked list takes time complexity of O(n)

The operation of processing each element in the list is known as

• sorting

• merging

• inserting

• traversal

Answer explanation

The operation of processing each element in the list is known as traversal

Consider the following linked list 12->15->18->21->24

What will be the output of search(3) and search(15) respectively?

• -1 and -1

• 1 and 1

• 1 and -1

• -1 and 1

Answer explanation

Since the element 3 is not the function returns -1 and element 15 is found at position 1 so it returns 1

Which of the following points is/are not true about Linked List data structure when it is compared with an array?

• Arrays have better cache locality that can make them better in terms of performance

• Access of elements in linked list takes less time than compared to arrays

• It is easy to insert and delete elements in Linked List

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

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

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

• 1 4 6 6 4 1

• 1 3 5 1 3 5

• 1 3 5 5 3 1

• 1 2 3 5

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

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

• Fixed size

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

• Accessing elements at specified positions

• Insertion based on position

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

Traversal is the most essential part in which of the following operations?

• Insertion after specific node

• Deletion after specific node

• Both a and b

• None of the above

Answer explanation

Traversal is the most crucial step to find the specific node to perform insertion and deletion

• Find and delete a given element in the list

• Find and return the given element in the list

• Find and return the position of the given element in the list

• Find and insert a new element in the list

Answer explanation

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