1.
Given a dataset of 10,000 sensor readings where frequent random access is required, which
structure (array or linked list) is more efficient and why? State the time complexity of random access
for both array and linked list.
Since frequent random access is required, Array is more efficient.
Because accessing any element takes O(1) in Array, but O(n) in Linked List.
Time Complexity:
o Array random access = O(1)
o Linked List random access = O(n)
2. Write a C function to count the number of nodes in a singly linked list.
int countNodes(struct Node* head) {
int count = 0;
struct Node* current = head;
while (current != NULL) {
count++;
current = current->next; // move to next node
}
return count;
}
3. Write a C function to print the elements stored in a linked list in reverse order.
1. Using Recursion (simple and elegant).
2. Using a Stack (iterative, avoids deep recursion for very long lists).
Method 1: Recursive Solution
void printReverse(struct Node* head) {
if (head == NULL) {
return; // base case
}
printReverse(head->next); // first go to the end
printf("%d ", head->data); // then print while unwinding recursion
}
Method 2: Iterative Using Stack
#define MAX 10000 // assuming list size won’t exceed this
void printReverse(struct Node* head) {
int stack[MAX];
int top = -1;
struct Node* current = head;
// push all elements onto stack
while (current != NULL) {
stack[++top] = current->data;
current = current->next;
}
// pop elements to print in reverse
while (top >= 0) {
printf("%d ", stack[top--]);
}
}
4. Write a C function to rotate a linked list.
// Function to rotate linked list by k nodes
struct Node* rotate(struct Node* head, int k) {
if (head == NULL || k == 0)
return head;
struct Node* current = head;
int count = 1;
// Traverse to the kth node
while (count < k && current != NULL) {
current = current->next;
count++;
}
// If k >= number of nodes, no rotation
if (current == NULL)
return head;
struct Node* kthNode = current;
// Traverse till the last node
while (current->next != NULL) {
current = current->next;
}
// Connect last node to head
current->next = head;
// New head is (k+1)th node
head = kthNode->next;
// Break the link at kth node
kthNode->next = NULL;
return head;
}
5. Write a C function to detect a loop in the linked list. - Floyd’s Cycle Detection Algorithm
int detectLoop(struct Node* head) {
struct Node *slow = head, *fast = head;
while (slow && fast && fast->next) {
slow = slow->next; // move slow pointer by 1
fast = fast->next->next; // move fast pointer by 2
if (slow == fast) { // loop detected
return 1;
}
}
return 0; // no loop
}
