ArrayDeque vs LinkedList — Node Allocation Traps

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStackAndQueue {

    public static void main(String[] args) {

        // ── Using ArrayDeque as a STACK (LIFO) ──────────────────────────
        // Think: a stack of pancakes — last one placed is first one eaten.
        Deque<String> browserHistory = new ArrayDeque<>();

        browserHistory.push("google.com");     // pushes to the FRONT (head)
        browserHistory.push("github.com");     // pushes to the FRONT, google moves back
        browserHistory.push("thecodeforge.io"); // now this is at the top

        System.out.println("=== Browser History (Stack) ===");
        System.out.println("Current page : " + browserHistory.peek()); // look without removing
        System.out.println("Going back   : " + browserHistory.pop());  // removes from front
        System.out.println("Now on       : " + browserHistory.peek());

        // ── Using ArrayDeque as a QUEUE (FIFO) ──────────────────────────
        // Think: a printer queue — first document sent is first printed.
        Deque<String> printQueue = new ArrayDeque<>();

        printQueue.offerLast("invoice.pdf");   // add to the TAIL
        printQueue.offerLast("report.docx");   // add to the TAIL
        printQueue.offerLast("photo.png");     // add to the TAIL

        System.out.println("\n=== Print Queue (FIFO) ===");
        // pollFirst() removes from the HEAD — first in, first out
        while (!printQueue.isEmpty()) {
            System.out.println("Printing: " + printQueue.pollFirst());
        }

        // ── Using BOTH ends simultaneously ───────────────────────────────
        // A sliding window of the last 3 user actions
        Deque<String> recentActions = new ArrayDeque<>();
        String[] actions = {"login", "view-dashboard", "edit-profile", "upload-photo", "logout"};
        int windowSize = 3;

        System.out.println("\n=== Last " + windowSize + " Actions ===");
        for (String action : actions) {
            recentActions.offerLast(action);         // new action enters at the tail
            if (recentActions.size() > windowSize) {
                recentActions.pollFirst();           // oldest action drops from the head
            }
        }
        System.out.println("Recent actions: " + recentActions);
    }
}

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class ArrayDequeInternals {

    // A simple benchmark to make the performance difference tangible.
    // Not a rigorous JMH benchmark, but good enough to see the shape.
    static final int OPERATIONS = 1_000_000;

    public static void main(String[] args) {

        // ── ArrayDeque timing ────────────────────────────────────────────
        Deque<Integer> arrayDeque = new ArrayDeque<>(OPERATIONS); // pre-size to avoid resizing
        long start = System.nanoTime();
        for (int i = 0; i < OPERATIONS; i++) {
            arrayDeque.push(i);         // addFirst under the hood
        }
        for (int i = 0; i < OPERATIONS; i++) {
            arrayDeque.pop();           // removeFirst under the hood
        }
        long arrayDequeMs = (System.nanoTime() - start) / 1_000_000;

        // ── LinkedList timing ────────────────────────────────────────────
        Deque<Integer> linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < OPERATIONS; i++) {
            linkedList.push(i);
        }
        for (int i = 0; i < OPERATIONS; i++) {
            linkedList.pop();
        }
        long linkedListMs = (System.nanoTime() - start) / 1_000_000;

        // ── Legacy Stack timing ──────────────────────────────────────────
        Stack<Integer> legacyStack = new Stack<>();
        start = System.nanoTime();
        for (int i = 0; i < OPERATIONS; i++) {
            legacyStack.push(i);
        }
        for (int i = 0; i < OPERATIONS; i++) {
            legacyStack.pop();
        }
        long stackMs = (System.nanoTime() - start) / 1_000_000;

        System.out.println("=== 1,000,000 push + pop operations ===");
        System.out.printf("ArrayDeque  : %d ms%n", arrayDequeMs);
        System.out.printf("LinkedList  : %d ms%n", linkedListMs);
        System.out.printf("Stack       : %d ms%n", stackMs);

        // ── Null safety demonstration ────────────────────────────────────
        System.out.println("\n=== Null element behaviour ===");
        try {
            Deque<String> noNulls = new ArrayDeque<>();
            noNulls.offerLast(null);   // ArrayDeque rejects null
        } catch (NullPointerException e) {
            // ArrayDeque throws NPE rather than silently storing null
            System.out.println("ArrayDeque: null rejected — " + e.getClass().getSimpleName());
        }

        Deque<String> nullsOk = new LinkedList<>();
        nullsOk.offerLast(null);       // LinkedList accepts null
        System.out.println("LinkedList : null accepted, poll() returns: " + nullsOk.pollFirst());
        // Ambiguous! Is null because the queue had a null element, or because it's empty?
        System.out.println("LinkedList : poll() on empty returns: " + nullsOk.pollFirst());
        // Both print null — you can't tell the difference.
    }
}

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;

// Simulates a minimal text editor with undo/redo support.
public class UndoRedoEditor {

    private final Deque<String> undoStack = new ArrayDeque<>(); // commands we can undo
    private final Deque<String> redoStack = new ArrayDeque<>(); // commands we can redo
    private final StringBuilder document = new StringBuilder();

    // Performs a new edit and records it for potential undo
    public void performEdit(String command, String text) {
        String snapshot = document.toString(); // save state BEFORE the change
        applyEdit(command, text);
        undoStack.push(snapshot);  // push old state so undo can restore it
        redoStack.clear();         // branching — future redo history is now invalid
        System.out.println("[EDIT]   command='" + command + "' text='" + text
                + "' | doc now: '" + document + "'");
    }

    // Undoes the last edit
    public void undo() {
        if (undoStack.isEmpty()) {
            System.out.println("[UNDO]   nothing to undo");
            return;
        }
        redoStack.push(document.toString()); // save current state so redo can restore it
        String previousState = undoStack.pop(); // restore the state before last edit
        document.setLength(0);
        document.append(previousState);
        System.out.println("[UNDO]   doc now: '" + document + "'");
    }

    // Redoes the last undone edit
    public void redo() {
        if (redoStack.isEmpty()) {
            System.out.println("[REDO]   nothing to redo");
            return;
        }
        undoStack.push(document.toString()); // save current so we can undo the redo
        String redoState = redoStack.pop();
        document.setLength(0);
        document.append(redoState);
        System.out.println("[REDO]   doc now: '" + document + "'");
    }

    private void applyEdit(String command, String text) {
        switch (command) {
            case "append" -> document.append(text);
            case "delete" -> {
                int len = Math.min(text.length(), document.length());
                document.delete(document.length() - len, document.length());
            }
            default -> throw new IllegalArgumentException("Unknown command: " + command);
        }
    }

    public static void main(String[] args) {
        UndoRedoEditor editor = new UndoRedoEditor();

        editor.performEdit("append", "Hello");
        editor.performEdit("append", ", World");
        editor.performEdit("append", "!");

        System.out.println();
        editor.undo();   // removes '!'
        editor.undo();   // removes ', World'

        System.out.println();
        editor.redo();   // restores ', World'

        System.out.println();
        // Performing a new edit here clears redo history
        editor.performEdit("append", " from Java");
        editor.redo();   // nothing to redo — new branch forked the history
    }
}

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

public class DequeMethodReference {

    public static void main(String[] args) {

        Deque<String> taskQueue = new ArrayDeque<>();

        // ── Adding elements ──────────────────────────────────────────────
        taskQueue.offerFirst("low-priority-task");   // safe add to HEAD
        taskQueue.offerLast("normal-task");           // safe add to TAIL
        taskQueue.offerFirst("urgent-task");          // jumps to the front

        // taskQueue is now: [urgent-task, low-priority-task, normal-task]
        System.out.println("Queue: " + taskQueue);

        // ── Peeking (non-destructive) ────────────────────────────────────
        System.out.println("Next up (head): " + taskQueue.peekFirst());  // does NOT remove
        System.out.println("Last in (tail): " + taskQueue.peekLast());   // does NOT remove
        System.out.println("Still intact  : " + taskQueue);              // unchanged

        // ── Removing elements ────────────────────────────────────────────
        String nextTask = taskQueue.pollFirst(); // safe remove from HEAD, returns null if empty
        System.out.println("Processing: " + nextTask);
        System.out.println("Remaining : " + taskQueue);

        // ── Throwing vs safe variants ────────────────────────────────────
        Deque<String> emptyDeque = new ArrayDeque<>();

        // Safe — returns null, no exception
        String safeResult = emptyDeque.pollFirst();
        System.out.println("\npollFirst on empty: " + safeResult); // null

        // Throwing — raises NoSuchElementException
        try {
            emptyDeque.removeFirst(); // throws because the deque is empty
        } catch (NoSuchElementException e) {
            System.out.println("removeFirst on empty: " + e.getClass().getSimpleName());
        }

        // ── Stack aliases (push/pop operate on the HEAD) ─────────────────
        Deque<Integer> callStack = new ArrayDeque<>();
        callStack.push(1);  // same as addFirst(1)
        callStack.push(2);  // same as addFirst(2)
        callStack.push(3);  // same as addFirst(3)
        System.out.println("\nCall stack top: " + callStack.peek()); // 3 — same as peekFirst()
        System.out.println("Popped        : " + callStack.pop());   // 3 — same as removeFirst()
        System.out.println("New top       : " + callStack.peek());  // 2

        // ── Size checks ──────────────────────────────────────────────────
        System.out.println("\nSize    : " + callStack.size());
        System.out.println("Empty?  : " + callStack.isEmpty());
        System.out.println("Contains 1? : " + callStack.contains(1)); // O(n) linear scan
    }
}

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequePreSize {

    public static void main(String[] args) {
        final int OPERATIONS = 1_000_000;

        // ── Without pre-sizing (starts at capacity 16, resizes multiple times) ──
        Deque<Integer> noPresize = new ArrayDeque<>();
        long start = System.nanoTime();
        for (int i = 0; i < OPERATIONS; i++) {
            noPresize.offerLast(i);
        }
        for (int i = 0; i < OPERATIONS; i++) {
            noPresize.pollFirst();
        }
        long noPresizeMs = (System.nanoTime() - start) / 1_000_000;

        // ── With pre-sizing (exact capacity) ─────────────────────────────
        Deque<Integer> presize = new ArrayDeque<>(OPERATIONS);
        start = System.nanoTime();
        for (int i = 0; i < OPERATIONS; i++) {
            presize.offerLast(i);
        }
        for (int i = 0; i < OPERATIONS; i++) {
            presize.pollFirst();
        }
        long presizeMs = (System.nanoTime() - start) / 1_000_000;

        System.out.println("=== 1,000,000 offer/poll operations ===");
        System.out.printf("Without pre-sizing: %d ms (includes %d resizes)%n", noPresizeMs, (int)(Math.log(OPERATIONS/16)/Math.log(2)));
        System.out.printf("With pre-sizing   : %d ms%n", presizeMs);
        System.out.println("Pre-sizing eliminates resize overhead — especially noticeable with large capacities.");
    }
}