Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

(i) O(n)

(ii) O(log2 n)

(iii) O(logn)

(iv) O(1)

# Linked List Node Deletion

**Adya_Nanda**#1

**Ruturaj**#2

It’s a simple yet important question.

Say you have just 3 nodes.

1->2->3

Now suppose you are pointing at node 1. Now in order to delete node 1 the simple approach is just copy everything from node 2 to node 1.

i.e. 2->2->3

Now just delete the middle node.

i.e. 2->3

So the time complexity would be just O(1).

option (iv) is correct.

Code Section

Let X be the pointer to node 1.

X.data = X.next.data

X.next=X.next.next

**rider**#3

Let the arbitrary node is the first node itself or say the second node.Why then the complexity is not O(n)?

**Ruturaj**#4

Let P be a singly linked list. Let Q be the pointer to head of the list. What is the worst-case time complexity of the best known algorithm to delete any arbitrary node x from the list?

(i) O(n)

(ii) O(log2 n)

(iii) O(logn)

(iv) O(1)

In this case the worst case time complexity would be O(n).

Observe the difference between the 2 questions.

**prateek111**#5

#Ruturaj

1>2>3 how are you going to delete 2 node in constant time…provided Q pointer is pointed to 2 node

**Ruturaj**#6

Let X be the pointer to node 2.

X.data = X.next.data

X.next=X.next.next

The above code will work fine.

1st line will copy data from node 3 to node 2.

2nd line will be X.next = X.next.next = null (As X.next.next is null)

This will delete the node from the current linked list. In java the memory will be freed automatically but in c like language memory would be reserved but it will be unlinked from the current linked list.