What is the time complexity of search and insert operations in a linked list?

For a linked list:

• Searching for an element: usually requires traversing the list from the beginning to the desired element, so the time complexity is O(n), where n is the number of elements.

• Inserting an element:

  • If the insertion occurs at the beginning of the list (with a pointer to the head), the operation is performed in O(1).
  • If inserting at an arbitrary position, you first need to find the position — this is O(n), then the insertion itself is O(1).

Thus, inserting at the beginning or after a known node is fast, while searching and inserting at an arbitrary position require linear time.