Time Complexity in singly link list

Question

I am studying data-structure: singly link list.

The website says singly linked list has a insertion and deletion time complexity of O(1). Am I missing something?

website link

I do this in C++, and I only have a root pointer. If I want to insert at the end, then I have to travel all the way to the back, which means O(n).

Answer 1

The explanation for this is, that the big O notation in the linked table refers to the function implementation itself, not including the list traversal to find the previous reference node in the list.

If you follow the link to the wikipedia article of the Singly-LinkedList implementation it becomes more clear:

function insertAfter(Node node, Node newNode)
function removeAfter(Node node)     

The above function signatures already take the predecessor node as argument (same for the other variants implicitly).

Finding the predecessor is a different operation and may be O(n) or other time complexity.

Answer 2

You missed the interface at two places:

1. std::list::insert()/std:list::erase() need an iterator to the element where to insert or erase. This means you have no search but only alter two pointers in elements in the list, which is constant complexity.

2. Inserting at the end of a list can be done via push_back. The standard requires this to be also O(1). Which means, if you have a std::list, it will store first and last element.

EDIT: Sorry, you meet std::forward_list. Point 1 holds also for this even if the names are insert_after and erase_after. Points 2 not, you have to iterate to the end of the list.