You are writing a procedure to add a node to a doubly linked list. The system on which this procedure is to be run is subject to periodic hardware failures. The list your program is to maintain is of great importance. Your program must ensure the integrity of the list, even if the machine fails in the middle of executing your procedure. Supply the individual statements to update the list. (Your list should be fewer than a dozen statements long.) Explain the effect of a machine failure after each instruction. Describe how you would revise this procedure so that it would restore the integrity of the basic list after a machine failure.

What will be an ideal response?

The key condition is that the new node should be attached before any nodes in the original list are changed. Suppose A and B are original nodes, and N is to be inserted between them. Existing links are A ? B and A ? B. The links in N should be set first, so that A ? N and N ? B. Then, either A or B is changed so that A ? N. At this point, in the event of a failure, the backward link from B to A will be incorrect. In the event of a failure, a recovery procedure is run to test consistency of forward and backward links. In case of inconsistency, the forward link is taken to be correct, and the backward link is set to match. This back link completes the correct chain. If no failure occurs, the adding process completes by setting N ? B.