Java LinkedList Explained — How It Works, When to Use It, and What to Avoid

import java.util.LinkedList;

public class LinkedListInternals {
    public static void main(String[] args) {

        // Creating an empty LinkedList — only head and tail references exist at this point
        LinkedList<String> browserHistory = new LinkedList<>();

        // addFirst() is O(1) — just rewires the head pointer
        browserHistory.addFirst("google.com");
        browserHistory.addFirst("github.com");  // github is now the new head
        browserHistory.addFirst("stackoverflow.com"); // stackoverflow is now head

        // addLast() is also O(1) — just rewires the tail pointer
        browserHistory.addLast("codeforge.io");

        System.out.println("Browser history (front to back):");
        System.out.println(browserHistory);
        // Prints in insertion order: [stackoverflow.com, github.com, google.com, codeforge.io]

        System.out.println("\nFirst page visited: " + browserHistory.getFirst()); // O(1)
        System.out.println("Last page visited:  " + browserHistory.getLast());  // O(1)

        // get(index) must walk the chain — notice Java is smart enough to start
        // from the TAIL if the index is in the second half of the list
        System.out.println("Page at index 2:    " + browserHistory.get(2)); // O(n)

        System.out.println("\nTotal pages in history: " + browserHistory.size());

        // removeFirst() is O(1) — back button pops from the front
        String closedPage = browserHistory.removeFirst();
        System.out.println("\nClosed tab: " + closedPage);
        System.out.println("History after closing: " + browserHistory);
    }
}

import java.util.Deque;
import java.util.LinkedList;

public class TaskQueueDemo {

    // Simulates a customer support ticket system
    // Regular tickets go to the back; VIP tickets jump to the front
    public static void main(String[] args) {

        // Declare against the Deque interface — not LinkedList directly.
        // This keeps your code flexible (easy to swap implementation later)
        Deque<String> supportQueue = new LinkedList<>();

        // Standard customers — addLast() puts them at the back of the queue (O(1))
        supportQueue.addLast("Ticket #101 — Password reset");
        supportQueue.addLast("Ticket #102 — Billing question");
        supportQueue.addLast("Ticket #103 — Feature request");

        System.out.println("Initial queue: " + supportQueue);

        // VIP customer — addFirst() jumps them to the front without reshuffling anything (O(1))
        supportQueue.addFirst("Ticket #104 — VIP account locked [URGENT]");

        System.out.println("After VIP ticket: " + supportQueue);

        System.out.println("\n--- Processing tickets ---");

        // peekFirst() lets us SEE the next ticket without removing it (O(1))
        System.out.println("Up next: " + supportQueue.peekFirst());

        // Process all tickets in FIFO order using removeFirst() (O(1) each time)
        while (!supportQueue.isEmpty()) {
            String currentTicket = supportQueue.removeFirst();
            System.out.println("Resolving: " + currentTicket);
        }

        // peekFirst() returns null on an empty deque — no exception
        System.out.println("\nQueue empty. Next ticket: " + supportQueue.peekFirst());

        // Compare: removeFirst() on empty queue WOULD throw NoSuchElementException
        // Use pollFirst() instead if empty queue is a normal condition — it returns null safely
        System.out.println("Safe poll on empty queue: " + supportQueue.pollFirst());
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class PerformanceComparison {

    private static final int OPERATION_COUNT = 100_000;

    public static void main(String[] args) {

        // --- TEST 1: Repeated insertion at the FRONT ---
        // ArrayList must shift every existing element right — O(n) per insert
        // LinkedList just rewires the head pointer — O(1) per insert

        List<Integer> arrayList = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < OPERATION_COUNT; i++) {
            arrayList.add(0, i); // always insert at index 0 (the front)
        }
        long arrayListFrontInsertTime = System.nanoTime() - startTime;

        List<Integer> linkedList = new LinkedList<>();
        startTime = System.nanoTime();
        for (int i = 0; i < OPERATION_COUNT; i++) {
            ((LinkedList<Integer>) linkedList).addFirst(i); // O(1) head rewire
        }
        long linkedListFrontInsertTime = System.nanoTime() - startTime;

        System.out.println("=== Front Insertion " + OPERATION_COUNT + " times ===");
        System.out.printf("ArrayList:  %,d ms%n", arrayListFrontInsertTime / 1_000_000);
        System.out.printf("LinkedList: %,d ms%n", linkedListFrontInsertTime / 1_000_000);

        // --- TEST 2: Sequential READ (iteration) ---
        // ArrayList wins here due to CPU cache locality — elements are contiguous in memory
        // LinkedList nodes are scattered on the heap — expect cache misses

        startTime = System.nanoTime();
        long arraySum = 0;
        for (int value : arrayList) { // enhanced for-loop uses Iterator internally
            arraySum += value;
        }
        long arrayListReadTime = System.nanoTime() - startTime;

        startTime = System.nanoTime();
        long linkedSum = 0;
        for (int value : linkedList) {
            linkedSum += value;
        }
        long linkedListReadTime = System.nanoTime() - startTime;

        System.out.println("\n=== Sequential Iteration ===");
        System.out.printf("ArrayList:  %,d ms%n", arrayListReadTime / 1_000_000);
        System.out.printf("LinkedList: %,d ms%n", linkedListReadTime / 1_000_000);
        // Confirm both computed the same sum (sanity check)
        System.out.println("Sums match: " + (arraySum == linkedSum));
    }
}

import java.util.LinkedList;
import java.util.ListIterator;

public class MidStreamEnrichment {

    // Real-world scenario: we have a log pipeline.
    // After every ERROR entry, we want to inject a DIAGNOSTIC_CHECK entry.
    // We're scanning the list once and enriching it in-place.

    public static void main(String[] args) {

        LinkedList<String> logPipeline = new LinkedList<>();
        logPipeline.add("INFO  — Server started");
        logPipeline.add("INFO  — Request received");
        logPipeline.add("ERROR — Database timeout");   // inject after this
        logPipeline.add("INFO  — Retry attempted");
        logPipeline.add("ERROR — Auth token expired"); // and after this
        logPipeline.add("INFO  — Session closed");

        System.out.println("Before enrichment:");
        logPipeline.forEach(System.out::println);

        // ListIterator lets us traverse AND modify the list safely at the same time.
        // It holds a direct node reference — no index lookup needed for add/remove.
        ListIterator<String> iterator = logPipeline.listIterator();

        while (iterator.hasNext()) {
            String logEntry = iterator.next();

            if (logEntry.startsWith("ERROR")) {
                // iterator.add() inserts AFTER the current element in O(1)
                // This is the key win over ArrayList: no array shifting happens
                iterator.add("DIAG  — Running diagnostic snapshot...");
            }
        }

        System.out.println("\nAfter enrichment:");
        logPipeline.forEach(System.out::println);

        System.out.println("\nTotal entries after enrichment: " + logPipeline.size());
    }
}