The LinkedList class in Java is a doubly linked list that implements both the List and the Deque interfaces, so we can use it as an indexed list, a queue or a stack. Each element sits in its own node with links to the previous and the next node, which makes adding and removing at either end an O(1) operation, while access by index takes O(n).
We use LinkedList when the code works mostly at the two ends of a sequence or inserts elements through an iterator, for example an undo history or a playback queue. For indexed reads, ArrayList is faster, and for pure queues and stacks, ArrayDeque is.
The following example calls the end methods, an index read and the Java 21 reversed() view on one LinkedList, with each result as a comment.
LinkedList<String> tasks = new LinkedList<>(List.of("write", "test"));
tasks.addFirst("plan"); // at the head, O(1)
tasks.addLast("deploy"); // at the tail, O(1)
String first = tasks.getFirst(); // "plan"
String last = tasks.getLast(); // "deploy"
String third = tasks.get(2); // "test", walks the nodes
String done = tasks.removeFirst(); // "plan"
LinkedList<String> backwards = tasks.reversed(); // [deploy, test, write]
String next = new LinkedList<String>().poll(); // null, empty listNotice that poll() on an empty list returns null, while removeFirst() would throw an exception. We look at the node structure, list operations and iterator inserts, queue and stack usage with an undo example, the Java 21 sequenced methods, the real cost of each operation, and thread-safe alternatives.
1. Nodes and Links in a LinkedList
A LinkedList object holds three fields, a reference to the first node, a reference to the last node and the size. Every node holds one element plus a prev and a next reference. Nothing is stored in a contiguous array, so the list never resizes or shifts elements.
The structure explains the costs. Adding at the head creates a node and changes two links, whatever the size. Reading get(500) in a list of 1,000 elements follows about 500 links, because the class walks from whichever end is closer to the index.
// does not compile: simplified excerpt of the JDK fields
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size;
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
}A LinkedList accepts duplicates and null, and it keeps insertion order. It does not implement RandomAccess, which is the marker interface that tells generic algorithms such as Collections.binarySearch() that index access is cheap.
2. Using LinkedList as a List
All List methods work on LinkedList, and the results are the same as on an ArrayList. The difference is only in the cost, which we cover in section 5.
LinkedList<String> stations = new LinkedList<>(List.of("A", "C", "D"));
stations.add(1, "B"); // insert at index 1
String old = stations.set(3, "E"); // "D", replaced
int pos = stations.indexOf("C"); // 2
boolean has = stations.contains("Z"); // false
List<String> all = stations; // [A, B, C, E]For a list of Integer, the two remove() methods are a common source of mistakes. A call with an int removes by index, and a call with an Integer object removes by value.
LinkedList<Integer> codes = new LinkedList<>(List.of(10, 20, 30));
Integer byIndex = codes.remove(1); // 20, removed index 1
boolean byValue = codes.remove(Integer.valueOf(10)); // true, removed value 10
List<Integer> left = codes; // [30]The real strength of a linked list is an insert or a removal while we iterate. A ListIterator already points at the right node, so add() and remove() on the iterator change only the neighboring links in O(1), without the shifting that an ArrayList needs.
LinkedList<String> route = new LinkedList<>(List.of("home", "office", "gym"));
ListIterator<String> stops = route.listIterator();
while (stops.hasNext()) {
if (stops.next().equals("office")) {
stops.add("cafe");
}
}
List<String> withCafe = route; // [home, office, cafe, gym]The ListIterator article covers the other iterator methods, such as previous() and set().
3. Using LinkedList as a Queue, Deque or Stack
Because LinkedList implements Deque, it offers a method for every end-of-list operation in two styles. One style throws an exception when the list is empty, and the other returns null, which suits polling loops.
| Operation | Throws on empty | Returns null on empty | Typical use |
|---|---|---|---|
| Add at tail | addLast(e), add(e) | offerLast(e), offer(e) | Queue |
| Add at head | addFirst(e), push(e) | offerFirst(e) | Stack |
| Remove from head | removeFirst(), remove(), pop() | pollFirst(), poll() | Queue and stack |
| Read head | getFirst(), element() | peekFirst(), peek() | Queue and stack |
| Remove from tail | removeLast() | pollLast() | Deque |
Queue<String> printJobs = new LinkedList<>();
printJobs.offer("report.pdf");
printJobs.offer("invoice.pdf");
String printing = printJobs.poll(); // "report.pdf", first in, first out
String waiting = printJobs.peek(); // "invoice.pdf", still queued
Deque<String> stack = new LinkedList<>();
stack.push("page1");
stack.push("page2");
String top = stack.pop(); // "page2", last in, first out
String empty = new LinkedList<String>().pop(); // NoSuchElementExceptionAn editor’s undo history is a typical case for both ends. Each action goes on top of the stack, undo takes the latest action, and the oldest action falls off the bottom once the history reaches its limit.
static void record(LinkedList<String> history, String action, int limit) {
history.push(action);
if (history.size() > limit) {
history.removeLast();
}
}LinkedList<String> history = new LinkedList<>();
for (String action : List.of("type a", "type b", "bold", "delete")) {
record(history, action, 3);
}
String undone = history.pop(); // "delete"
List<String> stillUndoable = history; // [bold, type b]For queues and stacks that never need index access or null elements, ArrayDeque is likely to be faster than LinkedList, because it stores elements in one array instead of one node object per element. The ArrayDeque and Queue interface articles show both in action.
4. Sequenced Methods From Java 21
Java 21 introduced sequenced collections. The LinkedList class already had getFirst(), getLast(), addFirst() and the other end methods from Deque, so the visible addition is reversed(). It returns a LinkedList view in reverse order, not a copy.
LinkedList<Integer> versions = new LinkedList<>(List.of(17, 21, 25));
LinkedList<Integer> newestFirst = versions.reversed(); // [25, 21, 17]
newestFirst.addFirst(26); // adds at the tail of versions
List<Integer> current = versions; // [17, 21, 25, 26]
Integer latest = versions.getLast(); // 26The bigger gain is that List, Deque and LinkedHashSet share the SequencedCollection interface since Java 21. A method that only needs the first and last element can accept any of them, and before Java 21 that needed separate overloads.
static <E> String ends(SequencedCollection<E> items) {
return items.getFirst() + ".." + items.getLast();
}String fromList = ends(new LinkedList<>(List.of("a", "b", "c"))); // "a..c"
String fromSet = ends(new LinkedHashSet<>(List.of("x", "y"))); // "x..y"5. Time Complexity of LinkedList Operations
The common claim that “LinkedList is faster for inserts and deletes” is only true at the ends or through an iterator. An insert at an index first has to find the node, and that walk costs O(n), the same order as the shifting in an ArrayList.
| Operation | LinkedList | ArrayList |
|---|---|---|
| add(e) at the end | O(1) | O(1) amortized |
| addFirst(e) / removeFirst() | O(1) | O(n), shifts all elements |
| get(i) / set(i, e) | O(n), walks from the nearer end | O(1) |
| add(i, e) / remove(i) | O(n) to find the node, O(1) to link | O(n) to shift |
| ListIterator.add() / remove() | O(1) | O(n) |
| contains(e) / indexOf(e) | O(n) | O(n) |
| Memory per element | Node with three references | One array slot |
A loop that calls get(i) on a LinkedList is O(n squared), so we always iterate a linked list with a for-each loop, an iterator or a stream. Beyond the big-O, an ArrayList is often faster even for middle inserts in lists of moderate size, because copying a contiguous array is cheap for the CPU while following node references causes cache misses.
In practice, ArrayList is the default list in Java, and LinkedList fits a narrow set of cases. The LinkedList vs ArrayList article compares the two in detail, and the ArrayList guide covers the default choice.
6. Thread Safety and Concurrent Alternatives
A LinkedList is not synchronized, and its iterators are fail-fast, so a change from another thread during iteration can throw ConcurrentModificationException or corrupt the links. The right replacement depends on how the threads use the list.
- For a shared list with low contention, Collections.synchronizedList(new LinkedList<>()) wraps every call in a lock, and iteration still needs a manual synchronized block.
- For a non-blocking queue or deque, ConcurrentLinkedDeque is a lock-free linked structure with the same Deque methods.
- For producer and consumer threads that must wait for elements, LinkedBlockingDeque or LinkedBlockingQueue add blocking put() and take() methods.
7. LinkedList FAQs
Developers who use the class search for these questions most often.
7.1. Is Java LinkedList singly or doubly linked?
Doubly linked. Each node has a prev and a next reference, and the list keeps references to both the first and the last node. That is why removeLast() and descendingIterator() run as fast as their counterparts at the head.
7.2. When should I use LinkedList instead of ArrayList?
We use LinkedList when most operations happen at both ends, or when we insert and remove through a ListIterator while walking the list. For indexed access and general storage, we use ArrayList, and for a plain queue or stack without null, ArrayDeque.
7.3. How do I reverse a LinkedList?
On Java 21 and later, reversed() returns a reverse-ordered view without copying. To reverse the list itself, we call Collections.reverse(), which swaps elements in O(n).
LinkedList<String> letters = new LinkedList<>(List.of("a", "b", "c"));
Collections.reverse(letters);
List<String> flipped = letters; // [c, b, a]7.4. Can a LinkedList contain null?
Yes, any number of null elements. Because of that, a null result from poll() or peek() is ambiguous, which is one more reason to prefer ArrayDeque, which rejects null, for queues.
8. Conclusion
The LinkedList class is a doubly linked list that implements List and Deque. It adds and removes at both ends in O(1) and inserts through a ListIterator in O(1), but every index-based call walks the nodes in O(n).
Java 21 gave it reversed() and the shared SequencedCollection type. We use it for undo histories and lists that change while we iterate them, and we pick ArrayList or ArrayDeque for everything else. The Java Collections guide shows where each of them fits.
9. References
Happy Learning !!
I was googling around for content about Linkedlist in java this morning when I came across your excellent article! Thanks a lot Lokesh Gupta!