A double linked list may be implemented in a workspace array by utilising only one index next. That is, we do not need to retain a distinct field back in the workspace array nodes to detect the backward linkages. The goal is to add a member workspace[current] into workspace[current] rather than the index of the next element on the list. The difference is the index of the next item less the index of the entry preceding current. We must additionally keep two pointers to subsequent nodes in the list, the current index and the prior index of the node right before current in the linked list. To find the next entry of the list, we calculate workspace[current].difference + previous; Similarly, to find the entry preceding previous, we calculate current − workspace[previous].difference;
A double linked list may be implemented in a workspace array by utilising only one index next. That is, we do not need to retain a distinct field back in the workspace array nodes to detect the backward linkages. The goal is to add a member workspace[current] into workspace[current] rather than the index of the next element on the list. The difference is the index of the next item less the index of the entry preceding current. We must additionally keep two pointers to subsequent nodes in the list, the current index and the prior index of the node right before current in the linked list.
To find the next entry of the list, we calculate workspace[current].difference + previous; Similarly, to find the entry preceding previous, we calculate current − workspace[previous].difference;
Step by step
Solved in 2 steps
