LinkedList OutOfMemoryError — 32 Bytes Per Node Overhead

package io.thecodeforge.java.collections;

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

public class LinkedListBasics {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        list.add("banana");
        list.add("cherry");
        list.add(0, "apple");  // insert at head — O(1) for LinkedList, O(n) for ArrayList

        System.out.println(list);      // [apple, banana, cherry]
        System.out.println(list.get(1)); // banana — O(n) traversal
        list.remove(1);                 // O(n) to find, O(1) to remove
        System.out.println(list);      // [apple, cherry]
    }
}

package io.thecodeforge.java.collections;

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

public class LinkedListDeque {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();

        // O(1) operations at both ends
        deque.addFirst(2);   // [2]
        deque.addFirst(1);   // [1, 2]
        deque.addLast(3);    // [1, 2, 3]
        deque.addLast(4);    // [1, 2, 3, 4]

        System.out.println(deque.peekFirst()); // 1
        System.out.println(deque.peekLast());  // 4
        System.out.println(deque.pollFirst()); // 1 — remove from front
        System.out.println(deque.pollLast());  // 4 — remove from back
        System.out.println(deque);             // [2, 3]
    }
}

package io.thecodeforge.java.collections;

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

public class MemoryOverhead {
    public static void main(String[] args) throws Exception {
        int N = 1_000_000;
        List<Integer> linked = new LinkedList<>();
        List<Integer> array = new ArrayList<>(N);

        // Fill both
        for (int i = 0; i < N; i++) {
            linked.add(i);
            array.add(i);
        }

        // Measure approximate memory (requires -XX:+UseCompressedOops)
        Runtime rt = Runtime.getRuntime();
        rt.gc();
        long memLinked = rt.totalMemory() - rt.freeMemory();

        // Clear linked, keep array reference alive
        linked.clear();
        rt.gc();
        long memArray = rt.totalMemory() - rt.freeMemory();

        System.out.printf("LinkedList with %d ints: ~%d MB%n", N, memLinked / (1024*1024));
        System.out.printf("ArrayList   with %d ints: ~%d MB%n", N, memArray / (1024*1024));
        System.out.println("Difference is node overhead (prev + next + header).");
    }
}

// The Node class from OpenJDK's LinkedList:
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {\n        this.item = element;\n        this.next = next;\n        this.prev = prev;\n    }
}

package io.thecodeforge.java.collections;

import java.util.*;

public class Benchmark {
    static final int N = 100_000;

    public static void main(String[] args) {
        // Scenario 1: Random access — ArrayList wins decisively
        List<Integer> arrayList = new ArrayList<>(Collections.nCopies(N, 1));
        List<Integer> linkedList = new LinkedList<>(Collections.nCopies(N, 1));

        long start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) arrayList.get(N / 2);
        System.out.printf("ArrayList random access:  %,dns%n", System.nanoTime() - start);

        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) linkedList.get(N / 2);
        System.out.printf("LinkedList random access: %,dns (much slower)%n", System.nanoTime() - start);

        // Scenario 2: Insert at head — LinkedList wins
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) arrayList.add(0, 0);
        System.out.printf("ArrayList head insert:  %,dns%n", System.nanoTime() - start);

        Deque<Integer> deque = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) deque.addFirst(0);
        System.out.printf("LinkedList head insert: %,dns%n", System.nanoTime() - start);
    }
}

package io.thecodeforge.java.collections;

import java.util.Deque;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class ThreadSafeDeque {
    public static void main(String[] args) {
        // Lock-free concurrent deque — preferred
        Deque<String> concurrentDeque = new ConcurrentLinkedDeque<>();
        concurrentDeque.addFirst("task1");
        concurrentDeque.addLast("task2");
        // Can be shared safely across threads
        
        // Synchronized LinkedList — use only if you need List interface
        List<String> syncList = Collections.synchronizedList(new LinkedList<>());
        syncList.add("item");
        // Access must be done within synchronized block for iteration
        synchronized (syncList) {
            for (String s : syncList) {
                System.out.println(s);
            }
        }
    }
}

package io.thecodeforge.java.collections;

import java.util.LinkedList;

public class LinkedListPracticeProblems {
    public static void main(String[] args) {
        // Problem 1: Queue using LinkedList
        LinkedList<String> queue = new LinkedList<>();
        queue.addLast("A"); // enqueue
        queue.addLast("B");
        queue.addLast("C");
        System.out.println("Queue front: " + queue.peekFirst()); // A
        queue.pollFirst(); // dequeue
        System.out.println("Queue after dequeue: " + queue); // [B, C]

        // Problem 2: Stack using LinkedList
        LinkedList<Integer> stack = new LinkedList<>();
        stack.addFirst(1); // push
        stack.addFirst(2);
        stack.addFirst(3);
        System.out.println("Stack top: " + stack.peekFirst()); // 3
        stack.pollFirst(); // pop
        System.out.println("Stack after pop: " + stack); // [2, 1]

        // Problem 3: Reverse a LinkedList
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); list.add(2); list.add(3); list.add(4);
        LinkedList<Integer> reversed = new LinkedList<>();
        for (int val : list) reversed.addFirst(val);
        System.out.println("Reversed: " + reversed); // [4, 3, 2, 1]

        // Problem 4: Find middle using slow-fast
        LinkedList<Integer> list2 = new LinkedList<>();
        for (int i = 1; i <= 7; i++) list2.add(i);
        var slow = list2.listIterator();
        var fast = list2.listIterator();
        while (fast.hasNext()) {
            fast.next();
            if (fast.hasNext()) fast.next();
            else break;
            slow.next();
        }
        System.out.println("Middle element: " + slow.next()); // 4

        // Problem 5: Detect cycle (using reference manipulation, but here we check by definition)
        // For a cycle detection, we need custom node class. Pseudocode provided.
        System.out.println("Cycle detection: Use slow-fast pointers — if they meet, there is a cycle.");
    }
}

package io.thecodeforge.java.collections;

import java.util.*;

public class WhenToUseLinkedList {
    public static void main(String[] args) {
        // Use case 1: iterator removal
        LinkedList<String> tasks = new LinkedList<>(List.of("task1", "task2", "task3", "task4"));
        var it = tasks.iterator();
        while (it.hasNext()) {
            String task = it.next();
            if (task.equals("task2")) {
                it.remove(); // O(1) in LinkedList, O(n) in ArrayList
            }
        }
        System.out.println("After removal: " + tasks);

        // Use case 2: Deque + List interface
        List<String> list = new LinkedList<>();
        Deque<String> deque = (Deque<String>) list; // same object
        deque.addFirst("front");
        deque.addLast("back");
        // list is now [front, back]
        System.out.println("List view: " + list.get(0)); // front
    }
}