Data Structures

⏲ The Two Costs Every Developer Must Know (5–25 min)

📞 The Contacts App Story — 4 Structures, 1 Problem

Same data: 500 contacts (name + phone). Four different structures. Wildly different results.

💻 Live Coding — Build the Contact Book (25–45 min)

We'll build all four versions and measure the difference.

import java.util.*;

public class ContactBook {

    // ── Option 1: ArrayList ─────────────────────────────────────────────────
    private List<String[]> listContacts = new ArrayList<>();

    public void addToList(String name, String phone) {
        listContacts.add(new String[]{name, phone});
    }

    public String findByNameSlow(String name) {
        int steps = 0;
        for (String[] c : listContacts) {   // O(n) — checks every single contact
            steps++;
            if (c[0].equals(name)) {
                System.out.println("  ArrayList: found in " + steps + " steps");
                return c[1];
            }
        }
        return null;
    }

    // ── Option 3: HashMap (one-way) ─────────────────────────────────────────
    private Map<String, String> nameToPhone = new HashMap<>();

    public void addToMap(String name, String phone) {
        nameToPhone.put(name, phone);          // O(1) insert
    }

    public String findByNameFast(String name) {
        System.out.println("  HashMap: found in 1 step (O(1))");
        return nameToPhone.get(name);           // O(1) — always 1 step
    }

    // ── Option 4: Two HashMaps (bidirectional — WhatsApp caller ID) ─────────
    private Map<String, String> phoneToName = new HashMap<>(); // EXTRA memory!

    public void addBidirectional(String name, String phone) {
        nameToPhone.put(name, phone);   // store forward
        phoneToName.put(phone, name);   // store REVERSE — costs 2x space
    }

    public String whoseNumberIsThis(String phone) {
        return phoneToName.get(phone);      // O(1) — paid with space, not time
    }

    public static void main(String[] args) {
        ContactBook book = new ContactBook();

        // Add 500 contacts to both structures
        for (int i = 1; i <= 499; i++) {
            book.addToList("Contact" + i,  "9000000" + i);
            book.addToMap("Contact" + i,   "9000000" + i);
        }
        // Add "Priya" as the LAST contact — worst case for ArrayList
        book.addToList("Priya", "9876543210");
        book.addBidirectional("Priya", "9876543210");

        System.out.println("Searching for Priya...");
        book.findByNameSlow("Priya");     // 500 steps!
        book.findByNameFast("Priya");     // 1 step

        System.out.println("\nIncoming call: 9876543210");
        String caller = book.whoseNumberIsThis("9876543210");
        System.out.println("Caller: " + caller); // "Priya" — O(1), paid with 2x space
    }
}

Searching for Priya...
  ArrayList: found in 500 steps
  HashMap:   found in 1 step (O(1))

Incoming call: 9876543210
Caller: Priya

📄 When to Use Each Structure

Every structure has one job it does best. Pick the one whose weakness you can afford to ignore.

🌎 Where You See This in Real Apps