Core Data Structures (Linked Lists, Stacks, Queues)

Data Structures Deep-Dive: Lists, Stacks, and Queues

The definitive guide to master core linear structures, real-world architectural patterns, and high-frequency MNC interview problems.

Software engineers must build scalable systems by selecting the correct memory layout for data. Inefficient choices introduce steep performance penalties. This guide dismantles the three fundamental linear data structures—Singly Linked Lists, Stacks, and Queues—equipping you with the theoretical insights, clean implementations, and tactical problem-solving frameworks required to ace technical interviews at top-tier tech companies.

1. Singly Linked Lists

Unlike arrays, a Singly Linked List abandons contiguous memory blocks entirely. Instead, it scatters its elements—called Nodes—randomly across the Heap memory. Every unique node houses two components: its payload data and a memory address pointer that references the next node in the sequence. This architecture eliminates the need for expensive memory reallocations when scaling dynamic data layouts.

Real-World Application: Scavenger Hunt Mechanics & Music Playlists
Think of a singly linked list like a city-wide scavenger hunt. You cannot find clue #4 without reading clue #3 first, because clue #3 holds the physical address of clue #4. Similarly, media streaming engines use linked lists to manage playback queues, where hitting "Next" simply reads the pointer reference of the current track to load the subsequent audio stream into memory.

High-Frequency Interview Problem 1: Reversing a Singly Linked List

MAANG interviewers frequently utilize this question to test your pointer-manipulation skills. The optimal approach swaps node pointers in-place using an iterative three-pointer strategy, achieving O(n) time complexity and O(1) auxiliary space complexity.

Google
Amazon
Microsoft
Meta

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

// Reverses a Singly Linked List via in-place Pointer Swapping
struct Node* reverseList(struct Node* head) {
    struct Node *prev = NULL;
    struct Node *current = head;
    struct Node *next = NULL;

    while (current != NULL) {
        next = current->next; // 1. Temporarily isolate the downstream node
        current->next = prev; // 2. Reverse the active pointer direction
        prev = current; // 3. Advance the tracking window forward
        current = next; // 4. Move to the next unprocessed node
    }
    return prev; // The tracking variable 'prev' now references the new head
}

High-Frequency Interview Problem 2: Detecting a Cycle in a Linked List

Interviewers want to see if you can identify structural corruption where a tail node links back to an earlier node. We solve this elegantly using Floyd’s Tortoise and Hare Algorithm. By advancing a slow pointer by one step and a fast pointer by two steps, they will inevitably collide if a cycle exists.

Netflix
Uber
Apple

int hasCycle(struct Node* head) {
    struct Node *slow = head, *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // Moves 1 node at a time
        fast = fast->next->next; // Moves 2 nodes at a time

        if (slow == fast) {
            return 1; // Cycle confirmed
        }
    }
    return 0; // Reached the end; no cycle present
}

2. Stacks (LIFO)

A Stack enforces a strict Last-In, First-Out (LIFO) policy. Imagine a vertical container where elements enter and depart exclusively from the top aperture. You cannot access lower elements without popping off everything sitting above them. Key operations run at a blazing fast O(1) time complexity, making stacks exceptionally fast toolsets for runtime evaluation tracking.

Real-World Application: The "Undo" Engine & Browser History
Every modern IDE uses a stack to power its history mechanisms. When you type characters, your editor pushes your actions onto a stack. Hitting Ctrl+Z pops the latest modification off the top of the stack, instantly restoring the previous text state.

High-Frequency Interview Problem: Validating Balanced Parentheses

Compilers use this logic to catch syntax syntax errors prior to runtime processing. The program maps incoming closing symbols to corresponding opening symbols tracking the current state on a stack tracking frame.

Amazon
Adobe
Microsoft

int checkBalanced(char expression[]) {
    char stack[100];
    int top = -1;

    for(int i = 0; expression[i] != '\0'; i++) {
        if(expression[i] == '(' || expression[i] == '{' || expression[i] == '[') {
            stack[++top] = expression[i]; // Push opening symbol
        } else if(expression[i] == ')' || expression[i] == '}' || expression[i] == ']') {
            if(top == -1) return 0; // Fail: Closing bracket has no matching opener

            char current_top = stack[top--]; // Pop the character
            // Validate matching structural pairs
            if(expression[i] == ')' && current_top != '(') return 0;
            if(expression[i] == '}' && current_top != '{') return 0;
            if(expression[i] == ']' && current_top != '[') return 0;
        }
    }
    return (top == -1) ? 1 : 0; // If empty, parentheses are balanced
}

3. Queues (FIFO)

Queues operate on a strict First-In, First-Out (FIFO) paradigm. Data entry occurs exclusively at the Rear, while element extractions occur at the Front. A standard linear array implementation of a queue suffers from memory leakage because data deletions leave unusable empty indices at the front. To prevent this, software systems implement Circular Queues, which wrap memory bounds back around to index zero using modulo arithmetic.

Real-World Application: Network Packet Routing & Thread Pools
Web servers handle high traffic volumes using request queues. Incoming HTTP connection requests land inside a queue managed by an operating system socket buffer. Worker threads systematically pull connections out from the front of the queue to process payloads without dropping connections.

High-Frequency Interview Problem: Robust Circular Queue Engine

This problem frequently surfaces during object-oriented system design and low-level programming rounds to evaluate resource tracking constraints.

Cisco
Intel
Oracle

#define SIZE 5
struct CircularQueue {
    int items[SIZE];
    int front, rear;
};

// Initialize queue tracking markers to unallocated bounds
void initQueue(struct CircularQueue* q) {
    q->front = -1;
    q->rear = -1;
}

// Insert element into the Circular Queue
int enQueue(struct CircularQueue* q, int value) {
    if ((q->front == 0 && q->rear == SIZE - 1) || (q->rear == (q->front - 1) % (SIZE - 1))) {
        return 0; // Overflow condition: Queue is full
    }
    if (q->front == -1) { // Allocate tracking flags for initial item placement
        q->front = q->rear = 0;
    } else if (q->rear == SIZE - 1 && q->front != 0) {
        q->rear = 0; // Loop around to reuse empty indices at the front
    } else {
        q->rear++;
    }
    q->items[q->rear] = value;
    return 1; // Operation successful
}

---

MNC Interview Complexity Comparison

Commit this computational complexity breakdown to memory before walking into your technical screening rounds:

Data Structure	Access (Worst Case)	Search (Worst Case)	Insertion (Average Case)	Deletion (Average Case)
Singly Linked List	O(n)	O(n)	O(1)	O(1)
Stack	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)

Data Structure Operations: Core Insertion Strategies

Mastering element insertion in Linked Lists, Queues, and Stacks for technical interviews.

In technical interviews at product-driven Multinational Corporations (MNCs), interviewers rarely ask you to just define a data structure. Instead, they test your ability to manipulate memory in real time. This guide breaks down the core insertion mechanics for Singly Linked Lists, Stacks, and Queues. We provide clean, production-ready C implementations alongside real-world applications and high-frequency interview strategies.

1. Singly Linked List Insertion Mechanics

Unlike arrays, where inserting elements requires shifting data, a Linked List handles insertions by rearranging memory pointers. Depending on the operational requirements, you can insert a node at the beginning, the middle (specific position), or the end of the list.

Real-World Application: Text Editor Cursor Tracking
Consider a text editor layout where each paragraph represents a node. When you type text at the very top of the page, the system performs an insertion at the beginning. When you append text to the end of the file, it executes an insertion at the end. If you place your cursor mid-page to insert a skipped word, the editor carries out an insertion at a specific position.

MNC Interview Problems & Code Implementation

Interviewers look closely at how you handle edge cases, such as inserting into an empty list or handling out-of-bounds positions.

Amazon Microsoft TCS Digital Infosys Infinity

#include <stdio.h>
#include <stdlib.h>

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

// 1. INSERT AT THE BEGINNING (FIRST POSITION)
// Time Complexity: O(1)
void insertAtFirst(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref); // Point new node to the old head
    (*head_ref) = new_node; // Move head pointer to point to the new node
}

// 2. INSERT AT THE END (LAST POSITION)
// Time Complexity: O(n)
void insertAtLast(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL; // This node will be the last node, so point to NULL

    if (*head_ref == NULL) {
        *head_ref = new_node; // If list is empty, make new node the head
        return;
    }
    while (last->next != NULL) {
        last = last->next; // Traverse to the final node
    }
    last->next = new_node; // Change the next pointer of the last node
}

// 3. INSERT AT MIDDLE (SPECIFIC POSITION)
// Time Complexity: O(n)
void insertAtPosition(struct Node** head_ref, int position, int new_data) {
    if (position < 1) {
        printf("Position invalid.\n");
        return;
    }
    if (position == 1) {
        insertAtFirst(head_ref, new_data);
        return;
    }
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    struct Node* temp = *head_ref;
    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next; // Locate the node right before the target position
    }
    if (temp == NULL) {
        printf("The previous node is NULL. Position out of bounds.\n");
        return;
    }
    new_node->next = temp->next; // Link new node to the rest of the list
    temp->next = new_node; // Redirect previous node to our new node
}

2. Stack Insertion: The Push Operation

Stack insertion uses a strict rule called Push. Because stacks follow a Last-In, First-Out (LIFO) pattern, every new element goes directly onto the very top of the stack. You cannot insert data anywhere else.

Real-World Application: Mobile Application Screen Routing
Think about navigating through an app on your phone. When you open your profile page, the operating system executes a push operation, placing the profile view container on top of the home screen view state. When you click back, it pops that view off.

High-Frequency Interview Focus: Handling Stack Overflow

MNC technical panels look to see if you remember to check for Overflow conditions before executing memory updates on fixed arrays.

Wipro Turbo Cognizant GenC Next HCLTech

#define MAX_SIZE 100

struct Stack {
    int arr[MAX_SIZE];
    int top;
};

// Push Operation: Inserts an item onto the top of the stack
// Time Complexity: O(1)
int push(struct Stack* s, int value) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack Overflow! Cannot push %d onto a full stack.\n", value);
        return 0; // Insertion failed
    }
    s->arr[++(s->top)] = value; // Increment top tracking index, then store the value
    return 1; // Insertion successful
}

3. Queue Insertion: The Enqueue Operation

Queue insertion uses a rule called Enqueue. Because queues follow a First-In, First-Out (FIFO) pattern, you add every new element to the Rear of the structure while removing elements from the Front.

Real-World Application: Food Delivery Order Routing
Food delivery platforms process orders sequentially. When you check out your cart, the platform enqueues your order details at the rear of the kitchen dispatch queue. The restaurant then processes jobs from the front of the queue, ensuring fair, chronological service.

High-Frequency Interview Focus: Linear Array Queue vs Circular Queue

A standard linear array queue wastes memory space because empty slots left behind by deleted elements at the front cannot be reused. To solve this, MNCs look for Circular Array Queues that wrap back around to reuse empty spaces at index zero.

Cisco Oracle Capgemini

#define QUEUE_CAPACITY 5

struct Queue {
    int storage[QUEUE_CAPACITY];
    int front;
    int rear;
};

// Enqueue Operation: Inserts an element into the rear of a Circular Queue
// Time Complexity: O(1)
int enqueue(struct Queue* q, int value) {
    // Check if the circular queue is completely full
    if ((q->rear + 1) % QUEUE_CAPACITY == q->front) {
        printf("Queue Overflow! Cannot add entry %d.\n", value);
        return 0; // Insertion failed
    }

    if (q->front == -1) { // If the queue is empty, set up initial tracking indices
        q->front = 0;
        q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % QUEUE_CAPACITY; // Loop back around to index 0 using modulo
    }

    q->storage[q->rear] = value;
    return 1; // Insertion successful
}

---

Insertion Performance Reference

Keep these time complexities in mind for your interview screenings to help you quickly choose the right design strategy:

Data Structure	Insertion Type	Time Complexity	Key Advantage
Singly Linked List	Insert at First	O(1)	Instant allocation with zero data shifting.
Singly Linked List	Insert at Middle / Last	O(n)	Flexible sizing, but requires traversal.
Stack	Push	O(1)	Highly efficient LIFO tracking.
Queue (Circular)	Enqueue	O(1)	Predictable, sequential FIFO ordering.

Quick Tip for Coding Interviews: If an interviewer asks you to optimize a linked list's insertAtLast operation from O(n) to O(1), introduce a tail tracking pointer. Keeping a reference to the final node allows you to attach new data instantly without having to loop through the entire list.

Pro-Tip for MNC Technical Interviews: When an interviewer asks you to optimize memory overhead, look for ways to replace dynamic node allocation with fixed-size arrays or circular arrays to drastically cut out pointer overhead. Conversely, if execution speeds matter most and data volumes spike unpredictably, shift your design to pointer-based models to eliminate array reallocation bottlenecks.