0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What is an insertion? Insertion at the beginning of the list? At the end? At a given position? In a sorted list, keeping the whole thing sorted? (Same kind of question about deletion). Your link is very vague about the description of the operation implemented, so it is difficult to answer properly. $\endgroup$
    – Nathaniel
    Nov 30, 2021 at 15:11
  • $\begingroup$ @Nathaniel Yes the description is vague, but in the absence of any further information, I think we can assume it's taking about insertion in the general sense (i.e., at a given position), and also that the linked list in not sorted. $\endgroup$
    – prmph
    Nov 30, 2021 at 15:14
  • $\begingroup$ (Please do not comment comments asking for additional information or clarification: Prefer editing your question.) at a given position Given how? Insert as $k_{th}$ element? Insert before/after element $e$? in the latter case, the existence of aliases for $e$ may make a difference. $\endgroup$
    – greybeard
    Nov 30, 2021 at 16:04

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ OK, @Steven, good explanation for deletion, but what about insertion? $\endgroup$
    – prmph
    Nov 30, 2021 at 15:22
  • $\begingroup$ If you have you want to insert an element $f$ just after an element $e$ and you have a reference to $e$, then this can be done in constant time for both single- and doubly-linked lists (the same applies for inserting at the beginning of the list). Additionally, in double linked lists you can also insert $f$ just before $g$ in constant time if you have a reference to $g$. $\endgroup$
    – Steven
    Nov 30, 2021 at 15:39
1
$\begingroup$

"""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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.