Given a linked list implementation, inserting a new element to the current position takes how long?

\Theta(1) time
  • \Theta(n) time
  • \Theta(\log n) time
  • \Theta(n \log n) time

Normally, the bottleneck in a linked list is getting to the proper position.

If we are already at the postion where we want to insert, then putting the new node in place takes only a couple of assignments.