Dev Training: Common Data Structures

Most developers can get by without thinking too much about data structures, just using the basics given in their language. But knowing how they work can be the difference between writing functional code and writing truly efficient, scalable solutions. Data structures shape the way we store, retrieve, and manipulate data, and they are a key part of technical interviews, particularly at companies like Google and Meta.

A good grasp of data structures helps in designing better software, optimising performance, and reducing memory overhead. Whether you’re preparing for interviews or just looking to improve your problem-solving skills, a strong understanding of these structures will help.

Arrays

Arrays store elements in a fixed-size sequential block of memory, allowing constant-time access (O(1)) to any element using an index. However, resising an array requires allocating new memory and copying elements, making insertions and deletions costly.

Think of an array as a row of numbered lockers. You can open any locker instantly if you know the number, but adding a new one means shifting everything over.

# Array (List in Python)
numbers = [10, 20, 30, 40]
print(numbers[2])  # O(1) access

Linked Lists

A linked list consists of nodes, where each node stores a value and a pointer to the next node. Unlike arrays, linked lists do not require a fixed size and allow fast insertions and deletions, but accessing elements is slower as you must traverse the list from the start.

A linked list is like a scavenger hunt where each clue tells you where to find the next one. You can insert a new clue anywhere, but you always have to start at the beginning to find something.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        if not self.head:
            self.head = Node(value)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(value)

Stacks

A stack follows the Last-In-First-Out (LIFO) principle, where the most recently added item is removed first. It is used for managing function calls, undo operations, and backtracking algorithms.

A stack is like a stack of plates. You always take the top plate first before reaching the ones below.

stack = []
stack.append(1)
stack.append(2)
stack.pop()  # Removes 2 (LIFO)

Queues

A queue follows the First-In-First-Out (FIFO) principle, where elements are removed in the order they were added. It is useful for task scheduling, handling requests, and breadth-first search.

A queue is like a line at a supermarket checkout. The first person in line gets served first.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()  # Removes 1 (FIFO)

Hash Tables

A hash table maps keys to values using a hash function, allowing average O(1) time complexity for lookups, inserts, and deletions. It is widely used in databases, caching, and key-value stores.

A hash table is like a dictionary where each word is mapped to a definition, making lookups very fast.

user_ages = {"Alice": 25, "Bob": 30}
print(user_ages["Alice"])  # O(1) lookup

Trees

A tree is a way of structuring data that branches out like an upside-down tree, with each element (called a node) linking to child nodes below it. Trees help in organising data efficiently, making searches faster compared to lists or arrays. A binary search tree (BST) is a type of tree where each node has at most two children, and values are arranged so that searching for an item takes fewer steps as the dataset grows. Some trees, like AVL trees, balance themselves automatically to maintain efficiency.

Think of a tree like a family tree, where each person (node) has parents and children, and finding a relative involves navigating the branches.

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

def insert(root, value):
    if not root:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

Graphs

Graphs consist of nodes connected by edges and are used to represent networks, social relationships, and route optimisation problems.

A graph is like a city map where locations are nodes and roads are edges, allowing for complex route-finding algorithms.

class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

Heaps

A heap is a priority queue, where the highest (or lowest) priority element is always retrieved first. Imagine a hospital emergency room where patients are treated based on urgency rather than arrival time.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
print(heapq.heappop(heap))  # Removes 1

Mastering these common data structures is crucial for writing efficient, optimised code. Whether preparing for coding interviews or working on real-world applications, understanding when to use each structure can save time, reduce complexity, and improve overall system performance.

Further Reading