ListMemoryDemo.java

import java.util.*;

/**
 * Demonstrates memory layout and internal structure of different List implementations
 * Key concepts: ArrayList vs LinkedList, memory overhead, cache locality
 */
public class ListMemoryDemo {
    
    public static void main(String[] args) {
        System.out.println("=== List Memory Layout Demo ===\n");
        
        demonstrateArrayList();
        demonstrateLinkedList();
        comparePerformance();
    }
    
    private static void demonstrateArrayList() {
        System.out.println("1. ArrayList - Contiguous Memory Layout");
        System.out.println("   - Backed by an array");
        System.out.println("   - Elements stored sequentially in memory");
        System.out.println("   - Good cache locality for iteration\n");
        
        ArrayList<String> arrayList = new ArrayList<>(3);
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        
        System.out.println("   ArrayList: " + arrayList);
        System.out.println("   Memory: [A][B][C] - contiguous block");
        System.out.println("   Random access: O(1) - direct index calculation\n");
    }
    
    private static void demonstrateLinkedList() {
        System.out.println("2. LinkedList - Node-based Memory Layout");
        System.out.println("   - Each element is a separate Node object");
        System.out.println("   - Nodes scattered in heap memory");
        System.out.println("   - Each node has data + prev/next pointers\n");
        
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("X");
        linkedList.add("Y");
        linkedList.add("Z");
        
        System.out.println("   LinkedList: " + linkedList);
        System.out.println("   Memory: [Node(X)]-->[Node(Y)]-->[Node(Z)]");
        System.out.println("   Random access: O(n) - must traverse from head\n");
    }
    
    private static void comparePerformance() {
        System.out.println("3. Performance Comparison (10,000 elements)");
        
        int size = 10000;
        
        // ArrayList performance
        ArrayList<Integer> arrayList = new ArrayList<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        long arrayListAddTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += arrayList.get(i);
        }
        long arrayListGetTime = System.nanoTime() - start;
        
        // LinkedList performance
        LinkedList<Integer> linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }
        long linkedListAddTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        sum = 0;
        for (int i = 0; i < size; i++) {
            sum += linkedList.get(i);
        }
        long linkedListGetTime = System.nanoTime() - start;
        
        System.out.println("   ArrayList:");
        System.out.printf("     - Add time: %.2f ms%n", arrayListAddTime / 1_000_000.0);
        System.out.printf("     - Random access time: %.2f ms%n", arrayListGetTime / 1_000_000.0);
        
        System.out.println("   LinkedList:");
        System.out.printf("     - Add time: %.2f ms%n", linkedListAddTime / 1_000_000.0);
        System.out.printf("     - Random access time: %.2f ms%n", linkedListGetTime / 1_000_000.0);
        
        System.out.println("\n   Key Takeaway:");
        System.out.println("   - ArrayList: Better for random access (cache-friendly)");
        System.out.println("   - LinkedList: Better for frequent insertions/deletions at ends");
    }
}