Java.Collections.What is the worst case running time of the add() method for a LinkedList?

Let’s explore the worst-case running time of the add() method in a LinkedList—and clarify which version of add() we mean:

---

🚨 Important: Which add()?

1. add(element) — appends to the end.
2. add(index, element) — inserts at a specific index.

Let’s go through both.

---

✅ add(element) — Add to the end

• Time complexity (worst case): O(1)
• LinkedList maintains a reference to the tail, so appending at the end is fast.

No traversal needed, and it creates and links a new node right at the end.

---

⚠️ add(index, element) — Insert at specific index

• Worst-case time complexity: O(n)
• Because LinkedList is not index-based, it must traverse the list from the head (or tail) to find the correct position.
• After finding the node, inserting itself is O(1).

So the cost is in finding the node, not in inserting it.

---

🧪 Examples:

LinkedList<String> list = new LinkedList<>();

// Worst case for add(index, element)
list.add(0, "a");      // O(1) — front
list.add(1000, "z");   // O(n) — if list has to traverse to the 1000th position

🧠 Summary:

Operation	Worst-case Time
add(element)	✅ O(1)
add(index, element)	❌ O(n)