LinkedList Internals
Explore the doubly-linked node structure of LinkedList and its time complexity profile.
LinkedList Internals is a free Java Academy lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Java Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
LinkedList Internals
Java's LinkedList is a doubly-linked list: each node holds a reference to the previous and next node, plus the element value. Unlike ArrayList, there is no backing array — memory is allocated per node.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Time Complexity Profile
LinkedList's performance characteristics differ significantly from ArrayList:
- addFirst / addLast: O(1)
- get(index): O(n) — must traverse from head or tail
- remove(index): O(n) to find, then O(1) to unlink
- Iterator traversal: O(n)
Use LinkedList when you need frequent head/tail insertions, not random access.
Creating and Traversing a LinkedList
Creating a LinkedList and iterating follows the same List interface you already know. The difference is internal structure.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList exposes head/tail operations that ArrayList doesn't offer efficiently:
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Node Unlinking: O(1) Delete After Finding
Once you have a reference to a node (via iterator), removal is O(1) because only next/prev pointers need updating — no element shifting like ArrayList.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]Memory Overhead vs ArrayList
Each LinkedList node carries two extra references (prev, next) plus the element reference — about 48 bytes per entry on a 64-bit JVM. ArrayList stores just the element reference (8 bytes) in a contiguous array.
For large read-heavy datasets, ArrayList is usually more cache-friendly and uses less memory.
Deque Operations: Stack and Queue
LinkedList implements the Deque interface, making it usable as both a stack and a queue.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topPriorityQueue Overview
PriorityQueue is a heap-based queue where the smallest element (by natural order or comparator) is always dequeued first. It is NOT backed by a linked list — it uses a binary heap array.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40PriorityQueue with Custom Comparator
Pass a Comparator to invert ordering or sort by a custom field:
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowChoosing LinkedList vs ArrayList
Rule of thumb:
- Use ArrayList for random access, iteration, and most scenarios.
- Use LinkedList when you need frequent O(1) insertions/removals at both ends and don't need index access.
- Use PriorityQueue when you need ordered processing (task scheduling, Dijkstra's algorithm).
Common Pitfalls
Avoid calling get(i) in a loop on a LinkedList — it's O(n²) total:
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}Quick Check
Which LinkedList operation is O(1) regardless of list size?
Recap: LinkedList & Deque
Key takeaways:
- LinkedList is a doubly-linked list with O(1) head/tail operations
- Random access (get/set by index) is O(n)
- Implements Deque — usable as stack or queue
- PriorityQueue provides heap-ordered processing
- Prefer ArrayList for most use cases; LinkedList shines at frequent head/tail mutations
Frequently asked questions
Is the “LinkedList Internals” lesson free?
Yes — the full text of “LinkedList Internals” is free to read here on the web, and the Java Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Java Academy course, upgrade to CoddyKit PRO.
What will I learn in “LinkedList Internals”?
Explore the doubly-linked node structure of LinkedList and its time complexity profile. You practise Java Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Java Academy?
No prior experience is required. Java Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “LinkedList Internals” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Java Academy lesson?
Yes. Every Java Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.