Java LinkedList
Learn about Java LinkedList. Understand how it differs from ArrayList, when to use it, and its special methods for manipulating the beginning and end of the list.
The LinkedList class is almost identical to ArrayList in how you use it, but it works differently internally.
Think of a Treasure Hunt Chain 🔗.
- ArrayList: A row of numbered lockers. You can go directly to Locker #5.
- LinkedList: A series of clues. Clue #1 points to Clue #2, which points to Clue #3. To get to Clue #5, you MUST visit 1, 2, 3, and 4 first.
ArrayList vs LinkedList
| Feature | ArrayList | LinkedList |
|---|---|---|
| Internal Structure | Dynamic Array | Doubly Linked List |
| Accessing Items | Fast (Direct access) | Slow (Must travel the chain) |
| Adding/Removing | Slow (Must shift elements) | Fast (Just change the pointers) |
| Memory | Less memory | More memory (Stores pointers) |
Time Complexity (Big O)
| Operation | ArrayList | LinkedList |
|---|---|---|
| Access (get) | O(1) | O(n) |
| Insert (add) | O(1)* | O(1) |
| Insert (middle) | O(n) | O(1)** |
| Remove | O(n) | O(1)** |
*Amortized O(1), O(n) when resizing. **O(1) if you have the iterator/pointer, otherwise O(n) to find the node.
When to use which?
- Use ArrayList when you want to access random items frequently.
- Use LinkedList when you want to add/remove items from the middle frequently.
Creating a LinkedList
import java.util.LinkedList;
LinkedList<String> cars = new LinkedList<String>();Special Methods
LinkedList has extra methods because it implements the Deque interface too.
addFirst()addLast()removeFirst()removeLast()getFirst()getLast()
LinkedList<String> cars = new LinkedList<String>();
cars.add("Volvo");
cars.add("BMW");
cars.addFirst("Ford"); // Adds to the beginning
System.out.println(cars); // [Ford, Volvo, BMW]Tip 💡: If you are building a Queue (First In, First Out) or a Stack (Last In, First Out), LinkedList is your best friend!
Which list is faster for adding items at the beginning?
Note : Java is a statically-typed language. It means that all variables must be declared before they can be used.
Challenge
Complete this chapter to unlock the next one.
Challenge
Task:
Create a LinkedList of Strings. Add 'A', then add 'B' to the first position. Print the first element.