Complexity of insertion into a linked list, single vs double

Question

At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says:

In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n).

And:

In a doubly-linked list, the time complexity for inserting and deleting an element is O(1).

Is this not a mistake? Why would the complexity for a singly-linked list be so different from that of a doubly-linked list (specifically for insertion)? Am I missing something?

Apologies if this sounds like a naive question, but I'm learning algorithm/data structures, and sometimes complexity is very confusingly explained.

Answer 1

Consider a list and let $e,f,g$ be three consecutive elements. Each element stores a value and has a "forward" pointer to the next element. Additionally, if the list is doubly linked each element also has a "backward" pointer to the previous element.

Consider a singly linked list first. If you want to delete element $f$, then you need to update the pointer of element $e$ (that previously pointed to $f$) to point to $g$. Since you don't know who $e$ is, you have to find it by using an exhaustive search from the beginning of the list. This requires time $\Theta(n)$ in the worst case. Notice that the above discussion holds even if you have a reference to $f$.

Inserting an element in a singly linked list given a reference to the element immediately preceding it can be done in time $O(1)$ (technically, saying that an insertion requires $O(n)$ time is not incorrect since $O(1) \subset O(n)$).

Let's now consider a doubly-linked list. Suppose that you want to delete $f$ and that you have a reference to it. Then you can find $e$ and $g$ in time $O(1)$ by simply following the forward and backward pointers of $f$. To perform the deletion you can update the forward pointer of $e$ to point to $g$ and the backward pointer of $g$ to point to $e$. This can also be done in constant time.

Inserting an element in a doubly linked list given a reference to the element immediately preceding or following it can be done in constant time.

Answer 2

"""In a doubly-linked list, the time complexity for inserting and deleting an element is O(1)."""

The above statement is not correct for all cases. I have explained it below.

I am assuming that you don't want a sorted linked list.

Then, inserting an element in both singly linked list and doubly linked list is O(1) if you insert at the head of the list.

Psuedocode is as follows (for singly linked list):

old_head = head;
head = new_element;
new_element->next = old_head;

For deletion in both singly linked list and doubly linked list, you will have to search the lists for the element that you want to delete. The time complexity of searching the element in both the lists in O(n). So, deletion in doubly linked list also requires O(n) time.

However, if you have a pointer to the element to be deleted then for doubly linked list, the time complexity is O(1) because you can directly update the previous pointer of the next element and the next pointer of the previous element and then free the desired element.

For deletion in a singly linked list (if you have a pointer to the element to be deleted), you will have to find the previous element (for updating the pointers correctly) by going through the list and hence the time complexity of deletion in a singly linked list, in this case, is O(n).

Answer 3

It depends on exactly what you try to do.

Inserting at the start of the list or deleting the first item is O(1). The same if you are given a pointer to one element of the list and want to insert after that item or delete the next item.

Inserting at the end of the list or before a given item, or deleting the last item or an item given by a pointer is O(n) with a single linked list and constant time otherwise. That’s because the operation requires you to find the item before a given item and with a single linked list you need to search starting at the beginning of the list.

And any operation that requires searching the list obviously takes O(n) time.