Data Structures & Algorithms Cheat Sheet
EE3491 - Programming Techniques | Chapter 4
1. Common Data Structures
Array
Fixed Array: Size known at compile time, stored in stack/data segment
Dynamic Array: Allocated at runtime using malloc()/new[], stored in heap
Extendable Array: Grows dynamically, typically doubles in size (K=2)
List Structures
Linked List: Sequential access, flexible insertion/deletion, overhead per element
Double Linked List: Bidirectional traversal, efficient delete operations
Queue (FIFO): First-In-First-Out, enqueue at rear, dequeue at front
Stack (LIFO): Last-In-First-Out, push/pop from same end
Circular Buffer: Fixed-size ring buffer, overwrites oldest when full
Advanced Structures
Binary Tree: Each node has max 2 children
Hash Table: Fast lookup using hash function
Set: Collection of distinct elements
Map: Key-value pairs with sorted access
2. Memory Management
Memory Segments
Segmen Purpose Managed
t By
Code Constants, read-only Compiler
(Text)
Data Global/static variables Compiler
Stack Local variables, function calls Compiler
(FILO)
Heap Dynamic allocation Developer
Dynamic Memory in C:
// Allocation
//Memory allocation:
int *p = (int*)malloc(n * sizeof(int));
//Memory allocate but with zero initial values:
int *p = calloc(n, sizeof(int));
//Reallocate pre-existing memory:
p = realloc(p, new_size * sizeof(int));
// Deallocation
free(p);
p = NULL; // ALWAYS DO THIS TO PREVENT REAL-TIME ERRORS!
Best Practices
Each malloc()/new should have corresponding free()/delete
Initialize pointers to NULL
Set pointers to NULL after freeing
Always check if allocation succeeded (returns NULL on failure)
Use stack when possible (faster than heap)
MALLOC()
The “malloc” or “memory allocation” method in C is used to dynamically allocate a
single large block of memory with the specified size. It returns a pointer of type void
which can be cast into a pointer of any form. It is defined inside <stdlib.h> header file.
Dynamic memory allocation depends on the developer, not the compiler, SO BE
CAREFUL AS IT CAN CAUSE REAL-TIME ERROR!
Syntax:
The cast-type makes sure the malloc returns the proper memory for that type of
variable, in this case it is int.
Always remember to use the free() function to release the memory segment allocated
by malloc()
FOR MORE DETAILS, CHECK OUT ASSIGNMENT_3_3
CALLOC()
calloc() is similar to malloc() but the memory is initialized with zero value (clear
allocate). It is used when you need memory with default zero values.
void *calloc(size_t n, size_t size)
Syntax:
Example:
int main() {
int *ptr = (int *)calloc(5, sizeof(int));
for (int i = 0; i < 5; i++)
printf("%d ", ptr[i]);
return 0;}
Output: 0 0 0 0 0
REALLOC()
“realloc()” or “re allocation” is used to change the memory allocated by malloc(),
calloc(), or realloc().
void *realloc(void *p, size_t size)
With *p is the memory you want to change.
realloc()is used to increase or decrease dynamic memory:
If it increases, the existing elements are unchanged and the newly added
elements have no initial values
If it decreases, the existing elements are the unchanged
However, if the memory space is not sufficient, realloc() will allocate new
memory block and copy the whole old memory block to the new one, then
delete the old one
FOR MORE DETAILS, CHECK OUT ASSIGNMENT_3_3
EXAMPLE OF WRONG USAGE:
COMMON ERRORS:
The pointer points to an undefined value
o “memory corruption”
The pointer points to NULL
o Program halts
Free a pointer pointing to a memory block which is not dynamic memory like stack,
constant data
Not free memory after using (memory leak).
Access elements which are not in the range of the allocated array
3. Sorting Algorithms
Selection Sort
Complexity: O(n²)
Method: Find minimum in unsorted part, swap with first unsorted element
Use: Simple but slow for large arrays
int min_loc(int a[], int k, int n) {
int pos = k;
for (int j = k+1; j < n; j++)
if (a[j] < a[pos]) pos = j;
return pos;
void sel_sort(int a[], int n) {
for (int k = 0; k < n-1; k++) {
int m = min_loc(a, k, n);
swap(&a[k], &a[m]);
Insertion Sort
Complexity: O(n²) average, O(n) best case
Method: Insert each element into sorted portion
Use: Good for nearly sorted data
Merge Sort
Complexity: O(n log n)
Method: Divide array, recursively sort halves, merge sorted halves
Space: Requires additional memory
Steps: log₂n merge operations, each taking O(n)
Quick Sort
Complexity: O(n log n) average, O(n²) worst case
Method: Choose pivot, partition around pivot, recursively sort partitions
Optimization: Use median-of-three for pivot selection
Best Case: Pivot splits array evenly (log₂n depth)
Worst Case: Already sorted array with poor pivot choice
Comparison
Algorit Best Averag Worst Spac
hm e e
Selectio O(n²) O(n²) O(n²) O(1)
n
Insertion O(n) O(n²) O(n²) O(1)
Merge O(n log O(n log O(n log O(n)
n) n) n)
Quick O(n log O(n log O(n²) O(log
n) n) n)
4. Searching Algorithms
Linear Search
Complexity: O(n)
Method: Check each element sequentially
Use: Unsorted data
int linearSearch(int arr[], int N, int x) {
for (int i = 0; i < N; i++)
if (arr[i] == x) return i;
return -1;
Binary Search
Complexity: O(log n)
Requirement: Array must be sorted
Method: Repeatedly divide search space in half
int binarySearch(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
Comparison: For 1 million elements, linear search needs ~1,000,000 operations vs
binary search needs ~20
5. Key Structures & Implementations
Vector Structure Example
struct Vector {
double *data;
int nelem;
};
Vector createVector(int n, double init);
void destroyVector(Vector v);
double getElem(Vector v, int i);
void putElem(Vector v, int i, double d);
Linked List Example
struct MessageItem {
string subject;
string content;
MessageItem* pNext;
};
struct MessageList {
MessageItem* pHead;
};
Stack Example
typedef struct Stack {
double buffer[MAXSIZE];
int count;
} Stack;
void push(Stack *s, double item) {
s->buffer[s->count++] = item;
double pop(Stack *s) {
return s->buffer[--s->count];
6. Important Concepts
typedef Usage
typedef struct Point {
int x, y;
} Point;
Point pt1, pt2; // cleaner than: struct Point pt1, pt2;
Common Errors to Avoid
❌ Memory corruption (uninitialized pointers)
❌ Null pointer access
❌ Memory leaks (not freeing allocated memory)
❌ Freeing non-dynamic memory
❌ Double-freeing memory
❌ Array index out of bounds
Efficiency Tips
Choose right algorithm for problem size
Use stack over heap when possible
Select appropriate data structure
Consider time vs space trade-offs
7. Quick Reference
When to Use What
Use Array: Known size, fast random access needed Use Linked List: Frequent
insertions/deletions, unknown size Use Stack: LIFO operations (undo, recursion,
expression evaluation) Use Queue: FIFO operations (task scheduling, breadth-first
search) Use Hash Table: Fast lookup by key Use Binary Search: Searching in sorted
data
Complexity Goals
O(1): Constant - ideal
O(log n): Logarithmic - very good
O(n): Linear - acceptable
O(n log n): Good for sorting
O(n²): Quadratic - avoid for large n
O(2ⁿ): Exponential - impractical for large n
Remember: The best data structure and algorithm depend on your specific use case!