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.