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.

Improve this question
$\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

1 Answer 1

Reset to default
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.

Improve this answer
$\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

Your Answer

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

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