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?
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).
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.
You missed the interface at two places:
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.
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.
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).
That's two operations, you first search O(n) the list for given position, then insert O(1) element into the list.
In a single linked list, the operation of insertion consists of:
alternating pointer of previous element
wrapping object into data structure and setting its pointer to next element
Both are invariant to list size.
On the other hand, take for example a heap structure. Insertion of each element requires O(log(n)) operations for it to retain its structure. Tree structures have similar mechanisms that will be run upon insertion and depend on current tree size.
Here it is considered that you already have the node after which you need to add a new element.
In that case for a singly-linked-list insertion time complexity becomes O(1).
The fact is that, unlike an array, we don’t need to shift the elements of a singly-linked list while doing an insertion. Therefore, the insertion time complexity of a singly-linked list is O(1).
Imagine that you have a Python list filled with integer numbers...
my_list = [9, 8, 4, 5, 6]
... and you want to insert the number 3 right after the element 8.
my_list.insert(2, 3)
The printed result will be:
[9, 8, 3, 4, 5, 6]
When you do an insertion to my_list, the other elements after the element 3 are all shifted towards the right, so their indexes are changed. As a result, the time complexity to insert an element at a given index is O(n).
However, in singly-linked lists, there are no array elements, but chained nodes and node values.
Image source: LeetCode
As the above image shows, the prev node holds the reference of the next node. As @πάντα ῥεῖ stated, "function signatures already take the predecessor node as argument". You can find the previous node in O(n) time, but while inserting a new node, you just need to change the addresses of connected nodes and that is O(1) time complexity.
