I just finished a short conversation with Aaron Randall from London who used the little Windows Live Messenger Flash application in my sidebar (oh, how I love thee, Internets) to ask me a question he had about linked lists after reading one of my posts:
“I am trying to understand the data structure for a doubly-linked list. I wanted to see if there was any way of having a data structure that could survive things like hardware failure (the computer can go down during updating a doubly-linked list without having its node broken/separated)”
His question was specifically for insertion and it got me thinking. The problem here is that given three nodes (inserting B between A and C), there are four steps to insertion into a doubly linked list, none of which has to be made in any specific order: Update A’s forward link to B, update B’s forward link to C, update B’s backward link to A and also update C’s backward link to B.
Given an abnormal termination, one has to be able to resume operation with the assumption that the data’s integrity remains. This means that no matter during which phase of the insertion the computer fails, you will be able to resume normal work when it returns to its normal state.
- A’s FutureNext pointer is set to point to B. Commit to disk.
- B’s Next pointer is set to point to C.
- A’s Next pointer is copied from its FutureNext pointer.
- C’s Previous pointer is set to point to B.
- B’s Previous pointer is set to point to A.
- A’s FutureNext pointer is nullified. Commit to disk.
The first step is the first phase in the two-phase commit, in which the link to the new node is established. Should a failure occur at any time after the first stage’s completion, a simple batch application scanning nodes for a non-null FutureNext pointer and completing the remaining five steps would be sufficient to keep data integrity.
Hope this helps, Aaron. :)