Question

1. Consider a “Remove” operation from a doubly linked list other than front and end.
   1. Explain the implementation of “Remove” operation using a drawing by showing appropriate links.
   2. Using the explanation of (a) write the statements to implement the “Remove” operation.
   3. Using (b) show that the complexity of “Remove” operation is O(1).

Answer 1

a)

b)

If "n" is the node to be removed then do the following operations:

1) n.prev.next = n.next
2) n.next.prev = n.prev
Now the node n is not reachable by the linked list and hence had been removed from the linked list.

c) Since n.prev.next = n.next and n.next.prev = n.prev are the only 2 operations to be done to remove a node in between the head and end of any linked list, the complexity is constant (i.e.) O(1)