Roll-number list: fixed array or linked list
A small school stores the roll numbers of 60 students in a list. During the term, 12 new students join at the beginning of the list and 5 leave from the middle; the office also searches for a roll number every time a fee receipt is issued. A student proposes an array of size 60 with a count variable, while another proposes a singly linked list with a head pointer. The array version currently shifts elements on every insertion at the front, and the search is a linear scan. A third student writes a linked-list traversal that prints roll numbers but the program hangs after printing the last node. The teacher wants a reasoned choice for this workload, not a general comparison, and a fix for the traversal.
1. Choose between the fixed 60-element array and the singly linked list for this workload. Justify with the number of shifts, growth, and search cost.
Read the worked answer
The fixed array of 60 cannot hold the 72 students after 12 join, so it would need resizing or a larger declared capacity. Each front insertion into an array shifts all current elements: at 60 students, 12 insertions cost roughly 12 x 60 = 720 element moves, and the cost grows. The linked list inserts at the head in O(1) with a head pointer and does not need a capacity limit. The 5 middle deletions still require a search in both structures, so they do not favour either one. Searches are linear in both. The linked list pays pointer memory and loses random access, but for this workload - growth plus front insertion - it is the better fit. A dynamic array of capacity 100 is a reasonable alternative if simplicity matters, but the stated fixed 60-element array is not.
2. The traversal prints all roll numbers and then hangs. Give the most likely pointer bug and a corrected loop.
Read the worked answer
The loop prints the last node and then does not terminate, which points to the last node's next field not being NULL, or to the pointer not being advanced inside the loop. If insertion code allocates a node but never sets new->next = NULL, the last link contains an arbitrary address; traversal follows it and may cycle. Correct pattern: for (p = head; p != NULL; p = p->next) printf("%d\n", p->roll); and set new->next = NULL when inserting at the tail. If the code uses while (p->next != NULL), it cannot print or stop correctly at the last node without extra handling. Check both the loop update and the initialization of every new node.
3. The office expects 500 searches per day. Does that change your recommendation? Explain with a rough comparison.
Read the worked answer
Five hundred searches over about 72 nodes is roughly 36,000 comparisons per day, which is trivial for either structure. Searches dominate the operation count, but neither array nor linked list gives sub-linear search unless the data is sorted and a binary search is used; front insertions would break sorted order in the array. The linked list remains acceptable, and its O(1) head insertion is still an advantage. If search latency were critical, the right change would be a different structure such as a hash table or a sorted array with a separate insertion policy, not merely switching between these two. On this scale, the recommendation does not change; the fixed capacity problem is the stronger argument.