Basic Data Structures

TL;DR

Arrays provide O(1) random access but O(n) insertion/deletion. Linked lists enable O(1) insertion/deletion but require O(n) traversal. Stacks enforce LIFO access, queues enforce FIFO access. Hash tables provide O(1) average lookup through key-value mapping. Each structure trades off different performance characteristics for different problem types.

Core Concepts

Arrays and Dynamic Arrays

Arrays are fixed-size collections of elements stored in contiguous memory. Each element occupies the same space and is accessible via index.

Characteristics:

• Random access: O(1) to get element at any index
• Cache-friendly: Contiguous memory enables CPU cache optimization
• Fixed size: Cannot add elements beyond initial capacity
• Insertion/deletion: O(n) due to need to shift elements

Dynamic arrays (like Python lists or Java ArrayLists) resize automatically when needed, providing O(1) amortized insertion while maintaining array benefits.

Linked Lists

Linked lists are collections of nodes where each node contains data and a pointer to the next node. This enables efficient insertion/deletion without shifting.

Variants:

• Singly linked: Each node points to next only; traversal is unidirectional
• Doubly linked: Each node points to both next and previous; bidirectional traversal
• Circular: Last node points back to first; no explicit end

Characteristics:

• Access: O(n) - must traverse from head
• Insertion/deletion: O(1) if position is known (after finding position)
• Memory overhead: Extra space for pointers
• No random access: Cannot jump to middle elements

Stacks

Stacks are LIFO (Last In, First Out) collections where elements are added and removed from the same end (top).

Operations:

• Push: Add element to top - O(1)
• Pop: Remove element from top - O(1)
• Peek: View top element - O(1)

Applications:

• Function call stacks
• Undo/redo functionality
• Expression evaluation
• Parentheses matching

Queues

Queues are FIFO (First In, First Out) collections where elements are added at rear and removed from front.

Operations:

• Enqueue: Add element to rear - O(1)
• Dequeue: Remove element from front - O(1)
• Front: View front element - O(1)

Applications:

• Task scheduling
• Breadth-first search
• Print job queues
• Message processing

Hash Tables

Hash tables are key-value stores that use a hash function to map keys to array indices, enabling fast lookup.

Key concepts:

• Hash function: Converts key to array index
• Collision: Multiple keys map to same index
• Load factor: Ratio of entries to capacity
• Collision resolution: Chaining (linked lists at each index) or open addressing (find alternative slot)

Characteristics:

• Average case: O(1) for insert, delete, lookup
• Worst case: O(n) when collisions dominate
• Space: O(n) for n elements

Sets and Collections

Sets are unordered collections of unique elements. Multisets allow duplicate elements.

Properties:

• Uniqueness: Sets enforce no duplicates
• Membership testing: O(1) average case
• Set operations: Union, intersection, difference

Key Algorithms and Techniques

Linear Search in Arrays

Scan array sequentially to find element. O(n) time, no preprocessing needed.

Array Rotation

Shift elements left or right, wrapping around. Useful for circular buffer implementations.

Linked List Reversal

Iterate through list, reversing direction of pointers. In-place with O(n) time, O(1) space.

Stack-based Expression Evaluation

Convert infix to postfix notation using stack, then evaluate. Handles operator precedence correctly.

BFS with Queue

Process graph level-by-level by enqueueing all neighbors of current node. Discovers shortest paths in unweighted graphs.

Practical Example

Python

# Array operations
arr = [1, 2, 3, 4, 5]
arr.append(6)  # O(1) amortized
arr.insert(0, 0)  # O(n) - shifts elements
print(arr[2])  # O(1) random access

# Linked list node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Stack using list
stack = []
stack.append(1)  # Push
stack.append(2)
top = stack.pop()  # Pop - O(1)

# Queue using deque
from collections import deque
queue = deque()
queue.append(1)  # Enqueue
queue.popleft()  # Dequeue - O(1)

# Hash table / Dictionary
hash_map = {}
hash_map['key'] = 'value'  # O(1) average
if 'key' in hash_map:  # O(1) average
    print(hash_map['key'])

# Set operations
set_a = {1, 2, 3}
set_b = {2, 3, 4}
print(set_a & set_b)  # Intersection: {2, 3}
print(set_a | set_b)  # Union: {1, 2, 3, 4}
print(set_a - set_b)  # Difference: {1}

Java

import java.util.*;

public class DataStructures {
    static class Node {
        int value;
        Node next;
        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    public static void main(String[] args) {
        // Array operations
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(arr[2]);  // O(1) random access

        // Dynamic array (ArrayList)
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);  // O(1) amortized
        list.add(0, 0);  // O(n) insertion
        System.out.println(list.get(2));  // O(1)

        // Stack
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        int top = stack.pop();  // O(1)

        // Queue
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);  // Enqueue
        queue.remove();  // Dequeue - O(1)

        // Hash table
        HashMap<String, String> hashMap = new HashMap<>();
        hashMap.put("key", "value");  // O(1) average
        System.out.println(hashMap.get("key"));  // O(1) average

        // Set operations
        Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
        Set<Integer> set2 = new HashSet<>(Arrays.asList(2, 3, 4));
        set1.retainAll(set2);  // Intersection
    }
}

TypeScript

// Array operations
let arr: number[] = [1, 2, 3, 4, 5];
arr.push(6);  // O(1) amortized
arr.unshift(0);  // O(n) - shifts elements
console.log(arr[2]);  // O(1) random access

// Linked list node
class Node {
    constructor(public value: number, public next: Node | null = null) {}
}

// Stack using array
let stack: number[] = [];
stack.push(1);  // O(1)
stack.push(2);
let top = stack.pop();  // O(1)

// Queue using array deque pattern
class Queue<T> {
    private items: T[] = [];
    enqueue(item: T): void {
        this.items.push(item);  // O(1)
    }
    dequeue(): T | undefined {
        return this.items.shift();  // O(n) - use deque for O(1)
    }
}

// Hash table / Map
let hashMap = new Map<string, string>();
hashMap.set("key", "value");  // O(1) average
if (hashMap.has("key")) {  // O(1) average
    console.log(hashMap.get("key"));
}

// Set operations
let set1 = new Set([1, 2, 3]);
let set2 = new Set([2, 3, 4]);
let intersection = new Set([...set1].filter(x => set2.has(x)));
let union = new Set([...set1, ...set2]);

Common Pitfalls

warning

Confusing stack and queue order: Push/pop from same end (LIFO) for stacks; enqueue rear, dequeue front (FIFO) for queues. Mixing them up breaks algorithms like BFS.

Not accounting for linked list traversal cost: O(n) traversal overhead for linked lists differs from O(1) array access. Choose structures based on operation patterns.

Hash collision underestimation: Worst-case O(n) performance when collisions dominate. Monitor load factor and choose good hash functions.

Array bounds errors: Off-by-one errors accessing array elements cause crashes or corruption. Always verify indices are within [0, length-1].

Not freeing memory: Memory leaks from unreferenced linked list nodes. Explicitly nullify references when removing nodes.

Self-Check

1. Why is insertion O(n) in arrays but O(1) in linked lists? What trade-offs exist?
2. How does a hash table achieve O(1) average lookup? What causes worst-case O(n)?
3. When would you use a stack versus a queue? Give a real-world example for each.

One Takeaway

info

Each basic data structure excels at different operations. Arrays provide fast random access, linked lists enable fast insertion/deletion, stacks/queues enforce specific access patterns, and hash tables provide fast lookups by key. Understanding operation costs guides choosing the right structure for your problem.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
• Bhargava, A. Y. (2016). Grokking Algorithms. Manning Publications.