Linked List in Data Structure

1. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
(a) O(n)
(b) O(log2 n)
(c) O(logn)
(d) O(1)
Answer

2. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. 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
Answer

3. In a circular linked list
(a) Components are all linked together in some sequential manner.
(b) There is no beginning and no end.
(c) Components are arranged hierarchically.
(d) Forward and backward traversal within the list is permitted.
Answer

4. In a linked list with n nodes, the time taken to insert an element after an element pointed by
some pointer is
(a) 0 (1)
(b) 0 (log n)
(c) 0 (n)
(d) 0 (n 1og n)
Answer

5. 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) None of these
Answer

6. Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?
(a) Deleting a node whose location is given
(b) Searching of an unsorted list for a given item
(c) Inverting the list after the node with given location
(d) Traversing a list to process each node
Answer

7. The time required to delete a node x from a doubly linked list having n nodes is
(a) O (n)
(b) O (log n)
(c) O (1)
(d) O (n log n)
Answer

8. Time required finding any element of the linked list is.
(a) O (n2)
(b) O (1)
(c) O (n)
(d) None of these
Answer

9. Pointer is pointing to the first element of the Node then time required to insert Element to second position is
(a) O(n2)
(b) O (sqrt(n))
(c) O(n)
(d) O(1)
Answer

10. A variant of linked list in which last node of the list points to the first node of the list is?

(a) Singly linked list
(b) Doubly linked list
(c) Circular linked list
(d) Multiply linked list
Answer