Consider a singly linked list with only a pointer to the first node in the list
ID: 670391 • Letter: C
Question
Consider a singly linked list with only a pointer to the first node in the list (i.e. there is no length field or pointer to the last node in the list). Express the worst-case asymptotic time complexity, using big-O notation, of efficient implementations of the following operations. Make your bounds as tight as possible append (1st, x) - creates a new node with the value x and adds it to the end of list 1st. prepend (1st, x) - creates a new node with the value x and adds it to the beginning of list 1st. contains (1st, x) - returns true if a node in the list 1st contains a value equal to x, and false otherwise. removeFirst (1st) - removes the first node in the list 1st. removeLast (1st) - removes the last node in the list 1st. remove (1st, p) - removes the node pointed to by p from the list 1st. length (1st) - returns the length of the list 1st.Explanation / Answer
a. O(n)
b. O(1)
c O(n)
d O(1)
e O(n)
f O(n)
g O(n)