What is the complexity of inserting an element into a LinkedList?

O(1).

Inserting an element into a LinkedList at a specific index requires iterating from the beginning or end of the list (whichever is closer to the index) to the desired position, which has a complexity of O(n). However, if we have a reference to the node before the insertion point (for example, when inserting at the beginning or end), the operation takes O(1).

// Inserting at the beginning
LinkedList<String> list = new LinkedList<>();
list.addFirst("element"); // O(1)

// Inserting at the end
list.addLast("another element"); // O(1)

// Inserting at an index (requires node search)
list.add(1, "middle"); // O(n) in the worst case, O(1) for 0 or size()