LinkedList in Java
Java's LinkedList implements both List and Deque. Internally it uses a doubly linked list of Node objects, where each node holds a reference to its element...
Structure of a Doubly Linked List
Java's LinkedList implements both List and Deque. Internally it uses a doubly linked list of Node objects, where each node holds a reference to its element, the previous node, and the next node. The class tracks a head node (called first) and a tail node (called last) along with a size counter.
Because there is no backing array, LinkedList never needs to reallocate or copy elements. Insertion at either end is always O(1): adding to the head updates first, and adding to the tail updates last. Removal from either end is equally O(1). These characteristics make LinkedList an excellent candidate for queue or deque operations where you repeatedly add to one end and remove from the other.
However, positional access runs in O(n) because the only way to reach index k is to traverse the chain of node references starting from whichever end is closer. LinkedList optimizes this slightly by starting from first when k is less than size/2 and from last otherwise, but it remains linear.
LinkedList as a Deque
Because LinkedList implements Deque, it exposes methods like addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast, making it usable as a stack, queue, or double-ended queue without extra wrappers. Calling push(e) is equivalent to addFirst(e) and pop() is equivalent to removeFirst(), giving stack semantics. Calling offer(e) adds to the tail and poll() removes from the head, giving queue semantics.
Memory overhead is a trade-off. Every element in a LinkedList requires a Node object holding three references (element, prev, next), so the per-element overhead is roughly 24 bytes on a 64-bit JVM (without compressed oops). An ArrayList of the same size uses only the element reference plus a fraction of the array header, making it more memory efficient for large collections.
When to Choose LinkedList and Interview Tip
Choose LinkedList when you frequently insert or remove elements at the front or middle of the list and rarely access elements by index. If your access pattern is mostly random reads or iteration, ArrayList is faster due to cache locality: array elements sit contiguously in memory, allowing the CPU prefetcher to load upcoming elements efficiently. Node-based structures scatter data across the heap, defeating prefetching.
A short code example showing queue use: LinkedList<String> queue = new LinkedList<>(); queue.offer("first"); queue.offer("second"); System.out.println(queue.poll()); prints first, demonstrating FIFO behavior.
An interview tip: interviewers sometimes ask why LinkedList is rarely used in production Java today. The answer is that for most workloads ArrayList outperforms LinkedList even for insertions because of CPU cache effects. Only when you have a proven bottleneck at head insertions or true deque operations should you reach for LinkedList.