🔍 contains() in a LinkedList
What does it do?
list.contains(element) checks whether the list contains a specific element. Internally, it:
- Starts from the head of the linked list.
- Iterates through each node.
- Uses
.equals()to compare each node’s value with the target.
⏱️ Worst-case running time?
✅ Time complexity: O(n)
n= number of elements in the list.- Worst case: the element is at the end or not present at all → the method must check every single node.
Even if the element is present, if it’s near the end, the search still takes almost full traversal.
🧠 Key point:
Unlike ArrayList, LinkedList cannot jump to the middle using indices. It has to walk node by node from the beginning.
🧪 Example:
LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");
list.add("c");
// contains("c") → O(n), because it might need to check all elements
Summary:
| Operation | LinkedList.contains() |
|---|---|
| Best Case | O(1) – if it’s the first element |
| Worst Case | ❌ O(n) – if it’s last or not present |