Learn Data Structures Deep Dive: Implementation and Interview Patterns

Data Structures Deep Dive: Implementation and Interview Patterns

DodaTech Updated Jun 20, 2026 9 min read

Data structures are the foundation of efficient algorithms — choosing the right structure can turn an O(n²) solution into O(n log n) or O(1), and understanding their internals is essential for coding interview success.

What You’ll Learn

Array and string manipulation patterns
Linked list: singly, doubly, and circular implementations
Stack and queue: use cases and implementations
Hash table: collision resolution, load factor, and runtime analysis
Trees: binary trees, BSTs, tries, and tree traversals
Graphs: adjacency list vs matrix, BFS, DFS, topological sort
Heaps: min-heap, max-heap, priority queue implementation

Why Data Structures Matter

Data structures are the most commonly tested topic in coding interviews. According to LeetCode data, 80% of interview problems involve at least one data structure from this guide. Understanding how they work internally — not just how to use them — lets you recognize which structure fits a problem, analyze time and space complexity accurately, and implement custom structures when built-in ones don’t exist.

Durga Antivirus Pro uses trie data structures for signature matching — identifying malware patterns in constant time requires the right data structure for the job.

Learning Path

    flowchart LR
  A[Coding Interview Prep] --> B[Data Structures Deep<br/>You are here]
  B --> C[Algorithms Deep]
  C --> D[System Design]
  D --> E[Mock Interviews]
  style B fill:#f90,color:#fff

Arrays

Key Operations

Operation	Time Complexity	Notes
Access	O(1)	By index
Search	O(n)	Unsorted; O(log n) if sorted
Insert (end)	O(1) amortized	May trigger resize
Insert (middle)	O(n)	Shift elements
Delete	O(n)	Shift elements

Common Patterns

# Two-pointer technique
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# Sliding window
def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Prefix sum
def subarray_sum(nums: list[int], target: int) -> bool:
    prefix_sum = 0
    seen = {0}
    for num in nums:
        prefix_sum += num
        if prefix_sum - target in seen:
            return True
        seen.add(prefix_sum)
    return False

Linked Lists

Singly Linked List Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

    def append(self, val):
        if not self.head:
            self.head = ListNode(val)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = ListNode(val)

    def reverse(self):
        prev, current = None, self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    def has_cycle(self) -> bool:
        slow = fast = self.head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Key Operations

Operation	Time	Notes
Access	O(n)	Must traverse
Search	O(n)	Linear scan
Insert (head)	O(1)	Update head pointer
Insert (tail)	O(n)	O(1) with tail pointer
Delete	O(n)	Find previous node

Stacks and Queues

Stack (LIFO)

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

# Use case: balanced parentheses
def is_valid_brackets(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    return not stack

Queue (FIFO)

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.popleft()

    def peek(self):
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

Hash Tables

Implementation

class HashTable:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

    def remove(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return
        raise KeyError(key)

Collision Resolution

Chaining: Each bucket holds a linked list (shown above)
Open addressing: Find next empty slot (linear probing, quadratic probing, double hashing)

Trees

Binary Tree Traversals

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

# In-order (DFS): left → root → right
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Pre-order: root → left → right
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Post-order: left → right → root
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Level-order (BFS)
from collections import deque
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Binary Search Tree

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        current = self.root
        while True:
            if val < current.val:
                if current.left:
                    current = current.left
                else:
                    current.left = TreeNode(val)
                    break
            else:
                if current.right:
                    current = current.right
                else:
                    current.right = TreeNode(val)
                    break

    def search(self, val) -> bool:
        current = self.root
        while current:
            if val == current.val:
                return True
            current = current.left if val < current.val else current.right
        return False

    def is_valid_bst(self, root, min_val=float('-inf'), max_val=float('inf')) -> bool:
        if not root:
            return True
        if not (min_val < root.val < max_val):
            return False
        return (self.is_valid_bst(root.left, min_val, root.val) and
                self.is_valid_bst(root.right, root.val, max_val))

Graphs

Adjacency List

class Graph:
    def __init__(self):
        self.adjacency = {}

    def add_edge(self, u, v):
        if u not in self.adjacency:
            self.adjacency[u] = []
        if v not in self.adjacency:
            self.adjacency[v] = []
        self.adjacency[u].append(v)

    def bfs(self, start):
        visited = {start}
        queue = deque([start])
        result = []
        while queue:
            node = queue.popleft()
            result.append(node)
            for neighbor in self.adjacency.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return result

    def dfs(self, start):
        visited = set()
        result = []

        def _dfs(node):
            visited.add(node)
            result.append(node)
            for neighbor in self.adjacency.get(node, []):
                if neighbor not in visited:
                    _dfs(neighbor)

        _dfs(start)
        return result

    def has_cycle(self) -> bool:
        visiting = set()
        visited = set()

        def _dfs(node):
            visiting.add(node)
            for neighbor in self.adjacency.get(node, []):
                if neighbor in visiting:
                    return True
                if neighbor not in visited:
                    if _dfs(neighbor):
                        return True
            visiting.remove(node)
            visited.add(node)
            return False

        for node in self.adjacency:
            if node not in visited:
                if _dfs(node):
                    return True
        return False

Heaps

Min-Heap Implementation

class MinHeap:
    def __init__(self):
        self.heap = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i): return 2 * i + 1
    def _right(self, i): return 2 * i + 2

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _heapify_up(self, i):
        parent = self._parent(i)
        if i > 0 and self.heap[i] < self.heap[parent]:
            self._swap(i, parent)
            self._heapify_up(parent)

    def _heapify_down(self, i):
        smallest = i
        left = self._left(i)
        right = self._right(i)
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != i:
            self._swap(i, smallest)
            self._heapify_down(smallest)

    def push(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        self._swap(0, len(self.heap) - 1)
        val = self.heap.pop()
        self._heapify_down(0)
        return val

    def peek(self):
        return self.heap[0] if self.heap else None

Common Data Structure Mistakes

1. Choosing the Wrong Structure

Using an array when you need frequent inserts/deletes, or a list when you need O(1) access.

Fix: Match the data structure to the operations you need most.

2. Forgetting About Resizing

Assuming hash table and dynamic array operations are always O(1). Resizing makes insertions O(n) occasionally.

Fix: Amortized analysis accounts for this — most operations are O(1), some trigger resizing.

3. Not Handling Edge Cases

Empty data structures, single elements, duplicates — always test these.

Fix: Write tests for: empty, single element, two elements, many elements, duplicates.

4. Confusing Tree Traversals

In-order gives sorted order for BSTs. Pre-order is useful for copying. Post-order is useful for deletion.

Fix: Draw the tree and trace each traversal manually.

5. Recursion Depth

Recursive tree traversals can overflow the stack for deep trees.

Fix: Use iterative approaches (explicit stack) for production code.

6. Graph Cycle Detection

Forgetting to track visiting vs visited nodes leads to infinite loops.

Fix: Use two sets: currently visiting (gray) and fully visited (black).

7. Heap Property Violation

After pushing or popping, the heap must maintain the heap property.

Fix: Always heapify up after push and heapify down after pop.

Practice Questions

1. What is the time complexity of array access, search, insert, and delete?

Access O(1), search O(n), insert O(n), delete O(n). Search is O(log n) if sorted (binary search).

2. How does a hash table handle collisions?

Chaining (linked list per bucket) or open addressing (find next empty slot via probing).

3. What is the difference between BFS and DFS?

BFS explores level by level (uses queue) — finds shortest path in unweighted graphs. DFS explores depth first (uses stack/recursion) — uses less memory for deep graphs.

4. When would you use a heap instead of a sorted array?

When you need to repeatedly insert and extract the min/max. Heap insert is O(log n) vs O(n) for sorted array insert.

5. What is a trie and when would you use it?

A tree-like structure for storing strings where each node represents a character. Used for autocomplete, spell checking, and prefix matching. Lookup is O(k) where k is string length.

Challenge: Implement a Least Recently Used (LRU) cache using a hash map and doubly linked list. The cache should support get and put operations in O(1) time.

FAQ

Which data structure appears most in interviews?

Arrays and hash tables appear in almost every interview. Trees and graphs appear in most medium/hard problems.

Should I implement data structures from scratch in interviews?

Only if asked. Most interviews let you use built-in data structures. But understanding implementation helps with complexity analysis.

What is the most important graph algorithm?

BFS and DFS are the foundation. Know both iterative and recursive implementations.

How deep should I know data structures for senior roles?

Senior roles add distributed data structures (consistent hashing, bloom filters, Merkle trees) and tradeoff analysis between structures.

What is the best resource for practicing data structures?

LeetCode categorized by data structure. Start with easy problems for each structure, then medium, then hard.

What’s Next

Tutorial	What You’ll Learn
Algorithms Deep Dive	Sorting, searching, DP, and graph algorithms
System Design Interview Prep	Applying data structures in system design
Coding Interview Prep	Problem-solving framework and strategies

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-20.

Previous Backend Interview Guide: API Design, Databases, Scalability, and Microservices Next Algorithms Deep Dive: Sorting, Searching, Dynamic Programming, and Graph Patterns

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Interview Prep