Question

What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?

(a) O(1)

(b) O(n)

(c) O(n^2)

(d) O(n^3)

The doubt is from Singly Linked List Operations in chapter Abstract Data Types of Data Structures & Algorithms I

I have been asked this question during an online interview.

Answer 1

The correct option is (a) O(1)

To explain: To add an element at the front of the linked list, we will create a new node which holds the data to be added to the linked list and pointer which points to head position in the linked list. The entire thing happens within O (1) time. Thus the asymptotic time complexity is O (1).