What is the worst case time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Option: c
Explanation: In the worst case, the position to be inserted maybe at the end of the
list, hence you have to traverse through the entire list to get to the correct position,
hence O(n).
What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) O(n2)
Option: a
Explanation: In the worst case, you have to traverse through the entire list of n
elements.
A linear collection of data elements where the linear node is given by means of
pointer is called?
a) Linked list
b) Node list
c) Primitive list
d) Unordered list
Option: a
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.
Consider an implementation of unsorted singly linked list. Suppose it hasits
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
Option : b
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
list. Suppose there are n elements in a linked list, we need to traverse through each
node. Hence time complexity becomes O(n).
and deletion at the last node requires to traverse through every node in the linked
In linked list each node contain minimum of two fields. One field is data fieldto
store the data second field is?
a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node
Option: c
Explanation: Each node in a linked list contains data and a pointer (reference) to the
next node. Second field contains pointer to node.
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)
Option: c
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).
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)
node points the node to which the head node of the linked list is also pointing. The
d) O(n3)
Option: b
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).
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)
Option: a
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).
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
Option: c
linked list, provided that we have a pointer to the last node at least one of the lists.
Explanation: We can easily concatenate two lists in O (1) time using singly or doubly
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.
What kind of linked list is best to answer question like “What is the itemat
position n?”
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Array implementation of linked list
Option: d
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.
Linked lists are not suitable to for the implementation of?
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
Option: d
Explanation: It cannot be implemented using linked lists.
Linked list is considered as an example of _______ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) Heap
Option: a
Explanation: As memory is allocated at the run time.
In Linked List implementation, a node carries information regarding __________
a) Data
b) Link
c) Data and Link
d) Node
Option: b
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.
Linked list data structure offers considerable saving in _______________
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) Speed Utilization
Option: c
Explanation: Linked lists saves both space and time.
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.
)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⁄2
c) log2 n – 1
d) n
Option: d
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.
What is the time complexity of inserting at the end in dynamic arrays?
array varies. If you try to insert into an array which is not full, then the element is
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1) or O(n)
Option: d
Explanation: 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.
What is the time complexity to count the number of elements in the linkedlist?
a) O(1)
b) O(n)
c) O(logn)
d) O(n2)
Option: b
Explanation: To count the number of elements, you have to traverse through the
entire list, hence complexity is O(n).
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)
Option: a
Explanation: You need a temp variable to keep track of current node, hence the space
complexity is O(1).
How do you calculate the pointer difference in a memory efficient double linked
list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node
Option: b
Explanation: The pointer difference is calculated by taking XOR of pointer to previous
node and pointer to the next node.
Which of the following application makes use of a circular linkedlist?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) Implement Hash Tables
Option: c
Explanation: Generally, round robin fashion is employed to allocate CPU time to resources which makes use of the circular linked list data structure. Recursive function calls use stack data structure. Undo Operation in text editor uses doubly
linked lists. Hash tables uses singly linked lists.
Which of the following is false about a circular linked list?
above the other is based on LIFO, people standing in a line is a queue and if the
a) Every node has a successor
b) Time complexity of inserting a new node at the head of the list isO(1)
c) Time complexity for deleting the last node is O(n)
d) We can traverse the whole circular linked list by starting from any point
Option: b
Explanation: Time complexity of inserting a new node at the head of the list is O(n)
because you have to traverse through the list to find the tail node.
Which of the following real world scenarios would you associate with a stack data
structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) tatkal Ticket Booking in IRCTC
Option: a
Explanation: Stack follows Last In First Out (LIFO) policy. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue. Tatkal
Ticket Booking Follows First in First Out Policy. People who click the book now first
will enter the booking page first.