Why Do We Need Binary Search Trees or Red-Black Trees?

In software engineering and system design, we frequently face a core challenge: how can we efficiently store, search, and dynamically modify data?

Array: If the data is unsorted, finding a specific value requires scanning from beginning to end, giving a time complexity of O(n) — very slow. Even if we sort the array (allowing binary search), inserting or deleting an entry still requires shifting every subsequent element forward or backward, so the modification complexity remains O(n). For example, here is what inserting new data into an array looks like:

#include <stdio.h>

// Insert a new value into a sorted array
void insertSortedArray(int arr[], int *size, int capacity, int value) {
    int i;

    // [Boundary check] Can't insert if the array is already full — avoid writing out of bounds
    if (*size >= capacity) {
        printf("Array is full, cannot insert new value %d\n", value);
        return;
    }

    // [Performance bottleneck] To find the correct position and make room,
    // every element larger than value must be shifted one slot to the right (worst case: O(n))
    for (i = *size - 1; (i >= 0 && arr[i] > value); i--) {
        arr[i + 1] = arr[i]; // shift right
    }
    
    // Place the new value
    arr[i + 1] = value;
    (*size)++;
}

Even if we already know where to insert, if the array holds 1 million entries and you want to insert at the very front, this loop still has to perform 1 million assignment operations.

Linked List: To solve the array’s “mass relocation” problem, we might think of a linked list instead. Inserting a new node into a linked list is extremely fast (O(1)) — but only once you’ve already found the insertion point. Because a linked list’s memory layout is non-contiguous, it can’t use array-style binary search; it can only walk from the head one node at a time, so “finding the position” still costs O(n).

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

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

// Find the correct position in a sorted linked list and insert
void insertSortedList(Node** head, Node* newNode) {
    Node dummy;
    dummy.next = *head;
    Node* current = &dummy;

    // [Performance bottleneck] Can't jump to the middle — must compare nodes one by one
    // Finding the insertion point costs as much as O(n)
    while (current->next != NULL && current->next->data < newNode->data) {
        current = current->next; // walk from head to tail
    }
    
    // Inserting the node itself only requires updating two pointers (O(1)),
    // but finding the position already cost O(n)
    newNode->next = current->next;
    current->next = newNode;
    *head = dummy.next;
}

Hash Table: Lookup and insertion are extremely fast (O(1) on average), but it has one fatal weakness: the data is unordered. When we need to find the “maximum,” the “minimum,” or perform a “range query” (e.g., find all IDs between 100 and 200), a hash table is completely useless.

The Binary Search Tree (BST) and its evolved form, the Red-Black Tree (RBT), were created to solve exactly this problem. They keep insertion, deletion, and search all at the fast O(log n) time complexity, while still preserving the ordering of the data. This makes them the go-to data structure for operating system schedulers, database indexes, and even state management in low-level communication protocols.

Terminology of a tree

Before diving into how BSTs and RBTs work, let’s cover some terminology used for “trees” in computer science. Picture a tree growing upside down (root at the top, leaves at the bottom):

• Node: Each individual data point in the tree.
• Root: The single, unique topmost node of the entire tree.
• Child / Parent: A node extending downward from another node is called that node’s “child”; conversely, the node one level up is its “parent.” In a binary tree, each parent can have at most two children (a left child and a right child).
• Uncle Node: A sibling of the parent node — i.e., another child of the “grandparent” node two levels up. This term becomes important later when determining how a red-black tree should rebalance itself.
• Leaf: A node at the bottom level with no children.
• Subtree: Taking any node in the tree as a new root, that node together with all of its descendants forms a “subtree.”
• NIL Node (empty node): In the definition of a red-black tree, whenever a node lacks a left or right subtree, we imagine an invisible empty node (NIL) attached there, and treat it as a leaf.

Figure 1 shows an example of a binary tree, which we’ll use to get familiar with tree structure.

The root of Figure 1 is node 2. Taking the left half as an example: node 7 is the left child of the top node 2, meaning the top node 2 is the parent of node 7. Going further down, node 7 is itself a parent — it has its own left child, 2, and right child, 6. The leaf nodes are the bottommost 2, 5, 11, and 4.

With these fundamentals in place, we can now move into the world of binary search trees.

Binary Search Tree (BST)

A binary search tree is a data structure based on the “divide and conquer” idea, designed so that both “search” and “insertion” are equally fast.

The rules of a BST are very simple — each node has at most two children (left and right), and the following rules must be strictly followed:

1. Smaller on the left: every node in the left subtree must have a value less than its parent’s value.
2. Larger on the right: every node in the right subtree must have a value greater than its parent’s value.
3. Both the left and right subtrees must themselves be binary search trees.

In other words, a newly inserted value is compared against existing nodes to decide whether it belongs on the left or the right of that node. When an equal value is encountered, there are two common approaches: if duplicates aren’t allowed, the new value is simply discarded; if duplicates are allowed, they are consistently placed on either the left or the right subtree.

Figure 2 shows a standard binary search tree.

Note that this figure looks almost identical to Figure 1 — but a binary search tree is not the same thing as a binary tree. More precisely, a binary tree is the broader category, requiring only that each node have at most two children, while a binary search tree is a binary tree with an additional ordering rule layered on top. So every binary search tree is a binary tree, but the reverse isn’t true.

To get a concrete feel for how a BST combines the strengths of “array-style binary search” and “linked-list-style dynamic insertion,” let’s look directly at its C implementation.

First, we need to define the tree’s node structure. It’s very similar to the linked list node from earlier, except the single next pointer is replaced with two branches, left and right, forming what's called a "two-way branch":

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

// Define the BST node structure
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Helper function to create a new node
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Here, typedef struct defines a custom type named TreeNode with three members:

• int data: stores the node's actual value.
• struct TreeNode* left: a pointer recording the memory address of the left child.
• struct TreeNode* right: a pointer recording the memory address of the right child.

createNode is the function that creates a new node:

• malloc(sizeof(TreeNode)): dynamically requests a block of memory just large enough to hold one TreeNode.
• newNode->data = value;: stores the passed-in value into that memory's data field.
• newNode->left = NULL; and newNode->right = NULL;: default both child pointers to NULL, indicating that this newly created node currently has no children attached (i.e., it's a leaf for now).
• Finally, it returns a pointer to this new node, so calling code (such as the insertion function) can attach it to the existing tree.

Next comes the core “insertion” logic. Because we strictly follow the “smaller on the left, larger on the right” rule, finding the insertion point no longer requires walking “from head to tail (O(n))” as with a linked list — instead, every comparison lets us eliminate one entire side of the current node’s subtree:

// Insert a new node into a BST (recursive)
TreeNode* insertBST(TreeNode* root, int value) {
    // 1. If the tree is empty, or we've reached the bottom (a NIL node),
    //    this is where the new node belongs!
    if (root == NULL) {
        return createNode(value);
    }

    // 2. If the value to insert is "less than" the current node, go left
    if (value < root->data) {
        root->left = insertBST(root->left, value);
    }
    // 3. If the value to insert is "greater than" the current node, go right
    else if (value > root->data) {
        root->right = insertBST(root->right, value);
    }
    
    // 4. Return the (possibly) unchanged node pointer to re-link the tree
    return root;
}

In a BST, since all nodes are linked together via pointers, any node already present in the tree never needs to change its actual position in memory — completely sidestepping the array’s “mass relocation” performance bottleneck.

We mentioned at the start of this article that a hash table’s fatal flaw is that its data is unordered. So how do we retrieve data stored in a BST in sorted order?

This is thanks to the BST’s strict “smaller on the left, larger on the right” property. We simply use a traversal method called “in-order traversal” — following the order “visit the left subtree → read the current node → visit the right subtree” — and the data naturally comes out from smallest to largest! The code is simple:

// In-order traversal: prints BST data from smallest to largest
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // 1. Go as far left as possible (find the smallest)
        printf("%d ", root->data);     // 2. Process the current node (print it)
        inorderTraversal(root->right); // 3. Go right (find larger values)
    }
}

What we just described, however, is the ideal case of random insertion, where the BST ends up nicely balanced and the search complexity is O(log n) (equivalent to binary search).

But suppose the data you insert is already sorted (say, 1, 2, 3, 4, 5). Because of the “larger on the right” rule, the tree will keep growing entirely to the right, eventually degenerating into a single-direction linked list. At that point, search complexity collapses to the worst case, O(n).

Red-Black Tree (RBT)

To prevent a BST from degenerating into a linked list, computer scientists invented the red-black tree. Let’s first introduce what it is, then look at where it’s used.

A red-black tree builds on the basic BST by adding a “color” attribute to every node, governed by five rules:

1. Every node is either black or red.
2. The root node, at the very top of the tree, must be black.
3. All empty nodes (i.e., the NIL nodes at the bottom) are considered black.
4. If a node is red, both of its children must be black (in other words, two consecutive red nodes can never occur).
5. Starting from any node, every path down to a NIL leaf must pass through exactly the same number of black nodes.

Figure 3 shows an example of a red-black tree.

The key to understanding how a red-black tree balances itself lies in how Rule 4 (no consecutive red nodes) and Rule 5 (equal black-node counts) constrain each other. Let’s see how these two rules bound the height of the tree:

1. The shortest possible path (all black):

Per Rule 5, every path from a given node down to any NIL leaf must pass through the same number of black nodes. Say this fixed number is N. If a particular path contains no red nodes at all, its total length is simply N. This is the shortest path possible in a red-black tree.

2. The longest possible path (alternating red-black):

If we deliberately wanted to stretch one side of the tree out (i.e., make it grow lopsided, approaching a linked list), the only way to do so is to squeeze red nodes in between black ones. But per Rule 4, red nodes can’t be consecutive. So the most we can possibly cram in follows a “black-red-black-red-black…” alternating pattern. In this extreme case, the number of red nodes on the path can be at most equal to the number of black nodes (N). So the longest possible path has a total length of at most N (black) + N (red) = 2N.

This rule guarantees that the longest path in the tree is never more than twice the length of the shortest path. In other words, it isn’t 100% perfectly balanced, but it’s “balanced enough” to guarantee O(log n) search time even in the worst case.

At this point you might be wondering: if a red-black tree still follows the BST’s “smaller on the left, larger on the right” rule, wouldn’t inserting 1, 2, 3, 4, 5 in sequence still make it grow into a one-sided linked list toward the right?

This is precisely where the elegance of the red-black tree algorithm lies. It doesn’t just passively check the five rules above — it actively “rebalances” every time a node is inserted or deleted.

In a red-black tree, every newly inserted node is, by default, marked “red.” If inserting it breaks one of the rules, the red-black tree kicks off two mechanisms: recoloring and rotation.

Let’s walk through inserting 1, 2, 3 in sequence:

• Insert 1: As the root, Rule 2 kicks in, forcing it to be black. State: [Black 1].
• Insert 2: Greater than 1, so it goes to the right, defaulting to red. State: [Black 1] → right child [Red 2]. No violation.
• Insert 3 (conflict!): Greater than 2, so it goes to the right, defaulting to red. State becomes [Black 1] → right [Red 2] → right [Red 3]. Now we have two consecutive red nodes, violating Rule 4. See Figure 4.

When a rule is violated, a red-black tree has two possible strategies: “recolor,” or “rotate + recolor.” It always tries recoloring first, and only falls back to “rotate + recolor” if recoloring won’t work. Let’s look at exactly what this means.

In Figure 4 we have three nodes, and to avoid violating Rule 4 we need to change some node colors. But per Rule 2, the root must stay black, so only the other two nodes are eligible for recoloring.

However, per Rule 5, the number of black nodes on the path from any node down to a NIL must be identical. Whether we recolor both remaining nodes to black, or just one of them, we end up violating Rule 5 — because going right from the root would then pass through more black nodes than going left. Figure 5 illustrates this, with the black-node count to each NIL labeled underneath. You can clearly see Rule 5 is violated.

So plain recoloring can’t resolve the conflict here, which means the red-black tree switches to rotation plus recoloring. Rotation comes in two flavors — “left rotation” and “right rotation” — and which one to use depends on whether the rule-violating nodes are clustered mostly on the right (use left rotation) or the left (use right rotation). In the Figure 4 example, the violating nodes are on the right, so a left rotation is used. The result after the left rotation is shown in Figure 6:

Next, per Rule 2, the root must be recolored black. Then, between nodes 1 and 3, one of them must change color — does node 1 turn red, or does node 3 turn black? The answer is that node 1 turns red. As mentioned earlier, the overall logic of a red-black tree is that the black-node count on every path from any node to every leaf must stay equal. So turning a node black usually means you’d need to re-check the entire tree to make sure every path’s black count increased by one accordingly — but coloring a node red, when it doesn’t otherwise violate any rule, avoids that entirely. The corrected result is shown in Figure 7:

Now suppose we insert a new node, 4. This again breaks Rule 4, so the red-black tree first checks whether recoloring alone can fix it. As Figure 8 shows, in this case we can indeed fix things by simply recoloring two nodes to black.

This brings us to the condition for when a red-black tree only needs “recoloring” versus when it needs “rotation plus recoloring”: if the newly inserted node’s uncle is black, rotation plus recoloring is required. If the uncle is red, recoloring alone is sufficient.

Following this logic, you can try working out what happens if we then insert 5 — see the result in Figure 9.

Under the red-black tree’s strict oversight, its two automatic correction mechanisms — recoloring and rotation — working in alternation, forcibly fold what would have been a straight line into a well-balanced, symmetric branching structure. This is the core value of the red-black tree. You might now worry: doesn’t this automatic correction mechanism slow down insertion?

The answer is: almost not at all. Both recoloring and rotation run in O(1) (constant time), because at the low level, the actual operations involved are extremely lightweight:

• What recoloring really is: at the code level, a node’s color is typically just an integer or an enum. “Recoloring” is nothing more than modifying a variable’s value in memory (e.g., node->color = BLACK;). This is a direct memory assignment — whether the tree has a hundred nodes or a million, this line of code always takes the same amount of time, hence O(1).
• What rotation really is: rotation might sound like uprooting and relocating the whole tree, but it never actually moves any node’s physical position in memory. All a rotation does is “re-link pointers.” Take a left rotation as an example — we only need to update the left, right, and parent pointers among three nodes (the parent, the node itself, and its right child). That's roughly six pointer updates, requiring no loops or recursive traversal — a fixed number of steps, hence extremely fast O(1).

Finding the insertion point costs O(log n), but the structural fix-up after insertion (rotation and recoloring) only costs O(1) up to at most O(log n) pointer operations. Put together, the overall insertion complexity remains solidly at O(log n). Let’s look at the implementation:

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

// Define the color enum
typedef enum { RED, BLACK } Color;

// Define the red-black tree node structure
typedef struct Node {
    int data;
    Color color;
    struct Node *left, *right, *parent;
} Node;

// ---------------------------------------------------------
// [Core Operation 1] Left Rotation - Time complexity O(1)
// Purpose: restructure the tree purely by re-linking pointers,
// without moving any data in memory
// ---------------------------------------------------------
void leftRotate(Node **root, Node *x) {
    Node *y = x->right; // y is x's right child, about to be promoted
    
    // Step 1: hand y's left subtree over to x as its new right subtree
    x->right = y->left;
    if (y->left != NULL) {
        y->left->parent = x;
    }
    
    // Step 2: promote y into x's original position (update x's parent's pointer)
    y->parent = x->parent;
    if (x->parent == NULL) {
        *root = y; // x was the root; now y becomes the root
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    
    // Step 3: push x down to become y's left child
    y->left = x;
    x->parent = y;
}

// ---------------------------------------------------------
// [Core Operation 2] Right Rotation - Time complexity O(1)
// Purpose: fully symmetric to left rotation; used to level out
// the tree's height when the left side is too heavy
// ---------------------------------------------------------
void rightRotate(Node **root, Node *x) {
    Node *y = x->left; // y is x's left child, about to be promoted
    
    // Step 1: hand y's right subtree over to x as its new left subtree
    x->left = y->right;
    if (y->right != NULL) {
        y->right->parent = x;
    }
    
    // Step 2: promote y into x's original position (update x's parent's pointer)
    y->parent = x->parent;
    if (x->parent == NULL) {
        *root = y; // x was the root; now y becomes the root
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    
    // Step 3: push x down to become y's right child
    y->right = x;
    x->parent = y;
}

// ---------------------------------------------------------
// [Core Operation 3] Insert Fixup
// Purpose: when consecutive red nodes are found, decide whether
// to "recolor" or "rotate"
// ---------------------------------------------------------
void insertFixup(Node **root, Node *z) {
    // While z's parent is red, Rule 4 is violated (no consecutive red nodes) — fix it
    while (z->parent != NULL && z->parent->color == RED) {
        
        // Case where z's parent is the grandparent's LEFT child
        // (the mirror-symmetric case, parent as right child, is handled analogously)
        if (z->parent == z->parent->parent->left) {
            Node *uncle = z->parent->parent->right; // find the uncle node
            
            // Case 1: uncle is red -> [Recolor]
            if (uncle != NULL && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED; // grandparent turns red
                z = z->parent->parent;          // move focus up to grandparent and continue checking
            } 
            // Case 2: uncle is black (or NIL) -> [Rotate + Recolor]
            else {
                // If z happens to be a right child (forming a ">" shape),
                // rotate left first to straighten it out
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(root, z);
                }
                // Recolor and right-rotate the grandparent (resolving the "/" shape)
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent); // right rotation to level things out
            }
        } else {
            // (Mirror-symmetric logic for the case where the parent is the right child, omitted for brevity)
        }
    }
    // Rule 2: no matter what, force the root to always be black
    (*root)->color = BLACK;
}

Red-black trees have many real-world applications, the most classic example being the Linux operating system’s process scheduler (CFS). In modern Linux, the core component responsible for deciding “which process gets to run on the CPU next” is called the Completely Fair Scheduler (CFS). CFS tracks a “virtual runtime” (vruntime) for every running process. To achieve fairness, the system always picks the process with the smallest vruntime (i.e., the one that has run the least and most urgently needs CPU time) to run next. At any given moment, countless processes are starting, pausing, and finishing, so the scheduler needs to perform "insert new process," "remove finished process," and "find the minimum" extremely frequently. With an array or linked list, searching or inserting costs O(n), which would grind the system to a halt. With a hash table, insertion is fast, but hash tables are unordered, so instantly finding the "minimum" is impossible. This is exactly where a red-black tree shines: processes are stored in the tree keyed by vruntime, so the bottom-left-most leaf is always the process with the smallest vruntime. Finding the minimum, inserting a new process, and removing an old one can all be done in O(log n).

Additionally, C++’s std::map and std::set: these two containers in the C++ Standard Template Library (STL) are required to always keep their data sorted, with worst-case operation complexity strictly bounded at O(log n). As a result, most C++ compilers implement them under the hood using a red-black tree. We'll go into more detail on this once we get to the C++ portion of this series.

In summary, I hope this article has given readers a solid foundational understanding of binary search trees and red-black trees.

Welcome to Ac Studio! Read This First

Binary Search Tree and Red-Black Tree was originally published in The Coding Handbook on Medium, where people are continuing the conversation by highlighting and responding to this story.

After introducing Stack in the previous article, in this article we introduce the Queue.

A Queue is a data structure that follows the First-In-First-Out (FIFO) rule — basically just like waiting in line to buy a drink: whoever gets in line first leaves first.

No matter how a Queue is implemented, it always comes down to the following operations:

• Enqueue: Add a new data to the rear of the Queue.
• Dequeue: Remove the data from the front of the Queue.
• isEmpty: Check whether the Queue has no data left.
• isFull: Check whether the Queue has reached its capacity limit; this is especially common in fixed-capacity array based queue implementations. Linked lists based queue usually don’t have a pre-set fixed capacity, we will explain this more clearly later.
• Peek / Front: Look at the data currently at the front of the line without removing it.

In C, there are generally two ways to implement a queue:

• Array-based Queue: Implemented using an array. Its advantage is that the implementation is simple, and memory allocation is contiguous. The downside is that the capacity is usually fixed upon initiation; if more data needs to be accommodated, a larger array typically has to be created separately and the data moved over. Also, without the Circular Queue technique (introduced later in this article), space can be wasted.
• Linked List-based Queue: Implemented using a linked list. The advantage is that it can grow dynamically with the amount of data, without needing to pre-set a fixed capacity — as long as the system still has enough memory, more data can keep being added. The downside is that it’s more complex to implement.

Implementing a Queue with an Array

Here’s how an Array-based Queue can be implemented in C:

#define MAX_SIZE 5 // Define the maximum capacity of the queue as 5

typedef struct {
    int items[MAX_SIZE]; // The "container" used to hold data (array)
    int front;           // Records which position in the array holds the "frontmost" data
    int rear;            // Records which position in the array holds the "rearmost" data
} Queue;

front and rear are not themselves data stored in the Queue, they are index values used to record the positions of data. The array's slots are numbered starting from 0 (0, 1, 2, 3, 4). We need front to remember "which slot holds the next piece of data ready to leave," and rear to remember "which slot holds the most recently added data."

Initializing the Queue looks like this:

void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

During initialization we set both front and rear to -1. Because array indexing in C starts at 0, if we set the initial value to 0, the program would mistakenly think slot 0 already contains data. Setting it to -1 is a common design convention in this kind of implementation, used to indicate that there is currently no valid data position. Since array indices start at 0, -1 can never be a valid index, so it conveniently serves to represent an empty Queue.

This might still feel a bit abstract, so here’s a step-by-step example of how front and rear move.

Suppose we have a Queue with MAX_SIZE 5, set up as above:

Index:   0    1    2    3    4
Array: [   ][   ][   ][   ][   ]

Since there’s nothing in it yet, as described above, we set both front and rear to -1.

Now suppose A is added to the Queue.

Index:   0    1    2    3    4
Array: [ A ][   ][   ][   ][   ]
         ↑
    front, rear

Since there’s only A in the line, front (the next piece of data ready to leave) is A's index, 0. rear (the most recently added data) is also index 0.

Now suppose B and C also enter the Queue in order.

Index:   0    1    2    3    4
Array: [ A ][ B ][ C ][   ][   ]
         ↑         ↑
       front      rear

At this point A is still the next piece of data ready to leave (remember, the Queue’s characteristic is FIFO, so A must leave first), so front stays at 0. The most recently added data is C, so rear is 2. This is the rule governing how front / rear change.

Checking whether the Queue is empty (isEmpty) or full (isFull)

In this linear-array Queue implementation, we can use front == -1 to indicate that the Queue is empty.

At initialization, both front and rear are -1, meaning the Queue has no data yet. When the last piece of data is removed, we reset both front and rear back to -1 inside dequeue(), so the Queue returns to the empty state (the code implementation follows below).

bool isEmpty(Queue *q) {
    return q->front == -1; // Check whether front is -1 to determine if the queue is empty
}

Checking for fullness is a matter of checking whether rear has reached the last slot:

bool isFull(Queue *q) {
    return q->rear == MAX_SIZE - 1;
}

With initialization and state-checking covered, the remaining core operations are Enqueue, Dequeue, and Peek.

Enqueue

When new data needs to be added to the queue, we first check whether the queue is already full (isFull). If there's still room, we move rear forward by one slot and place the data there. One thing to note in particular: if this is the "first" piece of data being added, we must also advance front from -1 to 0 at the same time, so that we know where the front of the line is.

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is Full, cannot add %d\n", value);
        return;
    }
    
    // If this is the first item, set front to 0
    if (q->front == -1) {
        q->front = 0;
    }
    
    q->rear++;                   // Move rear forward by one slot
    q->items[q->rear] = value;   // Place the data in the slot pointed to by rear
    printf("Successfully added %d\n", value);
}

Dequeue

When someone leaves the line, we likewise first check whether the queue is empty (isEmpty). If there is data, we take out the data at the front index, then move front forward by one slot, meaning the person who was originally second in line is now first. Note that the data at the slot that was just dequeued still physically exists there — only the front index position has changed.

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is Empty, cannot remove data\n");
        return -1; // Return -1 to indicate an error or no data
    }
    
    int item = q->items[q->front]; // Take out the frontmost data
    q->front++;                    // Move front forward by one slot
    
    // If the queue becomes empty after removal, reset both front and rear to -1
    if (q->front > q->rear) {
        q->front = -1;
        q->rear = -1;
    }
    
    return item;
}

Peek / Front

The purpose of peek is to look at the data pointed to by front without removing it from the Queue. This is the simplest operation. We just need to confirm the queue isn't empty, then return the data pointed to by front, without needing to change the values of front or rear.

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("The queue is currently empty\n");
        return -1;
    }
    return q->items[q->front];
}

This function exists because sometimes we just want to check “what’s the next task or next piece of data,” so we can peek at it and then write a conditional branch based on it.

The Drawback of the Linear Array Queue: False Overflow

If you look closely at the implementation logic above, you’ll notice a serious problem: Suppose our MAX_SIZE is 5. We add 5 items (at this point rear = 4, the queue is full), then remove 3 items (at this point front = 3). At this point, even though the first 3 slots of the array (0, 1, 2) have already been used and freed up, because rear is still 4, calling isFull() again would still return true. This wastes the space at the front, making it impossible to add new data. This situation — where space is clearly available at the front of the array, but no more data can be added because rear has already reached the end — is usually called False Overflow.

To solve this problem, we can use the Circular Queue technique.

Circular Queue

The concept behind a circular queue is simple: “connect the head and tail of the array to form a circle.” When rear reaches the last slot of the array, as long as there's still space at the next position, it wraps back around to slot 0 to continue placing data.

One difference between a circular queue and a linear queue is that the relative size of front and rear can no longer be directly used to determine whether the Queue is empty or full. For example, front might be greater than rear, yet the Queue may still contain data.

In C, the most common way to achieve this “wrap-around” effect is to use the modulo operator (%). For example, when rear reaches index 4, the next step, (4 + 1) % 5 = 0, perfectly computes that the next position is slot 0.

Modifying the Checks and Operations for a Circular Queue

To convert the original linear queue into a circular queue, besides letting front and rear move cyclically, we also need to redesign how we determine whether the Queue is "empty" or "full."

Here we continue using the same design as the linear queue before it: front == -1 indicates the Queue is empty — at initialization, both front and rear are -1; when the last item is removed, both are also reset back to -1, returning the Queue to the empty state.

As long as the next position after rear would collide with front, that means the queue is full:

bool isCircularFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

Let’s walk through an example. Suppose the queue currently already contains 4 items:

Index:   0    1    2    3    4
Array: [ A ][ B ][ C ][ D ][   ]
         ↑              ↑
      front            rear

A, B, C, D are placed at indices 0–3, so front is 0 and rear is 3. At this point, the next position after rear is:

(3 + 1) % 5 = 4

And front is 0. Since 4 ≠ 0, the Queue is not yet full, and one more item, E, can still be added:

Index:   0    1    2    3    4
Array: [ A ][ B ][ C ][ D ][ E ]
         ↑                   ↑
       front                rear

Now rear is 4, and the next position after rear becomes:

(4 + 1) % 5 = 0

And front is also exactly 0, so:

(q->rear + 1) % MAX_SIZE == q->front

holds true, and the Queue is determined to be full.

Here’s the full code for a circular queue:

// Check whether the circular queue is empty
bool isCircularEmpty(Queue *q) {
    return q->front == -1;
}

// Check whether the circular queue is full
bool isCircularFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// Circular queue enqueue
void circularEnqueue(Queue *q, int value) {
    if (isCircularFull(q)) {
        printf("Queue is full, cannot add %d\n", value);
        return;
    }

    // If this is the first item, initialize front
    if (isCircularEmpty(q)) {
        q->front = 0;
        q->rear = 0;
    } else {
        // Use % to achieve the wrap-around effect
        q->rear = (q->rear + 1) % MAX_SIZE;
    }

    q->items[q->rear] = value;
    printf("Successfully added %d\n", value);
}

// Circular queue dequeue
int circularDequeue(Queue *q) {
    if (isCircularEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }

    int item = q->items[q->front];

    // If front and rear point to the same position,
    // it means the queue becomes empty after removing this item
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        // Use % to achieve the wrap-around effect
        q->front = (q->front + 1) % MAX_SIZE;
    }

    return item;
}

Implementing a Queue with a Linked List

In C, we first need to define the linked list’s “Node,” and then define a queue structure that contains front and rear pointers.

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

// Define the linked list node
typedef struct Node {
    int data;           // The stored data
    struct Node *next;  // Pointer to the next node
} Node;

// Define the queue, containing pointers to the front and rear
typedef struct {
    Node *front;
    Node *rear;
} LinkedListQueue;

Initialization and Checking for Emptiness

In the linked-list version, initialization is very straightforward — just point both front and rear to NULL. Likewise, as long as front is NULL, the queue is considered completely empty. Here, there's usually no need to implement an isFull() like there is for a fixed-size array queue, because the queue has no pre-set fixed capacity; each time data is added, a new node can be created via dynamic memory allocation. However, this doesn't mean the capacity is unlimited — if the system doesn't have enough available memory, malloc() can still fail, in which case no more data can be added.

// Initialize the queue
void initLLQueue(LinkedListQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// Check whether the queue is empty
bool isLLEmpty(LinkedListQueue *q) {
    return q->front == NULL;
}

Enqueue

When new data needs to be added, we dynamically allocate (malloc) a block of memory for the new node. If the queue is empty, this new node becomes both front and rear; if the queue already has data, we attach the new node after the current rear, then update rear to point to this new node.

void llEnqueue(LinkedListQueue *q, int value) {
    // Dynamically allocate memory for the new node
    Node *newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL; // Since it's placed at the very end, next points to NULL

    // If the queue is empty, both front and rear point to the new node
    if (isLLEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        // Attach the new node after the current rear, and update the rear pointer
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Successfully added %d\n", value);
}

Dequeue

When removing data, we first temporarily store the node pointed to by front, take the data out of it, and then move front forward to the next node (front->next). Something worth flagging here: in C, dynamically allocated memory always has to be freed manually (free), or it will cause a memory leak. Additionally, if the queue becomes empty after removing the node, we also need to remember to set rear back to NULL.

int llDequeue(LinkedListQueue *q) {
    if (isLLEmpty(q)) {
        printf("Queue is empty, cannot remove data\n");
        return -1;
    }

    Node *temp = q->front;      // Temporarily store the node to be removed
    int item = temp->data;      // Extract the data

    q->front = q->front->next;  // Move front forward to the next node

    // If the queue becomes empty after removal, set rear to NULL as well
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp); // Free the memory
    return item;
}

Peek / Front

This operation is largely the same as the array version — just confirm the queue isn’t empty, then directly return the data in the front node.

int llPeek(LinkedListQueue *q) {
    if (isLLEmpty(q)) {
        printf("The queue is currently empty\n");
        return -1;
    }
    return q->front->data;
}

Conclusion

To sum up, this article covered the core FIFO concept of the Queue, and implemented two mainstream versions:

• Array-based Queue: Uses an array to store data, with simple memory allocation and good cache locality — suitable for cases with a clear upper bound on data volume, or where a fixed capacity is acceptable.
• Linked List-based Queue: Uses dynamic memory allocation, without needing to pre-specify a fixed capacity — suitable for cases where the amount of data varies significantly and is hard to estimate in advance; however, each node requires extra space for a pointer, and nodes aren’t necessarily contiguous in memory.

So, after learning about Queues, where are they actually used in real-world software development? Here are two examples:

Operating system task scheduling: When multiple programs or jobs are waiting to be processed by the CPU, the Queue is one of the common data structures used in OS scheduling. For example, in Round-Robin scheduling (a scheduling method where each job takes turns using the CPU for a fixed time slice), a Queue can be used to manage jobs waiting for the CPU in order, letting each job take turns getting a small slice of CPU time. Another classic application of Queue is print spooling — under FIFO scheduling, jobs are typically processed in the order they were submitted, so a job submitted earlier gets processed first.

Graph algorithms: There’s a very famous algorithm in graph theory called Breadth-First Search (BFS), whose core relies on a Queue for its implementation. When we’re navigating a maze or analyzing relationships in a social network, BFS uses the Queue to ensure we explore nodes “from near to far, one layer at a time.”

The concept of Queue is simple, and it’s an important foundation for getting started in computer science. Once you’ve mastered it, learning more advanced material later becomes much easier.

Welcome to Ac Studio! Read This First

C Programming — Queue was originally published in The Coding Handbook on Medium, where people are continuing the conversation by highlighting and responding to this story.

In the article introducing dynamic memory allocation, we explained Stack and Heap; they are different regions of memory space and are used at different times.

This article will introduce the Stack, but what we are introducing here is the Stack in data structures. It is a concept we define that regulates how data is stored, rather than a physically existing block of memory like the one we introduced in dynamic memory allocation.

Stack

A Stack is a data structure that follows the LIFO (Last-In, First-Out) principle, somewhat like a can of Pringles. When we put data in, it must be inserted from the top, and when we take data out, it must also be removed from the very top. Generally, when implementing it in C, we often define the following basic operations:

• Push: Add data to the top of the Stack.
• Pop: Remove and return the data at the top of the Stack.
• Peek/Top: Return the data at the top of the Stack, but do not remove it.
• isEmpty: Check if there is still data inside the Stack.

For beginners, the design of a Stack might seem quite useless. Why would I design a data structure that only allows me to put data on top, take data from the top, and doesn’t even let me freely modify values in the middle? The answer is that in certain scenarios, this seemingly restrictive setup is actually a protection mechanism.

For example, when you design the “Undo” and “Redo” functions in drawing software, you want the system to “retrace its steps” to prevent your brain from crashing while coding by writing code that extracts intermediate processes. Or, take the “Back” and “Forward” buttons in a browser — you wouldn’t want to suddenly jump to a completely different page. In these cases, the Stack demonstrates its functionality and serves as a protection mechanism.

In C, to build a Stack using an array, we need two things: an array data to hold the data, and a pointer (index) top to remember where the data is currently stacked up to (for instance, top = 2 means the data is currently stacked from 0 to 2). When we initialize a Stack, since it is still empty, top = -1. We can package them into a struct.

#include <stdio.h>
#include <stdbool.h> // To use bool, true, false

#define MAX_SIZE 5   // For teaching purposes, we first define that the Stack can hold at most 5 elements

// Define the Stack structure
typedef struct {
    int data[MAX_SIZE]; // The actual "container" used to store data
    int top;            // The "pointer" that always points to the topmost data (stores the array index)
} Stack;

You might notice that we added typedef in front of the struct and wrote Stack outside the final brace. In C, the function of typedef is to "define a new data type." If we only wrote the original struct Stack { ... };, every time we wanted to create a Stack variable in the future, we would have to write: struct Stack myStack;.

But by adding typedef, we are essentially telling the compiler: "Treat this structure as a new custom type named Stack." In the future, we simply and concisely write: Stack myStack;. This saves the trouble of typing struct every time and makes the code look intuitive.

Furthermore, note that the definition of this type is written at the very top, outside our main function main. This is because you will write the main tasks inside the main function, and then write the previously mentioned functions like pop, push, etc., separately. Since these functions also need to pass the Stack as a parameter, you must define this data type first so that this Stack becomes universally accessible (globally defined), and the compiler won't throw an error when it encounters pop or push.

Next, let’s write some common Stack functions. Notice that the parameters passed into these functions are pointers pointing to the Stack, rather than passing the Stack itself directly. There are two main reasons behind this:

1. If the Stack is passed directly, C will copy the entire Stack from the main function and pass it to the function. So the function gets a clone. Even if it pushes data into the clone, the clone will be freed when the function ends (refer back to dynamic memory allocation), resulting in absolutely no real changes. However, if we pass a pointer, the function can find the memory address of the Stack and push the data into it, thus actually modifying the values.
2. Suppose passing the entire Stack instead of its pointer; this would also waste a massive amount of performance. If the Stack stores a thousand integers, it is far more efficient to pass an 8-byte pointer instead.

So in practice, the scenario for using push will look like the following:

#include <stdio.h>

// Define the Stack specifications
typedef struct {
    int data[10];
    int top;
} Stack;

// Here we first define what the push function "looks like"
// Its first parameter is Stack *s, meaning it needs a "house number (address)"
void push(Stack *s, int value) {
    /* It's okay if you don't understand what push is doing; it will be explained below in the article
    */    
    s->top++;
    s->data[s->top] = value;
}

int main() {
    // 1. Declare a local variable my_stack inside main
    Stack my_stack;
    my_stack.top = -1; // Initialization

    // 2. Key point: when calling the function, add & in front of the variable
    // This way, what is passed in is the "address" of my_stack
    push(&my_stack, 10); 
    push(&my_stack, 20);

    // Verify that the original was indeed modified
    printf("The top of the Stack is now: %d\n", my_stack.data[my_stack.top]);

    return 0;
}

After seeing the main architecture, we can look at the implementation details of each function. First are push (putting data into the Stack) and pop (taking data out of the Stack).

To put data in using push, we only need two steps: first move the pointer, then insert the data. In the code below, s is a pointer pointing to the Stack, and -> is the Arrow Operator in C. Its function is to access members inside a structure. Basically, s->top is equivalent to (*s).top (dereference the pointer first, then access the member).

void push(Stack *s, int value) {
    // Check before acting: if it's full, you can't stuff anymore in!
    if (isFull(s)) {
        printf("Error: Stack is full (Overflow)!\n");
        return;
    }
    
    s->top++;                // Step 1: Move the top pointer up one slot (from -1 to 0)
    s->data[s->top] = value; // Step 2: Put the new data into the slot top is currently pointing at
    printf("Successfully pushed: %d\n", value);
}

Finally, there’s the Pop function to take data out. There is a counter-intuitive design here: we actually don’t need to truly “delete” the number in the array.

int pop(Stack *s) {
    // Check before acting: if it's empty, don't take anything
    if (isEmpty(s)) {
        printf("Error: Stack is empty (Underflow)!\n");
        return -1; // Return an error code
    }
    
    int poppedValue = s->data[s->top]; // Step 1: First take out and store the top data
    s->top--;                          // Step 2: Move the top pointer down one slot
    return poppedValue;                // Step 3: Give the newly extracted data to the caller
}

After we subtract 1 from top, although the number in that slot remains in memory, it is already "invisible" to the Stack. The next time we do a Push, the new data will naturally overwrite it. Doing this saves the performance cost of clearing the array to zero.

When dealing with Stacks, two very common errors are Stack Overflow and Stack Underflow.

• Stack Overflow: The box is already full, but you continue to Push things into it. The reasons it occurs are usually (1) the static array size is set too small, or (2) the program falls into an infinite loop, constantly calling itself, leading to the exhaustion of internal Stack space.
• Stack Underflow: The box is empty, but you Pop things from it. The program will try to grab data that simply doesn’t exist, resulting in a logical program error. This is also why we must check if the Stack is empty before doing a Pop.

Next are isEmpty and isFull, which are used to check if the Stack is empty or full, respectively. The way to determine this is to see if the position of top is at the very bottom or at the maximum capacity.

// Check if the Stack is empty
bool isEmpty(Stack *s) {
    return s->top == -1; // If top is still at -1, it means it is empty
}

// Check if the Stack is full
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1; // The index of the last slot in the array is MAX_SIZE - 1
}

Monotonic Stack

A Monotonic Stack is not a new data type, but rather a processing strategy that utilizes a Stack to maintain “monotonicity” (increasing or decreasing). There are two types of Monotonic Stacks: the elements inside the Stack remain either monotonically increasing or monotonically decreasing. Therefore, it is specifically used to solve problems like “finding the next greater/smaller element,” which can significantly optimize time complexity.

Let’s use a problem directly as an example. Suppose a problem gives an array and asks us to find, for each element, the element to its right that is smaller than it; otherwise, return the element itself. For example, for [8, 4, 6, 2, 3], the answer is [4, 2, 2, 2, 3]. This is a scenario where a Monotonic Stack is very suitable.

We can imagine a Monotonic Stack as a “to-do list of numbers that haven’t found their answers yet.” In this example, the Stack’s task is to help each number find its “next smaller value.” If it hasn’t been found yet, this number (or its index) has to wait in line in the Stack. Once a new incoming number is smaller than it, it can leave the Stack and get its answer.

We prepare an empty Stack that stores indices (Index), because indices allow us to accurately fill the values into the answer array.

• Encounter 8 (Index 0): The Stack is empty, 8 goes in and sits first. Stack: [0] (corresponding value 8)
• Encounter 4 (Index 1): We find that 4 is smaller than the 8 at the top of the Stack! Action: 8 has found its savior. We kick index 0 out of the Stack, and record ans[0] = 4. Now the Stack is empty, so 4 goes in to line up. Stack: [1] (corresponding value 4)
• Encounter 6 (Index 2): 6 is greater than 4. This does not meet our condition of finding a “smaller value.” Action: 6 also goes in to line up. The Stack maintains a state of increasing from bottom to top. Stack: [1, 2] (corresponding values 4, 6)
• Encounter 2 (Index 3): Here comes the key point! 2 is smaller than the 6 at the top of the Stack, and also smaller than the 4 below it. Action 1: 6 has found its savior (which is 2). Index 2 is out, record ans[2] = 2. Action 2: 4 has also found its savior (also 2). Index 1 is out, record ans[1] = 2. Now the Stack is empty again, 2 goes in to line up. Stack: [3] (corresponding value 2)
• Encounter 3 (Index 4): 3 is greater than 2. Action: 3 goes in to line up. Stack: [3, 4] (corresponding values 2, 3)

Finally, the remaining indices 3 and 4 in the Stack indicate that there are no smaller numbers to their right. According to the problem requirements, we make their answers equal to themselves.

Now that we are clear about the whole operational logic, let’s actually translate this “finding a savior” process into C language code. We will continue to use the previously written Stack structure and the push, pop, and isEmpty functions.

C Implementation of Monotonic Stack

#include <stdio.h>
#include <stdbool.h>

// Assuming the previously defined Stack structure, push, pop, and isEmpty have all been written
// ... (Basic Stack functions omitted here) ...

void findNextSmaller(int arr[], int size) {
    Stack my_stack;
    my_stack.top = -1; // Initialize Stack
    
    int ans[size];     // Array used to store the final answers
    
    // Iterate through all numbers in the array
    for (int i = 0; i < size; i++) {
        // Core logic: While the Stack is not empty, and "the new incoming number" is smaller than "the number corresponding to the index at the top of the Stack"
        while (!isEmpty(&my_stack) && arr[i] < arr[my_stack.data[my_stack.top]]) {
            // This means the number at the top of the Stack has found its savior!
            int top_index = pop(&my_stack); // Kick it out of the to-do list
            ans[top_index] = arr[i];        // Record its next smaller value
        }
        // After processing, the current number (its index) itself also needs to go into the Stack to line up and wait for its savior
        push(&my_stack, i);
    }
    
    // The array has been fully traversed, but there might still be leftover indices in the Stack that haven't found a savior
    while (!isEmpty(&my_stack)) {
        int leftover_index = pop(&my_stack);
        ans[leftover_index] = arr[leftover_index]; // According to the problem, if there's no smaller value on the right, set it to itself
    }
    
    // Print the final answers to verify the result
    printf("Original array: ");
    for (int i = 0; i < size; i++) printf("%d ", arr[i]);
    
    printf("\nAnswer array: ");
    for (int i = 0; i < size; i++) printf("%d ", ans[i]);
    printf("\n");
}

int main() {
    int arr[] = {8, 4, 6, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    findNextSmaller(arr, size);
    
    return 0;
}

Why use a Monotonic Stack?

You might think: “Couldn’t I just use two for loops—one to look at the current number, and another to scan to the right to find a smaller number—to calculate the answer?"

Thinking this way is also correct, but if the array length is 100,000, in the worst-case scenario using a double for loop (e.g., the array is already sorted from smallest to largest), the time complexity would be O(N²). The program would need to execute up to 10 billion times, which will absolutely result in a Time Limit Exceeded error.

However, using a Monotonic Stack, observing the code above closely reveals: each element (index) will be pushed in at most once, and popped out at most once. Therefore, even though there is a while loop nested inside, the overall total number of operations is still proportional to the array length. Its time complexity is significantly reduced to O(N). This is the value of the Monotonic Stack in this scenario.

• C Programming — Pointers in C
• C Programming — Linked List
• C Programming — Dynamic Memory Allocation
• C Programming — Double Pointers and Function Pointers
• Understanding Time and Space Complexity of Algorithm
• Welcome to Ac Studio! Read This First

C Programming — Stack was originally published in The Coding Handbook on Medium, where people are continuing the conversation by highlighting and responding to this story.

Imagine you are a newly hired software engineer. Your boss asks you to write a feature to check if there are any repeat customers in today’s orders. So you take out the first order and compare it with the remaining orders; then take out the second order and continue to compare it with the remaining orders, and so on. You used 100 pieces of data for testing, and it worked perfectly. Thus, the code was officially deployed online. As a result, when 10,000 orders flooded in during the long weekend, your website crashed immediately.

The problem is not that your code has a bug, but that you underestimated the “growth trend of the time required for program execution when data grows.” Assuming there are 10 pieces of data, this snippet of code will probably execute about 100 comparisons. But when the data increases by 1,000 times to 10,000, the number of program executions becomes 100,000,000 times.

This is why learning complexity is important. Since everyone’s computer performance is different, we need an objective standard to evaluate how terrifying a program’s resource consumption will become when the input data volume approaches infinity.

To solve this problem, computer scientists introduced Big O Notation.

Big O Notation focuses on the “growth trend.” For example, when we say the time complexity of an algorithm is O(n), it means that as the data volume n increases, the execution time will increase linearly.

Big O operates on two important principles:

1. Ignore constant coefficients: If your program needs a loop to run through the data twice, strictly speaking, it should be O(2n). However, as n increases, the impact of multiplying by two is very small because we care about the rate of growth. Therefore, we directly omit the factor of two and write it as O(n).
2. Keep only the highest order term: Similarly, suppose the number of times a program executes is n² + 5n + 1000. When n is only 10, the trailing 5n + 1000 has a significant impact. But when n becomes extremely large, the trailing 5n and 1000 have almost no effect. Since we care about extremely large n when evaluating complexity, we only look at the highest order term that truly makes an impact, writing it as O(n²).

Whether it is time or space complexity, we use Big O Notation to represent it. It indicates how many operation steps (time) and memory (space) will be consumed as the data volume n grows.

Going back to the opening example of comparing orders, let’s calculate its time complexity. Assuming there are n pieces of data, you first take the first piece of data and compare it with the remaining n-1 pieces. Then you take the second piece and compare it with the remaining n-2 pieces, and so on. Therefore, the total number of executions is: (n-1)+(n-2)+…+1=n(n-1)/2.

This is equivalent to (1/2)n²-(1/2)n. Next, we apply the simplification principles we just learned by ignoring the coefficient 1/2 and the lower order term, resulting in a time complexity of O(n²).

Now that we’ve looked at time complexity, what about the space complexity of this algorithm? In this example, we are simply comparing values back and forth within the original orders; we didn’t create a massive array or database for this task. In other words, we can complete this job with a simple double loop, requiring only two basic variables, i and j. This means that even if the data volume surges, we still just use two loops, and the extra variables needed remain a fixed quantity. This indicates a space complexity of O(1).

So, how do we solve the problem of excessively high time complexity? We could create an empty “seen customers list.” For every order read, we check the list to see if it repeats; if not, we save this order into it (we will cover the technical details of this in an article introducing hash tables). This way, you only need to search once, and the time complexity becomes O(n). However, because you created a new list, your space complexity also becomes O(n). This is a fascinating aspect of algorithms, as you are trading space for time.

Let’s look at more examples to familiarize ourselves with time and space complexity.

Suppose you want to find a specific number in an increasing sequence. You can choose to write a for loop to go through all the numbers to find the target, or you can opt for Binary Search. These two approaches will result in quite different complexities.

First, suppose you use a for loop:

def linear_search(arr, target):
    # n is the length of the array
    for i from 0 to len(arr) - 1:
        if arr[i] == target:
            return i  # Found it, return the position
    return -1         # Not found after finishing, return -1

In terms of time complexity, you might get incredibly lucky and find the number at the very first position of the array, which is O(1); or the number might appear at the very last position, which is O(n). Generally speaking, we usually consider the worst-case scenario (based on system reliability considerations), so we say its time complexity is O(n). As for space complexity, since you only need a fixed number of variables, it is O(1).

Suppose you use Binary Search:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2  # Find the midpoint
        
        if arr[mid] == target:
            return mid            # Exact hit on the midpoint
        elif arr[mid] < target:
            left = mid + 1        # Target is larger, discard the left half
        else:
            right = mid - 1       # Target is smaller, discard the right half
            
    return -1                     # Not found after finishing, return -1

The best case is that you hit the number you’re looking for on the very first cut, O(1). The worst case is finding it on the very last cut. Since every time you search, you divide the data volume by 2, the remaining data after the first execution is n/2, then n/4, then n/8…, all the way down to n/(2^k)=1. Taking the logarithm gives k=log n, meaning you only need to execute a maximum of log n operations, making the time complexity O(log n). The space complexity remains O(1) because you only use three variables (left, right, mid) to track positions, which won't increase memory consumption as the data grows.

Let’s look at sorting examples next. We just witnessed how blazingly fast binary search is, but its prerequisite is that the data must already be sorted. What if the current data is not sorted yet? How do we organize it? And how do we estimate the complexity of these sorting methods? Let’s see how to calculate their complexity (their implementation details will be covered in a future article regarding sorting).

By intuition, we’d likely think of the following two methods:

Bubble Sort: Imagine a row of people of varying heights, and you need to arrange them from shortest to tallest. The dumbest but most intuitive method is this: starting from the left, compare adjacent people in pairs. If the left person is taller than the right, tell them to swap places. Keep comparing all the way to the far right. At this point, the “tallest person” will definitely have been swapped to the rightmost position. Next, ignoring the last person who is already in place, repeat the same action for the remaining people in front. As shown in Figure (1).

• Time Complexity: Because we have to run through n people, and each time perform roughly n pairwise comparisons. So the calculation is (n-1) + (n-2) + (n-3) + … + 1, which according to the arithmetic progression sum formula is (1/2)n²-(1/2)n. Based on the simplification rules earlier, we get O(n²).
• Space Complexity: O(1), because everyone is just swapping places in situ, requiring no extra space.

Insertion Sort: Recall how you organize your hand of cards when playing poker? You pick up the first card, then the second card; if the second is smaller than the first, you insert it in front of the first. When you pick up the third card, you find the correct position to “insert” it among the already sorted cards in your hand. As shown in Figure (2).

• Time Complexity: In the worst-case scenario (e.g., the cards happen to be in reverse order, from largest to smallest), every time you draw a new card, you have to compare it with all the previous cards once, so it remains O(n²).
• Space Complexity: O(1), which can also be done in place.

As you can see, the efficiency of the previous two methods is quite limited. To address this, computer scientists applied the concept used in binary search: cutting in half. This strategy is called Divide and Conquer.

Merge Sort: If sorting 10,000 pieces of data is sluggish, wouldn’t sorting 5,000 pieces be much faster? The logic behind merge sort is: keep “cutting the large data in half” until each small group contains only 1 piece of data (since 1 piece of data is inherently sorted). Then, merge these small groups “in pairs” back into larger sorted groups, combining them all the way back to the original size, as shown in Figure (3).

• Time Complexity: We can visualize the whole process as an inverted tree. Because we split it in half every time, the data volume goes from n -> n/2 -> n/4 all the way down to 1. The total number of levels for this breakdown and merging will be log n levels. In each level, whether preparing to split or merging numbers in pairs, we have to look at all n numbers. Since there are log n levels in total, and each level processes n times, multiplying them yields a time complexity of O(nlog n).
• Space Complexity: Suppose you want to merge [3,8] and [2,9] into [2,3,8,9]. You cannot swap them directly in the array, otherwise you will overwrite numbers that haven't been compared yet (for instance, if you want to swap A and B, you cannot simply write A=B, because when you later write B=A, A has already been overwritten). Therefore, during the merge process, you have to create a temporary array of size n, place the sorted numbers in sequentially, and finally copy them back to the original array. Since the temporary space you create is of size n, the space complexity is O(n).

Having read this far, you should have a solid grasp of calculating time and space complexity. Now let’s review the intuition behind these complexities:

• O(1): This is the most ideal scenario because the complexity doesn’t change even as the data volume surges. Examples include reading a value at a specific array index (like arr[5]) or determining if a number is odd or even. No matter how large the data gets, the required time remains constant.
• O(log n): As the data volume increases, the time will also increase, but nowhere near as fast as the data grows. An example is Binary Search. When the data volume explodes exponentially, the number of operations crawls up slowly like a turtle.
• O(n): As the data increases, the time grows steadily in direct proportion. Examples include using a for loop to traverse an entire array to find a number (Linear Search), or calculating the sum of all numbers in an array.
• O(nlog n): This is usually the limit for “optimal sorting algorithms.” You can picture it like this: you first quickly and efficiently divide a massive pile of data into several small groups (this part is log n), and then process each piece of data (this part is n). While slightly slower than O(n), it remains a very robust and predictable range when dealing with colossal amounts of data. An example is Merge Sort.
• O(n²): This is a rather tragic complexity because the workload skyrockets as the data volume increases. Examples include Bubble Sort, Insertion Sort, or the disastrous code we mentioned at the start that “uses a double loop to check for duplicate orders.”

Of course, linear search, binary search, bubble sort, insertion sort, and merge sort do not encompass all search or sorting algorithms. The goal of this article is to build intuition — so that when you encounter an algorithm, you can estimate its underlying complexity. In practice, there’s a whole basket of these algorithms, which we will introduce separately in upcoming articles dedicated to searching and sorting.

• C Programming — Pointers in C
• C Programming — Linked List
• C Programming — Dynamic Memory Allocation
• C Programming — Double Pointers and Function Pointers
• Welcome to Ac Studio! Read This First

Understanding Time and Space Complexity of Algorithm was originally published in The Coding Handbook on Medium, where people are continuing the conversation by highlighting and responding to this story.

Prerequisites

The prerequisite knowledge required for this article includes: (1). Pointers (2). Dynamic Memory Allocation

In our introductory article on pointers, we covered the most basic concepts. A pointer variable can store the address of another variable, and we can then read the value at that address, as shown below:

int number = 100;   // Declare a normal variable with a value of 100
int *ptr;           // Declare a pointer variable ptr

ptr = &number;      // Store the "address" of number into ptr

// Now ptr stores an address (e.g., 0x101), and *ptr evaluates to 100
printf("Address is: %p\n", ptr);    // Prints the address
printf("Content is: %d\n", *ptr);   // Goes to the address and prints 100

In this article, we are going to take a step further and introduce Double Pointers and Function Pointers.

Double Pointers

We can intuitively imagine that if the first pointer stores the address of a variable, a double pointer likely stores the address of the first pointer. Therefore, a double pointer is also known as a Pointer to Pointer. So, how do we define a double pointer?

We know that a pointer to an integer is int *ptr. The way we define a pointer is by adding a * after the type we want to point to. Therefore, a pointer pointing to an integer pointer can be written as int **ptr.

Dereferencing works the same way. When we write *ptr, we tell the computer to read the content stored at the address ptr. Thus, **ptr represents dereferencing twice. The first dereference reads the value inside the pointer it points to (which is the address of an integer), and the second dereference reads the actual value of that variable, as shown below:

int val = 500;        // Original variable
int *ptr = &val;      // First-level pointer: points to the address of val
int **pptr = &ptr;    // Second-level pointer: points to the address of ptr

printf("Value of val: %d\n", val);
printf("Accessed via *ptr: %d\n", *ptr);
printf("Accessed via **pptr: %d\n", **pptr); // Dereferenced twice: finds ptr first, then val

printf("\nChain reaction of addresses:\n");
printf("Address stored in ptr (address of val): %p\n", ptr);
printf("Address stored in pptr (address of ptr): %p\n", pptr);

Triple Pointers

Similarly, we can define a triple pointer, which is a pointer to a double pointer. If a double pointer is an address of an address, a triple pointer is the address of an address of an address. The logic for definition and dereferencing is exactly the same. int ***ppp means that the variable ppp is used to store the memory address of an int **type variable.

Dereferencing ***ppp follows the preceding logic:

• *ppp goes to the address stored in ppp and finds a double pointer.
• **ppp goes to the double pointer's address and grabs a normal pointer.
• ***ppp grabs the actual variable.

int number = 100;
int *ptr = &number;    // First-level pointer
int **pptr = &ptr;     // Second-level pointer
int ***ppptr = &pptr;  // Third-level pointer

printf("ppptr stores the address of pptr: %p\n", ppptr);
printf("*ppptr gets the content stored in pptr: %p\n", *ppptr);
printf("**ppptr gets the content stored in ptr: %p\n", **ppptr);
printf("***ppptr gets the final value: %d\n", ***ppptr); // Prints 100

This logic can be extended to even more levels of pointers, but in practice, you usually won’t use more than this, otherwise, the code becomes very difficult to maintain.

Test Your Understanding: Use the following questions to see if you have grasped multiple pointers (answers are at the very end).

int a = 10;
int b = 20;
int *p = &a;      // p points to a
int **pp = &p;    // pp points to p
int ***ppp = &pp; // ppp points to pp

1. What will be printed if you print **ppp?
2. If you execute *pp = &b;, what will be the result of calling *p?
3. Following the previous question, if you execute ***ppp = 99;, which variable's value (a or b) will be changed to 99?

Practical Use Cases of Double Pointers

Double pointers might look fancy, but they aren’t just for showing off; they have highly practical applications. A common scenario for using double pointers is handling arrays of strings.

In C, there is no built-in string data type. A string in C is essentially a continuous array of characters, with a \0 appended at the end as a termination marker. Therefore, when we write char* str = "Hello";, the computer actually stores H-e-l-l-o-\0 in a block of memory, and lets the pointer str point to the address of the first letter, 'H'. As long as the program knows where it starts, it can read sequentially down the memory until it hits \0, signaling the end of the string. Thus, "a string" in the eyes of C is simply a "character pointer char *".

Understanding this, if we want to create a “list full of strings” — meaning a collection of multiple char * (e.g., ["Apple", "Banana", "Cherry"])—it is actually an "array of pointers". When this "array containing pointers" is passed as a parameter to a function, it naturally decays into a pointer to a pointer, which is a double pointer char **.

The most classic example is how the main function in C receives external arguments:

// Here, argv is a double pointer
// It points to an array, and every element in that array is a string (char *)
int main(int argc, char **argv) {
    
    printf("You entered a total of %d arguments\n", argc);
    
    for (int i = 0; i < argc; i++) {
        // argv[i] is equivalent to *(argv + i), which fetches the i-th string pointer in the array
        printf("Argument %d: %s\n", i, argv[i]);
    }
    
    return 0;
}

This way of writing the main function is C's standard mechanism for receiving command-line arguments. Simply put, when we run a program in a terminal or command prompt, we don't just start it; we can also pass settings or data to it at launch. To catch this data coming from the outside, we need the argc and argv parameters.

Let’s break this down with a concrete example. Suppose we compile this code into an executable named my_program. We then enter the following command in the terminal to execute it:

./my_program Apple Banana Cherry

At this point, the operating system automatically splits the space-separated text, packages them up, and sends them into the main function:

1. argc (Argument Count): The first parameter of the main function, its goal is to count the total number of arguments. In this example, there are four items: ./my_program, Apple, Banana, and Cherry, so the value of argc will be 4 (the program's own name counts as well).
2. argv: The second parameter, char argv, is the double pointer we just learned about. It's an array filled with pointers pointing to each string.

When you hit Enter, the operating system (like Linux or Windows) steps in and does the following:

• Splits the text string.
• Finds a place in memory to store the strings ./my_program, Apple, Banana, Cherry (each of them is a char *).
• Creates a real array of pointers to hold the addresses of these 4 strings: char *system_array[5] = {"./my_program", "Apple", "Banana", "Cherry", NULL};

Next, the operating system is ready to call your main function and pass this system_array in. However, in C, when you pass an array as a parameter to a function, C does not copy the entire array over (that would waste too much memory). It only passes "the memory address of the first element of this array". This phenomenon is known as Array Decay. That is to say:

• system_array is an array.
• Every element inside the array is a char * (string pointer).
• When it is passed into the main function, C only passes the address of the first element.
• What is the type of the address of a char * variable? It is a pointer pointing to a char *, which is char **.

This is why the original “array of strings” naturally decays into a “double pointer char **argv" the moment it crosses the function boundary.

Function Pointers

Besides pointing to variables, pointers can also point to functions, known as Function Pointers. Just like variables, functions also have their memory addresses.

In C, compiled functions are stored in the code segment of memory. The function name itself is actually a pointer pointing to the starting memory address of that function. A function pointer is a type of variable used to store this memory address, allowing us to dynamically decide which function to call at runtime.

In other words, since the function name itself is a memory location, how do we declare a variable to store the function’s location? When we declare a normal integer pointer, we write: int *ptr;. This tells the compiler: ptr is a pointer, and the content it points to is an int.

But for functions, just knowing it is a function is not enough. The compiler must know:

1. What data type will this function return?
2. What types of parameters does it need to receive?

Therefore, the standard syntax for declaring a function pointer is as follows:

return_type (*pointer_variable_name)(parameter_type1, parameter_type2...);

Note that the parentheses around (*pointer_variable_name) are crucial. For example, if you write: int (*ptr)(int, int); This is a function pointer pointing to a function that returns an int. But if you write: int *ptr(int, int); This means you are declaring a normal function that receives two int parameters and returns an integer pointer int *. The meanings of the two are completely different.

Let’s look at an example to implement a function pointer. Suppose we have a simple addition function:

int add(int a, int b) {
    return a + b;
}

The signature of this function is “receives two ints, and returns an int". Let's declare a function pointer that matches this signature and store the address of add into it:

// 1. Declare the function pointer
int (*func_ptr)(int, int);

// 2. Assign the address of the add function to func_ptr
func_ptr = add;

Once the function is stored in the pointer, we can execute the function through this pointer.

// Call the function via the function pointer, passing in parameters 3 and 5
int result = func_ptr(3, 5); 

printf("The result is: %d\n", result); // Output: The result is: 8

You might feel this is pointless — why not just write add(3,5) directly instead of taking a long detour using a function pointer? Let's look at a more complex example. Suppose we want to design a calculator that can do both addition and subtraction. We can dynamically let the user decide whether to use addition or subtraction at runtime.

#include <stdio.h>

// Define two functions with identical signatures
int add(int a, int b) {
    return a + b;
}

int subtract(int a, int b) {
    return a - b;
}

int main() {
    // Declare a function pointer
    int (*operation)(int, int);
    
    int choice = 1; // Assuming the user inputs 1 (for addition), or 2 for subtraction
    int x = 10, y = 5;

    // "Dynamically" change where the pointer points based on user choice
    if (choice == 1) {
        operation = add;      // Point to addition
    } else {
        operation = subtract; // Point to subtraction
    }

    // We don't need to write if-else blocks here to call the function
    // Just call operation directly, and it will execute the function that was just assigned!
    int result = operation(x, y);
    printf("Calculation result: %d\n", result);

    return 0;
}

Advanced Usage: Callback Functions

Let’s look at a more advanced use of function pointers.

Suppose we have an array of integers, and we want to print out specific numbers from it. Initially, we want to print out all the even numbers, so we write this function:

void print_evens(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 == 0) { // Check if it is an even number
            printf("%d ", arr[i]);
        }
    }
    printf("\n");
}

Then we want to change it to find all numbers greater than 50. This means we have to write another condition for checking if it’s greater than 50, eventually turning our code into a messy pile. However, we can elegantly solve this problem using function pointers.

#include <stdio.h>
#include <stdbool.h>

// This is our "Strategy 1": Check if it's an even number
bool is_even(int num) {
    return num % 2 == 0;
}

// This is our "Strategy 2": Check if it's greater than 50
bool is_greater_than_50(int num) {
    return num > 50;
}

// This function only handles the "framework"; it doesn't know what the specific filtering rule is.
// It requires you to pass in a function pointer (Callback) that "receives an int, returns a bool".
void filter_and_print(int arr[], int size, bool (*condition)(int)) {
    for (int i = 0; i < size; i++) {
        // Here we "call back" the function passed in; it decides whether to print or not
        if (condition(arr[i])) { 
            printf("%d ", arr[i]);
        }
    }
    printf("\n");
}

int main() {
    int my_array[] = {12, 55, 8, 99, 42, 3};
    int size = 6;

    printf("Print even numbers: ");
    filter_and_print(my_array, size, is_even); // Pass in Strategy 1

    printf("Print numbers greater than 50: ");
    filter_and_print(my_array, size, is_greater_than_50); // Pass in Strategy 2

    return 0;
}

This technique is called a Callback Function (Callback).

Next, let’s look at the ultimate boss of Callbacks in C — the built-in quicksort function (qsort). This function is defined in <stdlib.h>, and its signature looks like this:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));

This is a sorting machine. It knows how to sort things at top speed (using the QuickSort algorithm), but it doesn’t know what kind of things you are passing in (because it uses the universal void * pointer, which could be integers, floats, or even strings), and it certainly doesn't know which one is bigger or smaller.

Therefore, it forces you to pass in a fourth parameter: int (*compar)(const void *, const void *). This is a Callback function pointer used to tell qsort the rules for comparing two elements.

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

// This is the Callback function we will pass to qsort
// qsort dictates that the comparison function must return an int and receive two const void * parameters
int compare_ints(const void *a, const void *b) {
    // 1. Because we know what is passed in are integers, we first cast void * back to int *
    int *ptr_a = (int *)a;
    int *ptr_b = (int *)b;
    
    // 2. Extract the values inside
    int val_a = *ptr_a;
    int val_b = *ptr_b;
    
    // 3. Tell qsort which is bigger
    // Rule: if a < b return negative; if a == b return 0; if a > b return positive
    return val_a - val_b; 
}

int main() {
    int data[] = {88, 56, 100, 2, 25};
    int size = 5;

    // Call qsort: pass in the array, the number of items, the size of each element, and our comparison rule (Callback)
    qsort(data, size, sizeof(int), compare_ints);

    // Print the result
    printf("After sorting: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i]);
    }
    printf("\n"); // Output: 2 25 56 88 100

    return 0;
}

Many people become highly proficient at using qsort in their school programming classes, yet fail to realize that function pointers are quietly working behind the scenes.

Answers to the Questions

1. The address of variable a. If changed to ***ppp, it would print 10.
2. *pp is exactly equal to p. Therefore, *pp = &b is equivalent to changing the target that p points to from a to b.
3. Variable b, because the previous sub-question already changed p's arrow to point to b.

• C Programming — Pointers in C
• C Programming — Linked List
• C Programming — Dynamic Memory Allocation
• Understanding Time and Space Complexity of Algorithm
• Welcome to Ac Studio! Read This First

C Programming — Double Pointers and Function Pointers was originally published in The Coding Handbook on Medium, where people are continuing the conversation by highlighting and responding to this story.