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.