EMZETT.LinkedList
In short: A List implementation made of linked nodes — each node only knows its predecessor and successor, instead of sitting in a contiguous block of memory.
In more detail: Inserting/removing at the start or in the middle is fast for a LinkedList (no shifting needed), but access by index is slow, since the list has to be walked from the start. LinkedList also implements Deque, so it can also be used as a stack or queue.
In Depth
LinkedList<String> queue = new LinkedList<>();
// Use as a queue (FIFO) - via the Deque interface
queue.addLast("First");
queue.addLast("Second");
System.out.println(queue.removeFirst()); // "First" - comes out first
// Use as a stack (LIFO)
LinkedList<Integer> stack = new LinkedList<>();
stack.push(1); stack.push(2); stack.push(3);
System.out.println(stack.pop()); // 3 - last in, first out
// Insert at the start - O(1) for LinkedList, O(n) for ArrayList!
queue.addFirst("Right at the front");The decisive performance difference from ArrayList shows up when inserting/removing AT THE START or in the middle: an ArrayList has to shift all subsequent elements in memory (O(n)), while a LinkedList only adjusts the linking between the affected nodes (O(1), provided you already have a reference to the insertion point). In return, LinkedList loses significantly for direct index access (get(i)), because it has to work its way from one end of the list to the sought position, instead of jumping directly to the computed memory address (like ArrayList). In practice, ArrayDeque is usually the better choice today than LinkedList for pure stack/queue use cases, because internally it uses an array instead of individual nodes and is therefore more cache-friendly (and thus often faster in practice).