Static Linked Lists
Instead of using dynamic memory allocation with pointers, we can simulate linked lists using arrays. This approach is often faster and avoids memory overhead. The core idea involves maintaining an array for values and an array for indices (acting as pointers).
For a singly linked list, we maintain a head index and an idx counter represanting the current position for the next new node.
#include <stdio.h>
#define MAX_SIZE 100005
int values[MAX_SIZE];
int next_ptr[MAX_SIZE];
int head_idx;
int curr_pos;
void init_list() {
head_idx = -1;
curr_pos = 0;
}
// Insert at the head of the list
void insert_head(int x) {
values[curr_pos] = x;
next_ptr[curr_pos] = head_idx;
head_idx = curr_pos++;
}
// Insert after node k
void insert_after(int k, int x) {
values[curr_pos] = x;
next_ptr[curr_pos] = next_ptr[k];
next_ptr[k] = curr_pos++;
}
// Remove the node after k
void remove_after(int k) {
next_ptr[k] = next_ptr[next_ptr[k]];
}
int main() {
int ops;
scanf("%d", &ops);
init_list();
while (ops--) {
char op[5];
scanf("%s", op);
if (op[0] == 'H') {
int x;
scanf("%d", &x);
insert_head(x);
} else if (op[0] == 'I') {
int k, x;
scanf("%d%d", &k, &x);
insert_after(k - 1, x);
} else {
int k;
scanf("%d", &k);
if (k == 0) head_idx = next_ptr[head_idx];
else remove_after(k - 1);
}
}
for (int i = head_idx; i != -1; i = next_ptr[i]) {
printf("%d ", values[i]);
}
return 0;
}
Doubly Linked Lists
Doubly linked lists require maintaining both left (previous) and right (next) pointers. In a static array implementation, we typically reserve index 0 for the head sentinel and index 1 for the tail sentinel. The usable indices start from 2.
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100005
int left_ptr[MAX_SIZE];
int right_ptr[MAX_SIZE];
int values[MAX_SIZE];
int curr_pos;
void init_dlist() {
// 0 is head, 1 is tail
right_ptr[0] = 1;
left_ptr[1] = 0;
curr_pos = 2;
}
// Add node to the right of k
void add_right(int k, int x) {
values[curr_pos] = x;
right_ptr[curr_pos] = right_ptr[k];
left_ptr[curr_pos] = k;
left_ptr[right_ptr[k]] = curr_pos;
right_ptr[k] = curr_pos++;
}
// Remove node k
void remove_node(int k) {
right_ptr[left_ptr[k]] = right_ptr[k];
left_ptr[right_ptr[k]] = left_ptr[k];
}
int main() {
int n;
scanf("%d", &n);
init_dlist();
while (n--) {
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "L")) {
scanf("%d", &x);
add_right(0, x);
} else if (!strcmp(op, "R")) {
scanf("%d", &x);
add_right(left_ptr[1], x);
} else if (!strcmp(op, "D")) {
scanf("%d", &k);
remove_node(k + 1);
} else if (!strcmp(op, "IL")) {
scanf("%d%d", &k, &x);
add_right(left_ptr[k + 1], x);
} else {
scanf("%d%d", &k, &x);
add_right(k + 1, x);
}
}
for (int i = right_ptr[0]; i != 1; i = right_ptr[i]) {
printf("%d ", values[i]);
}
return 0;
}
Stacks
Stacks follow the Last-In-First-Out (LIFO) principle. They can be easily implemented using a static array with a pointer to the top element.
Expression Evaluation
Evaluating arithmetic expressions involving +, -, *, /, and parentheses requires two stacks: one for operands and one for operators. We handle operator precedence by evaluating higher or equal precedence operators before pushing a new one.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 100005
int nums[N];
char ops[N];
int num_top, op_top;
void evaluate() {
int b = nums[num_top--];
int a = nums[num_top--];
char c = ops[op_top--];
int res = 0;
if (c == '+') res = a + b;
else if (c == '-') res = a - b;
else if (c == '*') res = a * b;
else res = a / b;
nums[++num_top] = res;
}
int main() {
int priority[128] = {0};
priority['+'] = 1; priority['-'] = 1;
priority['*'] = 2; priority['/'] = 2;
char expr[N];
scanf("%s", expr);
for (int i = 0; expr[i]; i++) {
if (isdigit(expr[i])) {
int x = 0;
while (isdigit(expr[i])) {
x = x * 10 + expr[i++] - '0';
}
i--;
nums[++num_top] = x;
} else if (expr[i] == '(') {
ops[++op_top] = expr[i];
} else if (expr[i] == ')') {
while (ops[op_top] != '(') evaluate();
op_top--;
} else {
while (op_top != 0 && priority[ops[op_top]] >= priority[expr[i]]) {
evaluate();
}
ops[++op_top] = expr[i];
}
}
while (op_top != 0) evaluate();
printf("%d\n", nums[num_top]);
return 0;
}
Monotonic Stack
A monotonic stack maintains elements in a sorted order (increasing or decreasing). Its commonly used to find the nearest smaller or greater element.
#include <stdio.h>
#define N 100005
int stk[N];
int top_ptr;
int main() {
int n;
scanf("%d", &n);
while (n--) {
int x;
scanf("%d", &x);
while (top_ptr && stk[top_ptr] >= x) top_ptr--;
if (!top_ptr) printf("-1 ");
else printf("%d ", stk[top_ptr]);
stk[++top_ptr] = x;
}
return 0;
}
Queues
Queues follow the First-In-First-Out (FIFO) principle. A static array with head and tail pointers is sufficient.
Sliding Window Maximum/Minimum
Using a monotonic queue, we can efficiently find the maximum or minimum value in a sliding window. The queue stores indices, ensuring the values are monotonic.
#include <stdio.h>
#define N 1000005
int q[N], head, tail;
int arr[N];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
head = 0, tail = 0;
// Find Minimum
for (int i = 0; i < n; i++) {
// Remove elements out of window
if (head != tail && q[head] < i - k + 1) head++;
// Maintain monotonic increasing property
while (head != tail && arr[q[tail - 1]] >= arr[i]) tail--;
q[tail++] = i;
if (i >= k - 1) printf("%d ", arr[q[head]]);
}
puts("");
head = 0, tail = 0;
// Find Maximum
for (int i = 0; i < n; i++) {
if (head != tail && q[head] < i - k + 1) head++;
// Maintain monotonic decreasing property
while (head != tail && arr[q[tail - 1]] <= arr[i]) tail--;
q[tail++] = i;
if (i >= k - 1) printf("%d ", arr[q[head]]);
}
puts("");
return 0;
}
KMP Algorithm
The Knuth-Morris-Pratt algorithm optimizes string matching by using a "next" array (or failure function) to avoid unnecessary comparisons. This array stores the length of the longest proper prefix which is also a suffix.
#include <stdio.h>
#define M 1000005
#define N 100005
char text[M];
char pattern[N];
int fail[N];
int main() {
int n, m;
scanf("%d%s%d%s", &n, pattern + 1, &m, text + 1);
// Build failure function
for (int i = 2, j = 0; i <= n; i++) {
while (j && pattern[i] != pattern[j + 1]) j = fail[j];
if (pattern[i] == pattern[j + 1]) j++;
fail[i] = j;
}
// Match
for (int i = 1, j = 0; i <= m; i++) {
while (j && text[i] != pattern[j + 1]) j = fail[j];
if (text[i] == pattern[j + 1]) j++;
if (j == n) {
printf("%d ", i - n);
j = fail[j];
}
}
return 0;
}
Trie (Prefix Tree)
A Trie is used for efficient string storage and retrieval. Each node contains an array of children (usually size 26 for lowercase letters) and a count of occurrences.
#include <stdio.h>
#include <string.h>
#define N 100005
int children[N][26];
int count[N];
int node_cnt;
void insert(char *str) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - 'a';
if (!children[p][u]) children[p][u] = ++node_cnt;
p = children[p][u];
}
count[p]++;
}
int query(char *str) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - 'a';
if (!children[p][u]) return 0;
p = children[p][u];
}
return count[p];
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
char op[2], s[N];
scanf("%s%s", op, s);
if (op[0] == 'I') insert(s);
else printf("%d\n", query(s));
}
return 0;
}
Union-Find (Disjoint Set)
This structure manages a collection of disjoint sets. The key operations are find (determining the root) and merge (uniting two sets). Path compression is used in find to flatten the structure.
#include <stdio.h>
#define N 100005
int parent[N];
int rank[N]; // Optional for union by rank
int find_root(int x) {
if (parent[x] != x) {
parent[x] = find_root(parent[x]); // Path compression
}
return parent[x];
}
void merge_sets(int a, int b) {
int root_a = find_root(a);
int root_b = find_root(b);
if (root_a != root_b) {
parent[root_a] = root_b;
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) parent[i] = i;
while (m--) {
char op[5];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') merge_sets(a, b);
else {
if (find_root(a) == find_root(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
Heaps
A heap is a complete binary tree typically implemented as an array. For a node at index i, children are at 2i and 2i+1. The down operation maintains the heap property.
#include <stdio.h>
#include <string.h>
#define N 100005
int heap[N];
int sz;
void swap(int a, int b) {
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
void down(int u) {
int t = u;
if (u * 2 <= sz && heap[u * 2] < heap[t]) t = u * 2;
if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
if (u != t) {
swap(u, t);
down(t);
}
}
void up(int u) {
while (u / 2 != 0 && heap[u / 2] > heap[u]) {
swap(u / 2, u);
u /= 2;
}
}
int main() {
int n;
scanf("%d", &n);
sz = n;
for (int i = 1; i <= n; i++) scanf("%d", &heap[i]);
// Build heap
for (int i = n / 2; i; i--) down(i);
// Heapsort simulation
while (sz--) {
swap(1, sz + 1);
down(1);
}
for (int i = 1; i <= n; i++) printf("%d ", heap[i]);
return 0;
}
Hash Tables
Open Addressing
In open addressing, if a collision occurs, we probe the next available slot. The table size should be significantly larger (e.g., 2x) than the number of elements.
#include <stdio.h>
#define N 200003
#define NULL_VAL 0x3f3f3f3f
int hash_table[N];
int find_pos(int x) {
int k = (x % N + N) % N;
while (hash_table[k] != NULL_VAL && hash_table[k] != x) {
k++;
if (k == N) k = 0;
}
return k;
}
int main() {
memset(hash_table, 0x3f, sizeof(hash_table));
int n;
scanf("%d", &n);
while (n--) {
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find_pos(x);
if (op[0] == 'I') hash_table[k] = x;
else {
if (hash_table[k] == NULL_VAL) puts("No");
else puts("Yes");
}
}
return 0;
}
Separate Chaining
Separate chaining handles collisions by maintaining a linked list at every hash bucket.
#include <stdio.h>
#include <stdlib.h>
#define N 100003
int head[N];
int val[N], nxt[N];
int idx;
void init_hash() {
idx = 0;
memset(head, -1, sizeof(head));
}
void insert(int x) {
int k = (x % N + N) % N;
val[idx] = x;
nxt[idx] = head[k];
head[k] = idx++;
}
bool find(int x) {
int k = (x % N + N) % N;
for (int i = head[k]; i != -1; i = nxt[i]) {
if (val[i] == x) return true;
}
return false;
}
int main() {
init_hash();
int n;
scanf("%d", &n);
while (n--) {
char op[2];
int x;
scanf("%s%d", op, &x);
if (op[0] == 'I') insert(x);
else {
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
String Hashing
String hashing converts a string into a numeric value to allow efficient substring comparison. We use a base (e.g., 131) and treat the string as a base-B number. Using unsigned long long allows natural overflow modulo 2^64.
#include <stdio.h>
#include <string.h>
typedef unsigned long long ULL;
#define N 100005
int base = 131;
ULL pow_arr[N];
ULL hash_arr[N];
char str[N];
ULL get_hash(int l, int r) {
return hash_arr[r] - hash_arr[l - 1] * pow_arr[r - l + 1];
}
int main() {
int n, m;
scanf("%d%d%s", &n, &m, str + 1);
pow_arr[0] = 1;
for (int i = 1; i <= n; i++) {
pow_arr[i] = pow_arr[i - 1] * base;
hash_arr[i] = hash_arr[i - 1] * base + (str[i] - 'a' + 1);
}
while (m--) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (get_hash(l1, r1) == get_hash(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}