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. statement to remove operation

for any node to be deleted other than front and end.

select node to be delete lets its name be node,

point to node->next ->prev = node->prev ;

and also point

node->prev->next = node->next;

and free(node) from memory.

pseudocode for above operation is

void delete(Node head,Node node)

{

if (head == NULL || node == NULL)

{

return;

}

if (head ==node)

{

head = node->next;

}

if (node->next != NULL)

{

node->next->prev = node->prev;

}

if (node->prev != NULL)

{

node->prev->next = node->next;

}

free(node); // remove from memory

}

c. since each operation of shifting nodes is done in constant time , i.e. it does not depends on length of double linked list , hence its complexity is O(1).