Essential Data Structures & Algorithms for Software Engineers

Data structures and algorithms (DSA) are the foundation of efficient software. While frameworks and languages change, these fundamentals remain constant. Understanding them helps you write better code, ace technical interviews, and solve complex problems.

This isn’t about memorising solutions—it’s about understanding patterns that apply across countless real-world scenarios.

Why Data Structures Matter

Choosing the right data structure can mean the difference between an application that scales and one that crawls:

Operation	Array	Linked List	Hash Table	Binary Search Tree
Access by index	O(1)	O(n)	N/A	O(log n)
Search	O(n)	O(n)	O(1) avg	O(log n)
Insert	O(n)	O(1)	O(1) avg	O(log n)
Delete	O(n)	O(1)	O(1) avg	O(log n)

Essential Data Structures

Arrays and Lists

The most fundamental structure—contiguous memory for ordered elements.

When to use:

• Need indexed access
• Know the size upfront (or close to it)
• Iteration is common

// Dynamic array operations
const numbers: number[] = [1, 2, 3, 4, 5];

// O(1) - Access by index
const third = numbers[2];

// O(n) - Search
const index = numbers.indexOf(3);

// O(n) - Insert at position (shifts elements)
numbers.splice(2, 0, 2.5);

Hash Tables (Maps/Dictionaries)

Key-value storage with near-constant time operations.

When to use:

• Need fast lookups by key
• Counting occurrences
• Caching computed values

// Counting word frequencies - O(n)
function countWords(text: string): Map<string, number> {
  const words = text.toLowerCase().split(/\s+/);
  const frequency = new Map<string, number>();
  
  for (const word of words) {
    frequency.set(word, (frequency.get(word) || 0) + 1);
  }
  
  return frequency;
}

Real-world applications:

• Database indexing
• Caching (Redis, Memcached)
• Symbol tables in compilers
• Router path matching

Stacks and Queues

Ordered collections with restricted access patterns.

Stack (LIFO):

// Validating balanced parentheses
function isBalanced(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  
  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (')]}'.includes(char)) {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  
  return stack.length === 0;
}

Queue (FIFO):

// BFS traversal using a queue
function bfs(root: TreeNode): number[] {
  const result: number[] = [];
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.value);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

Real-world applications:

• Undo/redo functionality (stack)
• Browser history (stack)
• Task scheduling (queue)
• Message queues (RabbitMQ, Kafka)

Trees

Hierarchical structures for organised data.

Binary Search Tree:

class BSTNode {
  constructor(
    public value: number,
    public left: BSTNode | null = null,
    public right: BSTNode | null = null
  ) {}
}

function search(root: BSTNode | null, target: number): boolean {
  if (!root) return false;
  if (root.value === target) return true;
  
  return target < root.value
    ? search(root.left, target)
    : search(root.right, target);
}

Real-world applications:

• File systems
• DOM in browsers
• Database indexes (B-trees)
• Routing tables

Graphs

Networks of connected nodes.

// Adjacency list representation
class Graph {
  private adjacencyList = new Map<string, string[]>();
  
  addVertex(vertex: string): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }
  
  addEdge(v1: string, v2: string): void {
    this.adjacencyList.get(v1)?.push(v2);
    this.adjacencyList.get(v2)?.push(v1);
  }
}

Real-world applications:

• Social networks
• Route finding (Google Maps)
• Dependency resolution
• Network topology

Essential Algorithms

Sorting

Understanding sorting helps with many other problems.

Quick Sort — Average O(n log n), in-place:

function quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

Searching

Binary Search — O(log n) for sorted data:

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

Graph Algorithms

Dijkstra’s Algorithm — Shortest path:

function dijkstra(graph: Map<string, [string, number][]>, start: string) {
  const distances = new Map<string, number>();
  const visited = new Set<string>();
  const pq = new PriorityQueue<[string, number]>();
  
  distances.set(start, 0);
  pq.enqueue([start, 0]);
  
  while (!pq.isEmpty()) {
    const [current, dist] = pq.dequeue()!;
    
    if (visited.has(current)) continue;
    visited.add(current);
    
    for (const [neighbor, weight] of graph.get(current) || []) {
      const newDist = dist + weight;
      if (newDist < (distances.get(neighbor) || Infinity)) {
        distances.set(neighbor, newDist);
        pq.enqueue([neighbor, newDist]);
      }
    }
  }
  
  return distances;
}

Dynamic Programming

Breaking problems into overlapping subproblems.

Fibonacci with memoisation:

function fibonacci(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  
  const result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  memo.set(n, result);
  return result;
}

Big O Notation

Understanding time and space complexity:

Notation	Name	Example
O(1)	Constant	Array access
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Recursive Fibonacci

Practical Tips

1. Start with brute force — Get a working solution first
2. Identify patterns — Many problems share common approaches
3. Consider edge cases — Empty inputs, single elements, duplicates
4. Test your solution — Walk through with examples
5. Optimise iteratively — Don’t premature optimise

When to Apply This Knowledge

• Code reviews — Identify inefficient patterns
• System design — Choose appropriate data structures
• Performance debugging — Understand bottlenecks
• Technical interviews — Demonstrate problem-solving ability

Conclusion

Data structures and algorithms aren’t just interview topics—they’re tools that make you a better engineer. You don’t need to memorise every algorithm, but understanding the core patterns will help you:

• Write more efficient code
• Design better systems
• Debug performance issues
• Communicate effectively with other engineers

The investment in learning DSA pays dividends throughout your career.

---

KMS ITC’s engineering team applies these fundamentals in building scalable enterprise solutions. Contact us to learn more about our approach to software engineering.