Time complexity of node deletion in singly- and doubly-linked lists

Actually 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 -> Node 4
   Node 4 -> None

   Head = Node 1

We can implement delete Node 2 in such a way:

Node 2 Value <- Node 3 Value
Node 2 -> Node 4

Here we replace the value of Node 2 with the value of its next node (Node 3) and set its next value pointer to the next value pointer of Node 3 (Node 4), skipping over the now effectively "duplicate" Node 3. Thus no traversal needed.

Because you can't look backwards...

It has to do with the complexity of fixing up the next pointer in the node previous to the one you're deleting.

I don't think Its O(1) unless you know the address of the node whichh has to be deleted ..... Don't you loop to reach the node which has to be deleted from head ????

It is O(1) provided you have the address of the node which has to be deleted because you have it's prev node link and next node link . As you have all the necessary links available just make the "node of interest " out of the list by re arranging the links and then free() it .

But in a single linked list you have to traverse from head to get it's previous and next address doesn't matter whether you have the address to f the node to be deleted or the node position ( as in 1st ,2nd ,10th etc.,.) To be deleted .

Suppose there is a linked list from 1 to 10 and you have to delete node 5 whose location is given to you.

1 -> 2 -> 3 -> 4 -> 5-> 6-> 7-> 8 -> 9 -> 10

You will have to connect the next pointer of 4 to 6 in order to delete 5.

1. Doubly Linked list You can use the previous pointer on 5 to go to 4. Then you can do

4->next = 5->next;

or

Node* temp = givenNode->prev;
temp->next = givenNode->next;

Time Complexity = O(1)

2. singly Linked List Since you don't have a previous pointer in Singly linked list you cant go backwards so you will have to traverse the list from head

Node* temp = head;
while(temp->next != givenNode)
{
  temp = temp->next;
}
temp->next = givenNode->next;

Time Complexity = O(N)

In LRU cache design, deletion in doubly linked list takes O(1) time. LRU cache is implemented with hash map and doubly linked list. In the doubly linked list, we store the values and it hash maps we store the pointers of linked list nodes.

In case of a cache hit, we have to move the element to the front of the list. If the node is somewhere in the middle of doubly linked list, since we keep the pointers in the hash map and we retrieved in O(1) time, we can delete it by

  next_temp=retrieved_node.next
  prev_temp=retrieved_node.prev

then set the pointers to None

  retrieved_node.next=None
  retrieved_node.prev=None

and then you can reconnect the missing parts of the linked list

 prev_temp.next=next_temp