Temporary complexity of deleting a node in singly and doubly linked lists

Question

Why is the time complexity of deleting a node in doubly linked lists (O (1)) faster than node deleting in a singly linked list (O (n))?

Answer 1

The problem suggests that the node to be deleted is known and a pointer to the node is available.

To remove a node and join the previous and next node together, you need to know their pointers. In a doubly linked list, both pointers are available in the node to be removed. The time complexity in this case is constant, i.e. O (1).

If the pointer to the previous node is unknown in a simply linked list and can only be found by moving the list from the head until it reaches a node that has the next node pointer to node that should be removed. The time complexity in this case is O (n).

In cases where the node to be deleted is known only by value, the list needs to be searched and the time complexity becomes O (n) in both single and doubly linked lists.

Answer 2

Because you cannot look back ...

Answer 3

Insert and remove in a known position - O (1). However, find this position O (n) if it is not the head or tail of the list.

When we talk about the complexity of inserting and deleting, we usually assume that we already know where this will happen.

Answer 4

This is due to the difficulty of fixing the next pointer in the node that precedes the one you are deleting.

Answer 5

If the element to be deleted is the head (or first) of the node, we need to go to the node before the one to be deleted. Therefore, in the worst case, i.e. When we need to delete the last node, the pointer must go all the way to the second last node, thereby crossing the (n-1) position, which gives us the time complexity of O (n).

Answer 6

Actual deletion in singly linked lists can also be implemented in O (1).

Given a singly linked list with the following state:

SinglyLinkedList: Node 1 -> Node 2 Node 2 -> Node 3 Node 3 -> None Head = Node 3 

We can implement delete Note 2 this way:

 Node 2 Value <- Node 3 Value Node 2 -> None 

Here we replace the Node 2 value with the value of the next node ( Node 3 ) and set its next pointer to the value of the next pointer of the Node 3 ( None ) value, now skipping effectively “duplicate” Node 3 . Thus, no workaround is required.