Data Structures Programs in C, C++, Java and Python

Data structures programs form the core of every product-company technical interview, and the same logic compiles across C, C++, Java, and Python.

This article walks through the programs most commonly tested in placement rounds at Indian tech companies: linked list reversal, middle-element detection, stack and queue implementations, and sorting algorithms. Each program includes working code in all four languages with complexity notes. The NPTEL Data Structures and Algorithms course from IIT is the free reference curriculum behind these concepts.

Arrays — Core Programs

Arrays are the first data structure tested in most coding assessments because they expose a candidate’s grasp of index arithmetic, boundary conditions, and time-versus-space trade-offs.

Finding the Minimum and Maximum Element

The straightforward single-pass scan: iterate once, track the running min and max. Time: O(n). Space: O(1).

#include <stdio.h>

void findMinMax(int arr[], int n, int *min, int *max) {
    *min = arr[0];
    *max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < *min) *min = arr[i];
        if (arr[i] > *max) *max = arr[i];
    }
}

int main() {
    int arr[] = {3, 1, 7, 2, 9, 4};
    int n = 6, mn, mx;
    findMinMax(arr, n, &mn, &mx);
    printf("Min: %d, Max: %d\n", mn, mx);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {3, 1, 7, 2, 9, 4};
    int n = 6;
    int mn = *min_element(arr, arr + n);
    int mx = *max_element(arr, arr + n);
    cout << "Min: " << mn << ", Max: " << mx << endl;
    return 0;
}

import java.util.Arrays;

public class MinMax {
    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 2, 9, 4};
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();
        System.out.println("Min: " + min + ", Max: " + max);
    }
}

arr = [3, 1, 7, 2, 9, 4]
print(f"Min: {min(arr)}, Max: {max(arr)}")

Reversing an Array In-Place

Two-pointer swap: left pointer starts at index 0, right pointer at index n-1. Swap and advance inward until they meet. Time: O(n). Space: O(1).

#include <stdio.h>

void reverseArray(int arr[], int n) {
    int left = 0, right = n - 1, temp;
    while (left < right) {
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    reverseArray(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    reverse(arr, arr + n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ReverseArray {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int tmp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

arr = [1, 2, 3, 4, 5]
arr.reverse()
print(arr)

Linked Lists — Reverse, Middle, Cycle Detection

Linked list problems test pointer manipulation without array indexing. Three programs appear in nearly every product-company first round.

Reversing a Singly Linked List

The three-pointer iterative approach is O(n) time and O(1) space. Interviewers expect this version, not the recursive one, because it avoids O(n) stack overhead.

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

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

struct Node* reverse(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;
    struct Node* nxt  = NULL;
    while (curr != NULL) {
        nxt        = curr->next;
        curr->next = prev;
        prev       = curr;
        curr       = nxt;
    }
    return prev;
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

Node* reverse(Node* head) {
    Node *prev = nullptr, *curr = head, *nxt = nullptr;
    while (curr) {
        nxt        = curr->next;
        curr->next = prev;
        prev       = curr;
        curr       = nxt;
    }
    return prev;
}

class Node {
    int data;
    Node next;
    Node(int d) { data = d; }
}

public class ReverseList {
    static Node reverse(Node head) {
        Node prev = null, curr = head, nxt = null;
        while (curr != null) {
            nxt       = curr.next;
            curr.next = prev;
            prev      = curr;
            curr      = nxt;
        }
        return prev;
    }
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt        = curr.next
        curr.next  = prev
        prev       = curr
        curr       = nxt
    return prev

Finding the Middle Element

Two pointers: slow moves one step, fast moves two steps per iteration. When fast reaches null, slow is at the middle. Single pass, O(n) time, O(1) space.

void findMiddle(struct Node* head) {
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    printf("Middle: %d\n", slow->data);
}

void findMiddle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << "Middle: " << slow->data << endl;
}

static void findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    System.out.println("Middle: " + slow.data);
}

def find_middle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    print("Middle:", slow.data)

Detecting a Cycle — Floyd’s Algorithm

Floyd’s cycle-detection algorithm (tortoise and hare): if slow and fast ever point to the same node, a cycle exists. O(n) time, O(1) space.

int hasCycle(struct Node* head) {
    struct Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Stacks and Queues

Stack Using an Array

Push increments top before writing; pop reads before decrementing. Overflow and underflow checks are not optional: interviewers mark down missing guards.

#include <stdio.h>
#define MAX 100

int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX - 1) { printf("Stack Overflow\n"); return; }
    stack[++top] = x;
}

int pop() {
    if (top == -1) { printf("Stack Underflow\n"); return -1; }
    return stack[top--];
}

int peek() { return (top == -1) ? -1 : stack[top]; }

#include <iostream>
#define MAX 100
using namespace std;

class Stack {
    int top, arr[MAX];
public:
    Stack() : top(-1) {}
    void push(int x) {
        if (top == MAX - 1) { cout << "Overflow\n"; return; }
        arr[++top] = x;
    }
    int pop() {
        if (top == -1) { cout << "Underflow\n"; return -1; }
        return arr[top--];
    }
    int peek() const { return (top == -1) ? -1 : arr[top]; }
};

class Stack {
    int top = -1;
    int[] arr = new int[100];

    void push(int x) {
        if (top == 99) { System.out.println("Overflow"); return; }
        arr[++top] = x;
    }

    int pop() {
        if (top == -1) { System.out.println("Underflow"); return -1; }
        return arr[top--];
    }

    int peek() { return (top == -1) ? -1 : arr[top]; }
}

class Stack:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.items:
            print("Underflow")
            return -1
        return self.items.pop()

    def peek(self):
        return self.items[-1] if self.items else -1

Queue Using Two Stacks

Enqueue always pushes to s1. Dequeue moves everything from s1 to s2 only when s2 is empty, then pops from s2. Each element crosses between stacks at most once, giving O(1) amortised cost per operation.

#include <stack>
#include <iostream>
using namespace std;

class Queue {
    stack<int> s1, s2;
public:
    void enqueue(int x) { s1.push(x); }

    int dequeue() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue empty\n"; return -1;
        }
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int x = s2.top();
        s2.pop();
        return x;
    }
};

import java.util.Stack;

class Queue {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();

    void enqueue(int x) { s1.push(x); }

    int dequeue() {
        if (s1.isEmpty() && s2.isEmpty()) {
            System.out.println("Queue empty"); return -1;
        }
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) s2.push(s1.pop());
        }
        return s2.pop();
    }
}

class Queue:
    def __init__(self):
        self.s1, self.s2 = [], []

    def enqueue(self, x):
        self.s1.append(x)

    def dequeue(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        if not self.s2:
            print("Queue empty")
            return -1
        return self.s2.pop()

Sorting Algorithms — Complexity and Implementation

Sorting is tested in two ways: implementing a specific algorithm from scratch, and choosing the right algorithm given a constraint. The table below is the reference; Merge Sort and Quick Sort implementations follow.

Algorithm	Best case	Average	Worst case	Space	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No

Merge Sort

Divide-and-conquer: split the array in half recursively, sort each half, then merge. Guaranteed O(n log n) on all inputs.

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

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int *L = malloc(n1 * sizeof(int));
    int *R = malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L); free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Quick Sort

Partition around a pivot; recursively sort sub-arrays. O(n log n) average but O(n²) worst case when the pivot is always the smallest or largest element.

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public class QuickSort {
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high], i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                int tmp = arr[++i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
        int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

def quick_sort(arr, low, high):
    if low < high:
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        pi = i + 1
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

Trees and Graphs — Essential Programs

Height of a Binary Tree

Post-order recursion: height of a node is one plus the maximum of the heights of its left and right subtrees. Base case: a null node has height 0.

struct TreeNode {
    int data;
    struct TreeNode *left, *right;
};

int height(struct TreeNode* root) {
    if (root == NULL) return 0;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

class TreeNode:
    def __init__(self, val):
        self.val   = val
        self.left  = None
        self.right = None

def height(root):
    if root is None:
        return 0
    return 1 + max(height(root.left), height(root.right))

BFS and DFS on a Graph

BFS uses a queue to explore level by level. DFS uses a stack (or recursion) to go as deep as possible before backtracking.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue   = deque([start])
    visited.add(start)
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for nbr in graph[start]:
        if nbr not in visited:
            order.extend(dfs(graph, nbr, visited))
    return order

import java.util.*;

public class GraphTraversal {
    static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        List<Integer> order = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start); visited.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int nbr : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(nbr)) {
                    visited.add(nbr); queue.add(nbr);
                }
            }
        }
        return order;
    }
}

DSA Practice in the AI Era

Indian placement rounds have not replaced classical DSA with AI questions. The Amazon recruitment process still opens with an online assessment that tests algorithmic problem-solving on arrays, trees, and graphs, and that will remain true through at least 2027 based on current hiring patterns.

What has changed: product companies increasingly pair a classical DSA problem with a follow-up about scalability or system design. A candidate who can reverse a linked list but cannot explain why the iterative version is preferred over the recursive one in production code (stack overflow on large lists) gets screened out in the interview debrief. The depth of reasoning matters more than just running the code.

Competitive coding platforms and practice strategies help build that reasoning speed. The next layer after classical DSA (building systems that use AI components) is where TinkerLLM comes in. If you have the linked-list reversal and the Merge Sort solid, TinkerLLM at ₹299 gives you the first 10 AI programming challenges in a structured environment, using Python (the same language you just practiced here). Solving data structure problems in Python and then building LLM-powered features in the same language is not a detour. It is the same skill applied to a wider problem class.

Wildcard character matching in strings tests the same pattern-matching reasoning found in many DSA problems. The wildcard string matching program covers the full algorithm with code across languages.