LinkedList in Java – Complete Guide with Examples
LinkedList is a list in which every element is stored in its own small object, called a node, and each node points to the node before it and the node after it. It lives in the java.util package, has been part of the Collections Framework since JDK 1.2, and implements both the List and Deque interfaces.
Because of that double role, one class can act as a normal list, a queue, a stack or a double-ended queue. In this tutorial you will learn how LinkedList works, how to use its methods, and, just as important, when you should not use it.
1. What Is a LinkedList?
Picture a train. Each coach carries passengers (the data) and is coupled to the coach in front and the coach behind. To add a coach in the middle, you only uncouple two coaches and couple in the new one; nothing else moves. But to reach coach 40, you have to walk through coaches 1 to 39.
A LinkedList works the same way:
- Doubly linked: each node holds the element, a link to the previous node and a link to the next node.
- Head and tail: the list remembers its first and last node, so adding or removing at either end is instant.
- Ordered: it keeps insertion order and gives each element an index.
- Duplicates and
nullallowed, just like ArrayList. - No capacity: it never needs to resize; it creates one node per element.
- Not synchronized: it is not thread-safe.
2. Class Hierarchy and Declaration
LinkedList extends AbstractSequentialList and implements List, Deque, Cloneable and Serializable. Notice that it does not implement RandomAccess, which is the hint that reading by index is slow.
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable3. Your First LinkedList Program
This small playlist shows the methods that make LinkedList special: addFirst(), addLast(), getFirst() and getLast().
import java.util.LinkedList;
public class LinkedListQuickStart {
public static void main(String[] args) {
LinkedList<String> playlist = new LinkedList<>();
playlist.add("Song B"); // add at the end
playlist.addFirst("Song A"); // add at the beginning
playlist.addLast("Song C"); // add at the end
System.out.println("Playlist: " + playlist);
System.out.println("First: " + playlist.getFirst());
System.out.println("Last: " + playlist.getLast());
System.out.println("Size: " + playlist.size());
}
}Playlist: [Song A, Song B, Song C] First: Song A Last: Song C Size: 3
4. Constructors
| Constructor | What it does |
|---|---|
LinkedList() | Creates an empty list. |
LinkedList(Collection<? extends E> c) | Creates a list containing the elements of another collection, in its iteration order. |
There is no constructor that takes a capacity, because a linked list has no internal array to size.
5. Adding, Reading and Updating Elements
LinkedList supports every List method, plus extra methods for the two ends of the list.
import java.util.LinkedList;
import java.util.List;
public class LinkedListAddGet {
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>(List.of(20, 30));
numbers.addFirst(10); // [10, 20, 30]
numbers.addLast(50); // [10, 20, 30, 50]
numbers.add(3, 40); // insert at index 3
numbers.addAll(List.of(60, 70)); // add a collection at the end
System.out.println("List: " + numbers);
System.out.println("get(2): " + numbers.get(2));
System.out.println("getFirst(): " + numbers.getFirst());
System.out.println("getLast(): " + numbers.getLast());
System.out.println("indexOf(40): " + numbers.indexOf(40));
System.out.println("contains(99): " + numbers.contains(99));
numbers.set(0, 5); // replace the first element
System.out.println("After set: " + numbers);
}
}List: [10, 20, 30, 40, 50, 60, 70] get(2): 30 getFirst(): 10 getLast(): 70 indexOf(40): 3 contains(99): false After set: [5, 20, 30, 40, 50, 60, 70]
get(2) works, but it is not instant. The list walks node by node from whichever end is closer (the head or the tail) until it reaches index 2.6. Removing Elements
Besides remove(index) and remove(Object), LinkedList can remove from either end and can remove the last occurrence of a value.
import java.util.LinkedList;
import java.util.List;
public class LinkedListRemove {
public static void main(String[] args) {
LinkedList<String> tasks = new LinkedList<>(
List.of("Login", "Search", "Cart", "Search", "Pay", "Logout"));
System.out.println("Start: " + tasks);
tasks.removeFirst();
System.out.println("removeFirst(): " + tasks);
tasks.removeLast();
System.out.println("removeLast(): " + tasks);
tasks.remove(1); // by index
System.out.println("remove(1): " + tasks);
tasks.removeLastOccurrence("Search");
System.out.println("removeLastOccurrence(): " + tasks);
tasks.removeIf(t -> t.startsWith("P"));
System.out.println("removeIf(P*): " + tasks);
}
}Start: [Login, Search, Cart, Search, Pay, Logout] removeFirst(): [Search, Cart, Search, Pay, Logout] removeLast(): [Search, Cart, Search, Pay] remove(1): [Search, Search, Pay] removeLastOccurrence(): [Search, Pay] removeIf(P*): [Search]
removeFirst() and removeLast() throw NoSuchElementException on an empty list. Their safe versions, pollFirst() and pollLast(), return null instead.
7. Using LinkedList as a Queue
A queue serves elements in the order they arrive: first in, first out (FIFO), like people waiting at a ticket counter. LinkedList implements Queue, so you can use offer() to join the queue, peek() to look at the front, and poll() to take the front element.
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListAsQueue {
public static void main(String[] args) {
// Queue: first in, first out (FIFO)
Queue<String> printQueue = new LinkedList<>();
printQueue.offer("report.pdf");
printQueue.offer("photo.png");
printQueue.offer("notes.txt");
System.out.println("Next job (peek): " + printQueue.peek());
while (!printQueue.isEmpty()) {
System.out.println("Printing " + printQueue.poll());
}
System.out.println("poll() on empty queue: " + printQueue.poll());
}
}Next job (peek): report.pdf Printing report.pdf Printing photo.png Printing notes.txt poll() on empty queue: null
8. Using LinkedList as a Stack and Deque
A stack is last in, first out (LIFO), like the browser's Back button. push() adds to the front and pop() removes from the front. Because LinkedList is a Deque (double-ended queue), it can also add and remove at both ends.
import java.util.Deque;
import java.util.LinkedList;
public class LinkedListAsStack {
public static void main(String[] args) {
// Stack: last in, first out (LIFO)
Deque<String> history = new LinkedList<>();
history.push("home");
history.push("products");
history.push("product/42");
System.out.println("History: " + history);
System.out.println("Back from " + history.pop());
System.out.println("Now on " + history.peek());
// Deque: add and remove at both ends
Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(2);
deque.offerFirst(1);
deque.offerLast(3);
System.out.println("Deque: " + deque);
System.out.println("pollLast(): " + deque.pollLast() + ", pollFirst(): " + deque.pollFirst());
}
}History: [product/42, products, home] Back from product/42 Now on products Deque: [1, 2, 3] pollLast(): 3, pollFirst(): 1
ArrayDeque is usually faster than LinkedList because it stores elements in an array and creates no node objects. Use LinkedList when you also need null elements or List methods such as get(index).9. Iterating Forward and Backward
Because each node links to the previous one, LinkedList can walk backwards just as easily as forwards. A ListIterator can also insert or remove at its current position in constant time, which is where LinkedList really shines.
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
public class LinkedListIterate {
public static void main(String[] args) {
LinkedList<String> stops = new LinkedList<>(List.of("A", "B", "C", "D"));
// Forward with for-each
for (String s : stops) System.out.print(s + " ");
System.out.println();
// Backward with descendingIterator()
Iterator<String> back = stops.descendingIterator();
while (back.hasNext()) System.out.print(back.next() + " ");
System.out.println();
// Insert while looping with ListIterator: O(1) per insert
ListIterator<String> it = stops.listIterator();
while (it.hasNext()) {
if (it.next().equals("B")) {
it.add("B2"); // inserted right after B
}
}
System.out.println("After insert: " + stops);
}
}A B C D D C B A After insert: [A, B, B2, C, D]
10. Common LinkedList Methods
Many methods come in pairs: one throws an exception when the list is empty, the other returns a special value (null or false).
| Purpose | Throws exception | Returns null/false |
|---|---|---|
| Add at the front | addFirst(e), push(e) | offerFirst(e) |
| Add at the end | addLast(e), add(e) | offerLast(e), offer(e) |
| Remove from the front | removeFirst(), remove(), pop() | pollFirst(), poll() |
| Remove from the end | removeLast() | pollLast() |
| Read the front | getFirst(), element() | peekFirst(), peek() |
| Read the end | getLast() | peekLast() |
Other useful methods:
| Method | Description |
|---|---|
add(int index, E e) | Inserts at a position. |
get(int index), set(int index, E e) | Read or replace by index (walks the list). |
remove(int index), remove(Object o) | Remove by position or by value. |
removeFirstOccurrence(o), removeLastOccurrence(o) | Remove the first or last matching value. |
indexOf(o), lastIndexOf(o), contains(o) | Search for a value. |
descendingIterator() | Iterates from the last element to the first. |
listIterator(int index) | Iterator that can move both ways and add, set or remove. |
size(), isEmpty(), clear() | Count, check and empty the list. |
reversed() (Java 21+) | Returns a reversed view of the list. |
11. How LinkedList Works Internally
Inside the JDK, each element is wrapped in a private Node class:
private static class Node<E> {
E item; // the element
Node<E> next; // the node after this one
Node<E> prev; // the node before this one
}The list itself keeps three fields: first (the head), last (the tail) and size.
- Adding at the end: create a node, point the old tail's
nextat it, and make it the new tail. No copying. - Adding at the front: the same at the head.
- Inserting in the middle: first walk to the position (slow), then change four links (fast).
- Reading by index: walk from the head if the index is in the first half, otherwise from the tail. In the worst case that is
size / 2steps.
Each node costs extra memory for the two links and the object header, so a LinkedList uses several times more memory than an ArrayList with the same elements.
12. Time Complexity
| Operation | LinkedList | ArrayList |
|---|---|---|
| Add or remove at the front | O(1) | O(n) |
| Add or remove at the end | O(1) | O(1) amortized |
get(i), set(i, e) | O(n) | O(1) |
Insert or remove at index i | O(n) to find + O(1) to link | O(n) to shift |
Insert or remove with a ListIterator | O(1) | O(n) |
contains(e), indexOf(e) | O(n) | O(n) |
The biggest trap is looping with an index. Each get(i) walks the list again, so the loop below is O(n²) for a LinkedList:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class IndexLoopCost {
static long sumByIndex(List<Integer> list) {
long sum = 0;
for (int i = 0; i < list.size(); i++) {
sum += list.get(i); // O(1) for ArrayList, O(n) for LinkedList
}
return sum;
}
public static void main(String[] args) {
List<Integer> array = new ArrayList<>();
List<Integer> linked = new LinkedList<>();
for (int i = 0; i < 50_000; i++) { array.add(i); linked.add(i); }
long t1 = System.nanoTime();
sumByIndex(array);
long t2 = System.nanoTime();
sumByIndex(linked);
long t3 = System.nanoTime();
long arrayMs = (t2 - t1) / 1_000_000, linkedMs = (t3 - t2) / 1_000_000;
System.out.println("LinkedList much slower with get(i)? " + (linkedMs > arrayMs * 5));
}
}LinkedList much slower with get(i)? true
Use a for-each loop or an iterator instead, which visits each node exactly once.
13. LinkedList vs ArrayList
| Feature | LinkedList | ArrayList |
|---|---|---|
| Internal structure | Doubly linked nodes | Resizable array |
| Implements | List, Deque | List, RandomAccess |
| Access by index | Slow, O(n) | Fast, O(1) |
| Add or remove at the front | Fast, O(1) | Slow, O(n) |
| Memory per element | High (node + two links) | Low |
| CPU cache friendliness | Poor (nodes are scattered) | Good (contiguous array) |
| Can be a queue or stack | Yes | No |
In practice: ArrayList wins for most programs, even ones that insert now and then, because walking to the insert position in a LinkedList is slow. Choose LinkedList when you add and remove mainly at the ends and need List methods, or when you insert and remove through a ListIterator while walking the list.
14. LinkedList and Thread Safety
LinkedList is not synchronized. For a shared list, wrap it with Collections.synchronizedList(new LinkedList<>()). For a shared queue, use a class built for concurrency instead, such as ConcurrentLinkedQueue, ConcurrentLinkedDeque or LinkedBlockingQueue (which also lets consumers wait for new elements).
15. Common Mistakes
| Mistake | Problem | Better |
|---|---|---|
Looping with get(i) | O(n²) running time | Use for-each or an iterator. |
| Choosing LinkedList "because inserts are fast" | Finding the position is still O(n) | Measure; ArrayList is usually faster. |
Calling getFirst() or pop() on an empty list | NoSuchElementException | Check isEmpty() or use peekFirst()/pollFirst(). |
| Using LinkedList as a simple stack or queue | Extra memory and garbage | Use ArrayDeque. |
Declaring the variable as List and then needing addFirst() | Method not visible | Declare it as Deque or LinkedList. |
16. Summary
- LinkedList is a doubly linked list that implements both
ListandDeque. - Adding and removing at either end is O(1); reading or writing by index is O(n).
- It can be used as a list, queue, stack or deque.
- It uses more memory than ArrayList and is slower for most everyday tasks.
- Avoid index-based loops; use for-each,
IteratororListIterator. - For pure stacks and queues, prefer
ArrayDeque.
Related Tutorials
Reference: Java SE 21 API: java.util.LinkedList
Frequently Asked Questions (FAQ)
Q1. What is a LinkedList in Java?
LinkedList is a class in java.util that stores elements as a chain of nodes, where each node links to the previous and next node. It implements List and Deque, keeps insertion order, and allows duplicates and null.
Q2. Is Java's LinkedList singly or doubly linked?
Doubly linked. Every node has a link to the next node and to the previous node, which is why the list can be walked in both directions and why removing a node never requires searching for its predecessor.
Q3. When should I use LinkedList instead of ArrayList?
Use LinkedList when most of your operations are adding or removing at the beginning or end of the list, or inserting and removing through a ListIterator while you walk it. For reading by index, looping and general use, ArrayList is faster and uses less memory.
Q4. Why is get(index) slow on a LinkedList?
Nodes are not stored in an array, so there is no way to jump straight to a position. get(i) starts at the head or the tail (whichever is closer) and follows links one by one, which takes O(n) time.
Q5. Does LinkedList have a default capacity?
No. Capacity is an array concept. A LinkedList creates one node for each element, so it never needs to grow or shrink an internal array, and it has no ensureCapacity() or trimToSize() methods.
Q6. Can a LinkedList contain null and duplicate elements?
Yes, both. Be careful when using it as a queue: poll() and peek() return null when the list is empty, so a stored null would look the same as "no element". Queue-only classes such as ArrayDeque forbid null for this reason.
Q7. What is the difference between add(), addLast() and offer()?
All three add an element at the end. add() comes from List/Collection and returns true; addLast() comes from Deque and returns nothing; offer() comes from Queue and returns true. For a LinkedList they behave the same, because it has no size limit. Choose the one that matches how you are using the list.
Q8. What is the difference between poll(), remove() and pop()?
All three remove and return the first element. On an empty list, poll() returns null, while remove() and pop() throw NoSuchElementException. Note that remove(int) and remove(Object) are different methods that remove by index or by value.
Q9. What is the difference between peek(), element() and getFirst()?
They all return the first element without removing it. peek() returns null if the list is empty; element() and getFirst() throw NoSuchElementException.
Q10. How do I use a LinkedList as a stack?
Declare it as a Deque and use push(), pop() and peek():
Deque<Integer> stack = new LinkedList<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2Avoid the legacy Stack class, which is synchronized and extends Vector. ArrayDeque is usually the fastest choice.
Q11. Is LinkedList thread-safe?
No. Use Collections.synchronizedList(new LinkedList<>()) for a shared list, or a concurrent class such as ConcurrentLinkedDeque or LinkedBlockingQueue for a shared queue.
Q12. Why does LinkedList use more memory than ArrayList?
Each element lives in a separate node object that also stores two references (previous and next) and an object header. On a typical 64-bit JVM that is around 24 bytes per node in addition to the element itself, while ArrayList needs only one reference per element in its array.
Q13. How do I iterate over a LinkedList in reverse?
Use descendingIterator(), a ListIterator started at the end, or, from Java 21, the reversed() view:
Iterator<String> it = list.descendingIterator();
while (it.hasNext()) System.out.println(it.next());
for (String s : list.reversed()) System.out.println(s); // Java 21+Q14. Does LinkedList implement RandomAccess?
No. RandomAccess is a marker interface for lists with fast index access, such as ArrayList. Generic algorithms check for it with instanceof RandomAccess and switch to iterator-based loops when a list does not implement it.
Q15. How do I remove elements from a LinkedList while iterating?
Use removeIf() or the iterator's own remove(). Removing with list.remove() inside a for-each loop throws ConcurrentModificationException.
list.removeIf(s -> s.isBlank());Q16. Is insertion in the middle of a LinkedList really O(1)?
Only the linking step is O(1). To insert at index i, the list must first walk to that position, which is O(n). Insertion is truly O(1) only when you already have an iterator at the right place, for example with ListIterator.add().
Q17. What is the difference between LinkedList and ArrayDeque?
Both implement Deque. ArrayDeque uses a circular array, so it is faster and lighter for stack and queue operations, but it does not allow null and does not implement List. LinkedList allows null and offers index-based List methods.
Q18. How do I convert a LinkedList to an ArrayList or an array?
List<String> arrayList = new ArrayList<>(linkedList);
String[] array = linkedList.toArray(new String[0]);Q19. Can I sort a LinkedList?
Yes, with list.sort(comparator) or Collections.sort(list). Internally the elements are copied into an array, sorted, and written back, so sorting a LinkedList is as fast as sorting an ArrayList (O(n log n)).
Q20. Which interfaces does LinkedList implement?
List, Deque (and therefore Queue), Cloneable and Serializable. From Java 21 it also implements SequencedCollection through List and Deque.