Data Structures That Actually Work - Arrays, Lists, Trees, and Why They Matter

|

Understanding Data Structures - What Actually Matters

Introduction: Why I Finally Cared About This

Honestly? I spent my first year coding without really understanding data structures. My projects worked fine, so I didn't think much about it. Then I built an app that crashed when we hit 10k users. The same code that handled 100 users made queries timeout at scale.

I realized later: the problem wasn't the code. It was how I was storing the data.

Once you really understand when to use an array vs linked list vs tree, something clicks. Your code gets faster. Your memory usage drops. Suddenly apps that felt sluggish start flying. You go from writing code that works to code that actually scales.

This guide covers the data structures you'll actually use. Not theoretical stuff—practical implementations, why they matter, and when to use each one.

1. Arrays - The Foundation Data Structure

What Are Arrays?

An array is a contiguous block of memory containing elements of the same data type. It's the most fundamental data structure and the basis for understanding more complex structures.

Key Characteristics:

  • Fixed Size - Size defined at declaration (in most languages)
  • Contiguous Memory - All elements stored sequentially
  • Fast Access - O(1) access time using index
  • Slow Insertion/Deletion - O(n) time for middle elements
  • Type Homogeneity - All elements must be same type

Array Operations and Complexity

Operation          Time Complexity    Space Complexity
Access by index    O(1)              O(1)
Search            O(n)              O(1)
Insertion         O(n)              O(1)
Deletion          O(n)              O(1)

Real-World Array Applications

1. Image Processing

Pixel array: 2D array where each element = color value
Performance-critical: Millions of pixels processed per frame

2. Caching Mechanisms

CPU Cache uses fixed-size arrays for fast data retrieval
Memory layout: contiguous for cache line efficiency

3. Database Indexing

B+ tree nodes use arrays for sorted key storage
Binary search requires contiguous array structure

Practical Implementation Example

public class DynamicArray<T> {
    private T[] elements;
    private int size;
    private static final int INITIAL_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public DynamicArray() {
        elements = new Object[INITIAL_CAPACITY];
        size = 0;
    }
    
    public void add(T element) {
        if (size == elements.length) {
            resize(elements.length * 2);
        }
        elements[size++] = element;
    }
    
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return elements[index];
    }
    
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        size--;
    }
    
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        T[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }
}

2. Linked Lists - Dynamic Data Structures

Understanding Linked Lists

A linked list is a linear data structure where elements (nodes) are dynamically allocated. Each node contains:

  • Data - The actual value
  • Pointer(s) - Reference to next node (and previous in doubly-linked)

Advantages Over Arrays:

  • ✓ Dynamic sizing - grow/shrink as needed
  • ✓ Efficient insertion/deletion - O(1) if position known
  • ✓ No pre-allocation needed

Disadvantages:

  • ✗ No random access - must traverse from head
  • ✗ Extra memory - pointers overhead
  • ✗ Cache unfriendly - nodes scattered in memory

Linked List Variants and Use Cases

1. Singly Linked List

Node → Node → Node → null
Used: Implement stacks, simple queues

2. Doubly Linked List

null ← Node ↔ Node ↔ Node → null
Used: LRU Cache, navigation (forward/backward)

3. Circular Linked List

Node → Node → Node ↻ (points back to first)
Used: Round-robin scheduling, music playlists

Complete Implementation

public class SinglyLinkedList<T> {
    private Node<T> head;
    private int size;
    
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }
    
    // Insert at beginning - O(1)
    public void insertFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // Insert at position - O(n)
    public void insertAt(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            insertFirst(data);
            return;
        }
        Node<T> current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        Node<T> newNode = new Node<>(data);
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }
    
    // Delete at position - O(n)
    public T deleteAt(int index) {
        if (index < 0 || index >= size || head == null) {
            throw new IndexOutOfBoundsException();
        }
        T data;
        if (index == 0) {
            data = head.data;
            head = head.next;
        } else {
            Node<T> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            data = current.next.data;
            current.next = current.next.next;
        }
        size--;
        return data;
    }
    
    // Search - O(n)
    public boolean contains(T data) {
        Node<T> current = head;
        while (current != null) {
            if (current.data.equals(data)) return true;
            current = current.next;
        }
        return false;
    }
    
    public int getSize() { return size; }
}

3. Stacks - LIFO Data Structure

Stack Operations

Push (add to top)    - O(1)
Pop (remove top)     - O(1)
Peek (view top)      - O(1)
Search               - O(n)

Real-World Stack Applications

1. Browser Back Button

Press page A → Push A to stack
Press page B → Push B to stack
Click back → Pop B from stack, show A

2. Function Call Stack

main() calls func1()  → Push func1
func1 calls func2()   → Push func2
func2 returns         → Pop func2

3. Expression Evaluation

Infix: 3 + 4 * 2
Convert to postfix: 3 4 2 * +
Evaluate using stack: [3, 4, 2] → multiply 4*2 → add 3+8 = 11

Stack Implementation

public class Stack<T> {
    private Node<T> top;
    private int size;
    
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }
    
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    public T pop() {
        if (isEmpty()) throw new EmptyStackException();
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) throw new EmptyStackException();
        return top.data;
    }
    
    public boolean isEmpty() { return size == 0; }
    public int getSize() { return size; }
}

4. Queues - FIFO Data Structure

Queue Operations

Enqueue (add to rear)    - O(1)
Dequeue (remove front)   - O(1)
Peek (view front)        - O(1)

Queue Variants

1. Simple Queue (FIFO)

[Front] ← 1, 2, 3 ← [Rear]
Operations: dequeue 1, enqueue 4 → [2, 3, 4]

2. Circular Queue

Wraps around when rear reaches end
More efficient space usage in fixed-size queue

3. Priority Queue

Elements retrieved based on priority, not arrival order
Used in: OS scheduling, Dijkstra's algorithm, Huffman coding

4. Deque (Double-Ended Queue)

Add/remove from both front and rear
Insert at front: prepend operation
Insert at rear: append operation

Real-World Queue Applications

1. CPU Scheduling

Process arrives → Added to ready queue
CPU selects → Processes in FIFO order
Process completes → Removed from queue

2. Printer Queue

Document 1 submitted → Queue it
Document 2 submitted → Queue it
Printer processes → FIFO order

3. Message Processing

Message arrives → Enqueue
Worker processes → Dequeue oldest message
Handles backpressure → Queue grows if workers slow

Queue Implementation

public class Queue<T> {
    private Node<T> front, rear;
    private int size;
    
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }
    
    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) throw new NoSuchElementException();
        T data = front.data;
        front = front.next;
        if (isEmpty()) rear = null;
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) throw new NoSuchElementException();
        return front.data;
    }
    
    public boolean isEmpty() { return size == 0; }
    public int getSize() { return size; }
}

5. Trees - Hierarchical Data Structures

Binary Trees

A binary tree has at most 2 children per node.

       A
      / \
     B   C
    / \
   D   E

Types:

  • Full Binary Tree - Every node has 0 or 2 children
  • Complete Binary Tree - All levels filled except possibly last
  • Perfect Binary Tree - All internal nodes have 2 children, all leaves same depth
  • Balanced Tree - Height difference ≤ 1

Binary Search Tree (BST)

public class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;
    
    private static class Node<T> {
        T data;
        Node<T> left, right;
        Node(T data) { this.data = data; }
    }
    
    // Insert - O(log n) average, O(n) worst
    public void insert(T data) {
        root = insertRecursive(root, data);
    }
    
    private Node<T> insertRecursive(Node<T> node, T data) {
        if (node == null) return new Node<>(data);
        
        int cmp = data.compareTo(node.data);
        if (cmp < 0) {
            node.left = insertRecursive(node.left, data);
        } else if (cmp > 0) {
            node.right = insertRecursive(node.right, data);
        }
        return node;
    }
    
    // Search - O(log n) average, O(n) worst
    public boolean search(T data) {
        return searchRecursive(root, data);
    }
    
    private boolean searchRecursive(Node<T> node, T data) {
        if (node == null) return false;
        
        int cmp = data.compareTo(node.data);
        if (cmp < 0) {
            return searchRecursive(node.left, data);
        } else if (cmp > 0) {
            return searchRecursive(node.right, data);
        }
        return true;
    }
    
    // In-order traversal: Left → Root → Right (sorted order)
    public void inOrder() {
        inOrderRecursive(root);
    }
    
    private void inOrderRecursive(Node<T> node) {
        if (node == null) return;
        inOrderRecursive(node.left);
        System.out.print(node.data + " ");
        inOrderRecursive(node.right);
    }
}

AVL Trees - Self-Balancing BSTs

AVL trees maintain balance factor and rebalance on insertion/deletion to guarantee O(log n) operations.

Balance Factor = Height(left) - Height(right)
Valid range: -1, 0, 1

If violated: Perform rotations (LL, RR, LR, RL)

Red-Black Trees

Rules:

  1. Every node is red or black
  2. Root is black
  3. Leaves (null) are black
  4. Red nodes have black children
  5. All paths from node to leaf have same black node count

Used in: Linux kernel schedulers, Java's TreeMap, C++ STL map

6. Hash Tables - Fast Lookup

How Hash Tables Work

1. Key → Hash Function → Index
2. Store value at index in array
3. Collision handling (chaining or probing)

Collision Resolution Strategies

1. Chaining (Separate Chaining)

Hash table: [Linked List | Linked List | Linked List | ...]
Collision: Add to chain
Pros: Easy implementation
Cons: Extra memory for pointers

2. Open Addressing

Linear Probing: Find next empty slot
Quadratic Probing: Skip increasingly
Double Hashing: Use second hash function

Pros: Better cache locality
Cons: Clustering, deletion issues

Hash Table Implementation

public class HashTable<K, V> {
    private static final int INITIAL_CAPACITY = 16;
    private Entry<K, V>[] table;
    private int size;
    private float loadFactor = 0.75f;
    
    @SuppressWarnings("unchecked")
    public HashTable() {
        table = new Entry[INITIAL_CAPACITY];
        size = 0;
    }
    
    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public void put(K key, V value) {
        if (size >= table.length * loadFactor) {
            resize();
        }
        
        int index = hash(key);
        Entry<K, V> entry = table[index];
        
        // Check if key exists (update)
        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }
        
        // Insert new entry at beginning of chain
        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
    }
    
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];
        
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }
    
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }
    
    @SuppressWarnings("unchecked")
    private void resize() {
        Entry<K, V>[] oldTable = table;
        table = new Entry[oldTable.length * 2];
        size = 0;
        
        for (Entry<K, V> entry : oldTable) {
            while (entry != null) {
                put(entry.key, entry.value);
                entry = entry.next;
            }
        }
    }
}

7. Graphs - Network Representations

Graph Basics

Components:

  • Vertices (nodes)
  • Edges (connections)

Types:

  • Directed - Edges have direction
  • Undirected - Edges bidirectional
  • Weighted - Edges have weights
  • Cyclic - Contains cycles
  • Acyclic - No cycles (DAG)

Graph Representations

1. Adjacency Matrix

O(1) edge lookup but O(V²) space
Good for: Dense graphs, small graphs

2. Adjacency List

O(V+E) space, O(degree) edge lookup
Good for: Sparse graphs, large graphs

Graph Traversal Algorithms

Depth-First Search (DFS) - O(V+E)

public void dfs(Vertex start) {
    Set<Vertex> visited = new HashSet<>();
    Stack<Vertex> stack = new Stack<>();
    stack.push(start);
    
    while (!stack.isEmpty()) {
        Vertex current = stack.pop();
        if (!visited.contains(current)) {
            visited.add(current);
            System.out.print(current + " ");
            
            for (Vertex neighbor : current.neighbors) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

Breadth-First Search (BFS) - O(V+E)

public void bfs(Vertex start) {
    Set<Vertex> visited = new HashSet<>();
    Queue<Vertex> queue = new Queue<>();
    queue.enqueue(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        Vertex current = queue.dequeue();
        System.out.print(current + " ");
        
        for (Vertex neighbor : current.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.enqueue(neighbor);
            }
        }
    }
}

Famous Graph Algorithms

1. Dijkstra's Algorithm - Shortest path O(E log V) 2. Bellman-Ford - Shortest path (handles negative weights) O(VE) 3. Floyd-Warshall - All pairs shortest paths O(V³) 4. Topological Sort - DAG ordering O(V+E) 5. Strongly Connected Components - Find SCCs O(V+E)

Key Takeaways for Interviews

  1. Understand Trade-offs - Every structure trades speed for space
  2. Complexity Analysis - Know average vs worst case
  3. Implementation - Can you code it from scratch?
  4. Real-World Use - When/why to use each structure
  5. Optimization - Can you improve space/time?

Study Strategy:

  • Implement each structure completely
  • Solve 50+ problems using them
  • Understand when to use which
  • Practice coding without references