Linked List Node Deletion


#1

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)


#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


#3

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


#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.


#5

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


#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.