LinkedList
When working with Java collections, it is tempting to think that every List implementation behaves the same way internally. They do not. LinkedList and ArrayList both implement the List interface, but their internal data structures are fundamentally different.
LinkedList stores elements as a sequence of linked nodes. Each node keeps the element and references that connect it to neighboring nodes. This structure makes LinkedList particularly useful when operations at the beginning or end of the sequence are important.
Core Idea: ArrayList is backed by a resizable array, while LinkedList is based on linked nodes. Their performance characteristics are therefore different.
Why Does LinkedList Exist?
Imagine a chain of train carriages. Each carriage is connected to the next one, and each carriage knows how it connects to its neighbors. Adding or removing a carriage can be done by changing the connections around it rather than physically shifting every carriage after it.
A linked list follows a similar idea. Instead of storing all elements in one contiguous array-like structure, it connects individual nodes together.
Node A <-> Node B <-> Node C <-> Node D
Each node contains an element and links to neighboring nodes. Java's LinkedList is specifically implemented as a doubly linked list.
Simple analogy: ArrayList is like numbered seats in a theater; LinkedList is like people holding hands in a chain. Reaching a particular person in the chain requires following links from one person to another.
LinkedList Hierarchy
LinkedList is more versatile than ArrayList because it implements both the List and Deque interfaces.
Collection
|
+-- List
| |
| +-- LinkedList
|
+-- Queue
|
+-- Deque
|
+-- LinkedList
This means LinkedList can be used as a List, Queue, or Deque depending on the reference type and the operations your application needs.
Creating a LinkedList
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> names = new LinkedList<>();
names.add("Bibhu");
names.add("Rahul");
names.add("Priya");
System.out.println(names);
}
}
Here, the variable is declared using the List interface. This is generally a good design when the calling code only needs List behavior.
Creating LinkedList as a Deque
Because LinkedList implements Deque, you can also expose it through the Deque interface.
import java.util.Deque;
import java.util.LinkedList;
Deque<String> tasks = new LinkedList<>();
tasks.addFirst("Urgent");
tasks.addLast("Normal");
System.out.println(tasks);
This gives the code a clear statement of intent: the collection is being used as a double-ended queue.
Adding Elements
The normal List add() method appends an element to the end.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
System.out.println(languages);
LinkedList maintains the order in which elements are inserted.
Adding at the Beginning and End
LinkedList provides convenient methods for both ends because it implements Deque.
LinkedList<String> languages = new LinkedList<>();
languages.addLast("Java");
languages.addLast("Python");
languages.addFirst("C#");
System.out.println(languages);
The ability to efficiently work with both ends is one of LinkedList's useful characteristics.
| Method | Purpose |
|---|---|
| addFirst() | Adds an element at the beginning. |
| addLast() | Adds an element at the end. |
| offerFirst() | Offers an element at the beginning. |
| offerLast() | Offers an element at the end. |
Accessing Elements
LinkedList supports the List get(index) method, but it is important to understand that index access is not as efficient as it is in ArrayList.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
System.out.println(languages.get(1));
To reach an index, LinkedList may need to traverse through its nodes. Therefore, index-based access is typically O(n).
Key Difference: ArrayList provides typically O(1) index access. LinkedList typically requires O(n) traversal to reach an arbitrary index.
How LinkedList Finds an Index
LinkedList is a doubly linked list, so it can traverse from either end. For an indexed operation, the implementation can choose the closer end and walk toward the requested position.
Head
|
v
A <-> B <-> C <-> D <-> E
^
|
Tail
If you request an element near the beginning, traversal can start from the head. If the element is closer to the end, traversal can start from the tail.
This improves practical traversal compared with always starting from the first node, but arbitrary index access is still generally O(n).
Updating Elements
LinkedList supports the List set() method.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
languages.set(1, "JavaScript");
System.out.println(languages);
The element at index 1 is replaced. Finding the node at that index is still part of the operation, so unlike ArrayList, this is not generally considered O(1) index access.
Removing Elements
LinkedList supports removal by index, by value, and from either end.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("C#");
languages.add("Python");
languages.removeFirst();
languages.removeLast();
System.out.println(languages);
The first and last elements can be removed directly through the Deque-oriented API.
Queue Operations
LinkedList can also behave as a Queue.
Queue<String> tasks = new LinkedList<>();
tasks.offer("Task 1");
tasks.offer("Task 2");
tasks.offer("Task 3");
System.out.println(tasks.poll());
The Queue reference restricts the visible API to Queue behavior, which makes the intended usage clearer.
Deque Operations
When used as a Deque, LinkedList can add, remove, and inspect elements at both ends.
Deque<String> tasks = new LinkedList<>();
tasks.addFirst("Urgent");
tasks.addLast("Normal");
System.out.println(tasks.peekFirst());
System.out.println(tasks.peekLast());
This is one of the major differences between LinkedList and ArrayList at the interface level: LinkedList can directly provide Deque operations.
LinkedList as a Stack
Because LinkedList implements Deque, it can technically provide stack operations as well.
Deque<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");
stack.push("C");
System.out.println(stack.pop());
However, if your only requirement is stack or deque behavior, ArrayDeque is generally a better default choice.
LinkedList and Duplicate Elements
LinkedList follows the List contract, so duplicate values are allowed.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("Spring");
languages.add("Java");
System.out.println(languages);
Each Java value occupies its own position in the List.
LinkedList and Null Values
LinkedList permits null elements.
LinkedList<String> values = new LinkedList<>();
values.add("Java");
values.add(null);
values.add("Spring");
System.out.println(values);
Whether null is a good design choice is a separate question. Just because a collection permits null does not mean an application should use it everywhere.
LinkedList Performance
LinkedList's performance should be understood in terms of both locating a node and modifying the links between nodes.
| Operation | Typical Complexity | Reason |
|---|---|---|
| get(index) | O(n) | May require traversal to locate the node. |
| set(index, value) | O(n) | Node must generally be located first. |
| addFirst() | O(1) | Updates the front links. |
| addLast() | O(1) | Updates the rear links. |
| removeFirst() | O(1) | Removes the first node directly. |
| removeLast() | O(1) | Removes the last node directly. |
| contains(value) | O(n) | May require scanning nodes. |
| remove(index) | O(n) | Locating the indexed node can require traversal. |
There is an important nuance here: inserting or removing a node at a position is O(1) after the node or its position has already been located. If locating that position requires traversal, the total operation can be O(n).
Interview Insight: Never say "LinkedList insertion is always O(1)." A complete answer must consider the cost of locating the insertion point.
ArrayList vs LinkedList
This is one of the most common Java Collections interview comparisons.
| Feature | ArrayList | LinkedList |
|---|---|---|
| Underlying structure | Resizable array | Doubly linked nodes |
| get(index) | Typically O(1) | Typically O(n) |
| set(index, value) | Typically O(1) | Typically O(n) |
| Add at end | O(1) amortized | Typically O(1) |
| Add at beginning | Typically O(n) | O(1) |
| Remove at beginning | Typically O(n) | O(1) |
| Random access | Excellent | Poor compared with ArrayList |
| Memory overhead | Generally lower | Generally higher |
| Cache locality | Generally better | Generally worse |
| Typical default for List | Yes | Less commonly the default |
Why ArrayList Is Usually Preferred for List Workloads
A common misconception is that LinkedList should be preferred whenever elements are inserted or removed frequently. In practice, that conclusion is often too simplistic.
ArrayList benefits from contiguous array storage, efficient index access, and good CPU cache locality. LinkedList allocates separate node objects and follows references between them, which introduces memory and traversal overhead.
Therefore, even for some workloads involving modifications, ArrayList can perform very well. The correct choice depends on the actual access pattern and workload rather than a single Big-O comparison.
Practical Rule: Start with ArrayList for a normal List use case. Choose LinkedList when its specific linked/deque characteristics actually solve a problem better.
LinkedList vs ArrayDeque
If your requirement is specifically a Queue or Deque rather than a List, the comparison should often be between LinkedList and ArrayDeque.
| Feature | LinkedList | ArrayDeque |
|---|---|---|
| Deque operations | Supported | Supported |
| Underlying structure | Doubly linked nodes | Resizable array |
| Null elements | Allowed | Not allowed |
| Memory overhead | Generally higher | Generally lower |
| Random access | List operations supported but typically O(n) | Not provided as a core Deque operation |
| Typical dedicated Deque choice | Less common | Often preferred |
When Should You Use LinkedList?
LinkedList can be a sensible choice when its characteristics align closely with the problem.
- You need List behavior and also need LinkedList-specific deque operations through the same object.
- Your algorithm naturally manipulates nodes around the ends or already-known positions.
- You need a List implementation that permits null and its other characteristics are appropriate.
- A workload has access patterns where linked-node behavior is genuinely advantageous and has been validated by measurement.
For a dedicated Queue or Deque, however, ArrayDeque is often a better starting point. For a general-purpose List, ArrayList is usually the first implementation to consider.
Using ListIterator with LinkedList
LinkedList supports ListIterator, which provides bidirectional traversal and modification operations.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("Spring");
languages.add("SQL");
ListIterator<String> iterator =
languages.listIterator();
while (iterator.hasNext()) {
String language = iterator.next();
System.out.println(language);
}
A ListIterator can also move backward through the List.
while (iterator.hasPrevious()) {
String language = iterator.previous();
System.out.println(language);
}
The bidirectional behavior is especially natural for a linked structure, although the API is defined by the List contract rather than being exclusive to LinkedList.
Adding and Removing Through ListIterator
ListIterator can insert or remove elements during traversal.
LinkedList<String> languages = new LinkedList<>();
languages.add("Java");
languages.add("Spring");
ListIterator<String> iterator =
languages.listIterator();
while (iterator.hasNext()) {
String language = iterator.next();
if (language.equals("Spring")) {
iterator.set("Spring Boot");
}
}
This allows controlled modifications without directly changing the collection structure through the List reference while the iterator is active.
Common Beginner Mistakes
- Assuming LinkedList is always faster for insertion: You must account for the cost of locating the position.
- Using LinkedList for frequent get(index): Indexed access is typically O(n).
- Choosing LinkedList simply because it is called a linked list: ArrayList often performs better for normal List workloads.
- Ignoring memory overhead: LinkedList stores node objects and links, which generally requires more memory than ArrayList.
- Using LinkedList as a dedicated Deque without comparison: ArrayDeque is often a better fit for dedicated deque operations.
- Assuming LinkedList is thread-safe: It is not inherently synchronized.
- Using raw types: Prefer LinkedList<String> or another generic type.
Best Practices
- Use the List interface when your code requires List behavior rather than LinkedList-specific methods.
- Prefer ArrayList for most general-purpose List workloads unless you have a clear reason to choose LinkedList.
- Consider ArrayDeque for dedicated Queue or Deque requirements.
- Do not use LinkedList for workloads dominated by random index access.
- Consider the cost of locating a node before claiming that an insertion or removal is O(1).
- Use generics for compile-time type safety.
- Use appropriate concurrent collections or synchronization when shared access across threads is required.
Interview Insights
Question: What is LinkedList in Java?
Answer: LinkedList is a doubly linked implementation of both List and Deque. It stores elements in linked nodes and supports List, Queue, and Deque operations.
Question: Why is get(index) slower in LinkedList than ArrayList?
Answer: ArrayList can directly access an array position, while LinkedList generally has to traverse nodes to locate the requested index.
Question: Is insertion in LinkedList always O(1)?
Answer: No. Once the insertion position or node is known, relinking can be O(1), but locating that position can require O(n) traversal.
Question: Which is generally better for a normal List: ArrayList or LinkedList?
Answer: ArrayList is generally the better default because of fast index access, lower memory overhead, and good cache locality. LinkedList should be chosen when its specific characteristics fit the workload.
Question: Can LinkedList be used as a Queue and Deque?
Answer: Yes. LinkedList implements Queue and Deque-related behavior and provides operations for adding, removing, and inspecting elements at both ends.
Quick Revision
| Concept | Key Point |
|---|---|
| LinkedList | Doubly linked implementation of List and Deque. |
| Structure | Stores elements in linked nodes. |
| get(index) | Typically O(n) because the node must be located. |
| addFirst() | Typically O(1). |
| addLast() | Typically O(1). |
| removeFirst() | Typically O(1). |
| removeLast() | Typically O(1). |
| Duplicates | Allowed. |
| Null values | Allowed. |
| Memory | Generally higher overhead than ArrayList because of node objects and links. |
| General List default | Usually ArrayList unless LinkedList's characteristics are specifically useful. |
| Dedicated Deque | ArrayDeque is often a better default choice. |
LinkedList is a valuable class to understand because it demonstrates an important software-engineering lesson: two classes can implement the same interface while having very different internal behavior. Do not choose a collection based only on its name or on a single Big-O claim. Think about access patterns, memory overhead, traversal cost, cache locality, and the actual operations your application performs. In the next chapter, we will explore HashSet and see how Java efficiently manages collections where duplicate elements are not allowed.