I've sat on both sides of the interview table, and there is one particular answer that makes me immediately realize a candidate is reciting a textbook rather than thinking like an engineer. When asked about the difference between an array and a linked list, they almost always say: "Linked lists are faster because you can insert elements in O(1) time."

The "Linked Lists are Magic for Fast Insertions" Myth

On paper, this is true. If you already have a pointer to the node where you want to insert, swapping a few pointers is indeed an O(1) operation. But in a real C program, you almost never "just have" that pointer. You usually have to find the insertion point first.

// The textbook version: "Look how fast this is!"
void insert_after(Node* prev_node, int new_data) {
    Node* new_node = malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
}

The mistake is ignoring the cost of getting to prev_node. If you're inserting the 500th element in a list, you have to call next 499 times. That's O(n). In an array, while you have to shift elements to make room (which is also O(n)), the actual memory access is contiguous and incredibly fast. I've seen candidates fail interviews because they insisted a linked list was the "correct" choice for a high-frequency insertion task, ignoring the fact that the search time completely negated the insertion benefit.

The Reality: O(1) Insertion Requires an O(n) Search

To answer this correctly in an interview, you need to distinguish between the act of insertion and the process of locating the insertion point. If you are implementing a Queue, where you only ever touch the head and tail, a linked list is fantastic. But for a general-purpose list? The array often wins because of how CPUs actually work.

This leads into another favorite interview topic: Cache Locality. An array is a single contiguous block of memory. When the CPU loads one element, it loads the next few elements into the cache automatically. A linked list, however, scatters nodes across the heap. Every time you follow a next pointer, you're potentially triggering a cache miss, forcing the CPU to wait for a slow trip to main RAM. I always suggest mentioning this; it shows you understand the hardware, not just the Big O notation.

Navigating the "Classic" Data Structure Questions

Beyond the array vs. list debate, C interviews love to test your pointer manipulation. You'll likely run into these three patterns. Don't memorize the code; memorize the mechanism.

• Reversing a Linked List: The trick here is maintaining three pointers (prev, current, next). If you try to do it with two, you'll inevitably "orphan" the rest of your list and create a memory leak.
• Cycle Detection: Use "Floyd's Tortoise and Hare." One pointer moves one step, the other moves two. If they ever meet, you've got a loop. It's a elegant solution that avoids having to store every visited address in a separate hash set.
• Stack vs. Queue: Be ready to explain why a stack is LIFO and a queue is FIFO, but more importantly, be ready to implement them using both an array (fixed size, fast) and a linked list (dynamic size, slightly more overhead).

When you're writing these on a whiteboard or in a shared editor, talk through your memory management. In C, an interview isn't just about the algorithm; it's about whether you remember to free() your nodes. If you implement a delete_list function and forget to free the temporary pointer before moving to the next node, it's a red flag that you don't handle resources carefully.

📋 Practical Task

Implementing a Fast-Slow Pointer Cycle Detector

One of the most common C interview challenges is detecting a loop in a singly linked list. Your task is to implement a function int has_cycle(Node* head). This function should return 1 if a cycle exists (where a node's next pointer eventually points back to a previous node in the list) and 0 if the list terminates with a NULL pointer.

Requirements:

• Do not use any extra data structures (like an array or hash map) to store visited nodes; you must use the "Tortoise and Hare" approach.
• Ensure your code handles edge cases: an empty list (head == NULL) and a list with only one node.
• Provide a small main function that manually creates a circular link between two nodes to verify your detector works.

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int has_cycle(Node* head) {
    // Your implementation here
}